Voting power in a system of compound majority rule

In 1973, the United States Supreme Court ruled that a water district's voting scheme that apportioned votes on the basis of the assessed valuation of acreage in the district was constitutional. Among the justifications for the constitutionality of this scheme was the concurrent requirement that legislation be approved by a majority of voters as well as by a majority of weighted votes. However, analysis of this voting scheme in game-theoretic terms indicates that this justification is only partial: when two sets of winning coalitions must form simultaneously in order to pass legislation, the voting power of each voter in the combined system equals the mean of the voting power afforded each voter in each simple system. The results can be generalized to three or more concurrent requirements.     

Incoherent majorities: The McGarvey problem in judgement aggregation

Judgement aggregation is a model of social choice where the space of social alternatives is the set of consistent truth-valuations (‘judgements’) on a family of logically interconnected propositions. It is well known that propositionwise majority voting can yield logically inconsistent judgements. We show that, for a variety of spaces, propositionwise majority voting can yield any possible judgement. By considering the geometry of sub-polytopes of the Hamming cube, we also estimate the number of voters required to achieve all possible judgements. These results generalize the classic results of McGarvey (1953) [13] and Stearns (1959) [22].     

Optimal bounds for the no-show paradox via SAT solving

One of the most important desirable properties in social choice theory is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result by Moulin (1988) has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin’s result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.     

Special domains and nonmanipulability

We investigate domains on which a nonmanipulable, nondictatorial social choice function exists, having at least three distinct values. We do not make the assumptions of Kalai and Muller (1977). We classify all such 2-person functions on the domain which is the cyclic group Z_m. We show that for any domain containing Z_m, existence for 2 voters and existence for some n > 2 voters are equivalent. We show that for an n-person, onto, nonmanipulable social choice function F on Z_m, F(P₁, P₂,…, P_n) {x₁, x₂,…, x_n} always, x_i being the most preferred alternative under preference P_i. We show that no domain containing the dihedral group admits such a social choice function. We show that there exists a domain on which all k-tuples are free for arbitrarily large k, for which such a social choice function does exist.     

Majority voting leads to unanimity

We consider a situation where society decides, through majority voting in a secret ballot, between the alternatives of ‘reform’ and ‘status quo’. Reform is assumed to create a minority of winners, while being efficient in the Kaldor–Hicks sense. We explore the consequences of allowing binding transfers between voters conditional on the chosen alternative. In particular, we establish conditions under which the winners wish to compensate all losers, thus leading to unanimity for reform, rather than compensating some losers to form a non-maximal majority. The analysis employs concepts from cooperative game theory.      

大型群体决策问题中的简单多数规则（3个评选对象场合）

一个群体决策问题取决于两个因素,一个是群体决策的规则,另一个是投票。当选定群体决策规则时,一个群体决策问题由投票完全决定,此时,群体决策问题与投票之间一一对应。简单多数规则是个简单且被广泛采用的群体决策规则,但它有缺陷,我们可举出些群体决策问题使用简单多数规则没法从投票得到最后群体决策的结果。这里我们将给出一个简单多数规则的有趣性质,即在3个评选对象场合,使用简单多数规则没法从投票得到最后群体决策结果的n个评选人的群体决策问题的个数与所有n个评选人的群体决策问题的个数之比当评选人个数n趋向无穷时趋于零,这说明3个评选对象的大型群体决策场合,简单多数规则的缺陷不严重。     

Three-dimensional Yang-Mills-Higgs equations in gauge-invariant variables

A formulation of three-dimensionalSU(2) andSO(1,2) Yang-Mills theories in the gauge-invariant variablesG _ij=tr^* F _i ^* F_j is proposed. It is shown that the tensorG _ij satisfies three-dimensional Einstein equations with simple right-hand side andG _ij playing the role of a metric. This result is generalized to the case of a system of Yang-Mills-Higgs fields.Moscow State University. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 94, No. 1, pp. 66–75, January, 1993.     

Calculus of Functorial Morphisms

We prove that, if F, G: 𝒞 → 𝒟 are two right exact functors between two Grothendieck categories such that they commute with coproducts and U is a generator of 𝒞, then there is a bijection between Nat(F, G) and the centralizer of Hom_𝒟(F(U), G(U)) considered as an Hom_𝒞(U, U)-Hom_𝒞(U, U)-bimodule. We also prove a dual of this result and give applications to Frobenius functors between Grothendieck categories.     

The McKay conjecture for exceptional groups and odd primes

Let G be a simply-connected simple algebraic group over an algebraically closed field of characteristic p with a Frobenius map F : G → G and G := G ^F , such that the root system is of exceptional type or G is a Suzuki group or Steinberg’s triality group. We show that all irreducible characters of C _G (S), the centraliser of S in G, extend to their inertia group in N _G (S), where S is any F-stable Sylow torus of (G, F). Together with the work in [16] this implies that the McKay conjecture is true for G and odd primes ℓ different from the defining characteristic. Moreover it shows important properties of the associated simple groups, which are relevant for the proof that the associated simple groups are good in the sense of Isaacs, Malle and Navarro, as defined in [14]. This research has been supported by the DFG-grant “Die Alperin-McKay-Vermutung für endliche Gruppen” and an Oberwolfach Leibniz fellowship.     

Asymptotic probability of majority inversion under a general binomial voting model

We obtain limits on the probability of majority inversion when the number of voters tends to infinity, for a binomial voting model specific to each state with different population sizes, and for different voting quotas in the two stages of the voting procedure. The case of weighted votes at the second stage is also discussed. For an important special case where the limit cannot be determined, we provide an exact expression for the inversion probability, but only for unweighted votes.     

Choice from a Three-Element Set: Some Lessons of the 2000 Presidential Campaign in the United States

We consider the behavior of four choice rules—plurality voting, approval voting, Borda count, and self-consistent choice—when applied to choose the best option from a three-element set. It is assumed that the two main options are preferred by a large majority of the voters, while the third option gets a very small number of votes and influences the election outcome only when the two main options receive a close number of votes. When used to rate the main options, Borda count and self-consistent choice contain terms that allow both for the strength of preferences of the voters and the rating of the main candidates by voters who vote for the third option. In this way, it becomes possible to determine more reliably the winner when plurality voting or approval voting produce close results.     

Win probabilities and simple majorities in probabilistic voting situations

This paper considers an election between candidatesA andB in which (1) voters may be uncertain about which candidate they will vote for, and (2) the winner is to be determined by a lottery betweenA andB that is based on their vote totals. This lottery is required to treat voters equally, to treat candidates equally, and to respond nonnegatively to increased support for a candidate. The set _n of all such lottery rules based on a total ofn voters is the convex hull of aboutn/2 basic lottery rules which include the simple majority rule. For odd values ofn 3 let , and for even values ofn 4 let . With the average of then voters probabilities of voting forA, it is shown that within _n the simple majority rule maximizes candidateA's overall win probability whenever , and that(n) is the smallest number for which this is true. Similarly, the simple majority rule maximizesB's overall win probability whenever (the average of the voters probabilities of voting forB) is as large as(n). This research was supported by the National Science Foundation, Grant SOC 75-00941.     

A core of voting games with improved foresight

This paper considers voting situations in which the vote takes place iteratively. If a coalition replaces the status quo a with a contestant b, then b becomes the new status quo, and the vote goes on until a candidate is reached that no winning coalition is willing to replace. It is well known that the core, that is, the set of undominated alternatives, may be empty. To alleviate this problem, Rubinstein [Rubinstein, A., 1980. Stability of decision systems under majority rule. Journal of Economic Theory 23, 150–159] assumes that voters look forward one vote before deciding to replace an alternative by a new one. They will not do so if the new status quo is going to be replaced by a third that is less interesting than the first. The stability set, that is, the set of undominated alternatives under this behavior, is always non-empty when preferences are strict. However, this is not necessarily the case when voters’ indifference is allowed. Le Breton and Salles [Le Breton, M., Salles, M., 1990. The stability set of voting games: Classification and generecity results. International Journal of Game Theory 19, 111–127], Li [Li, S., 1993. Stability of voting games. Social Choice and Welfare 10, 51–56] and Martin [Martin, M., 1998. Quota games and stability set of order d. Economic Letters 59, 145–151] extend the sophistication of the voters by having them look d votes forward along the iterative process. For d sufficiently large, the resulting set of undominated alternatives is always non-empty even if indifference is allowed. We show that it may be unduly large. Next, by assuming that other voters along a chain of votes are also rational, that is, they also look forward to make sure that the votes taking place later on will not lead to a worst issue for them, we are able to reduce the size of this set while insuring its non-emptiness. Finally, we show that a vote with sufficient foresight satisfies a no-regret property, contrarily to the classical core and the stability set.     

The Littlewood-Richardson rule for wreath products with symmetric groups and the quiver of the category F≀FIn

We give a new proof for the Littlewood-Richardson rule for the wreath product F?S_n where F is a finite group. Our proof does not use symmetric functions but use more elementary representation theoretic tools. We also derive a branching rule for inducing the natural embedding of F?S_n to F?S_n+1. We then apply the generalized Littlewood-Richardson rule for computing the ordinary quiver of the category F?FI_n where FI_n is the category of all injective functions between subsets of an n-element set.     

Free Resolution Invariants for Finite Groups

Given a finite group G and a G-free resolution F _* of Z, then d _G (Im(F _m+1F _m ))–(–1) ^m–i d _G (F _i ) is almost always an invariant of G.     

两类简单多数原则的完全特征

易建新(2005)引入了两类多数投票的社会福利函数,本文用无关备选对象的独立性、匿名性、中立性等公理给出了它们的完全特征.     

Federations and transitive group choice

The following is a brief English summary of the paper Mirkin (1979), in which he discusses social welfare functions where the relations involved are solely assumed to be reflexive. Under axioms of independence and neutrality, monotonicity, and two domain assumptions the author shows that such a social welfare function is determined by a ‘federation’,i.e., the set of coalitions such that if that each member considers a not worse than b so does the group. The author then characterizes transitive, completeness, definiteness, (a sort of non-indifference assumption), and majority rule in this framework. He also characterizes those domains on which social welfare functions determined by federations F satisfying I ∈ F if and only if ī ? F, are transitive. We omit proofs, which are given in the Russian version, as well as the author's discussion of these results.     

Strong and coalition-proof political equilibria under plurality and runoff rule

We analyze the effects of voter coordination on the equilibrium of voting games. Specifically, we analyze the concepts of strong equilibrium and coalition-proof equilibrium for plurality rule and runoff rule elections. We characterize these equilibria in the three candidate case, and provide results for important special cases in the general multicandidate case.      

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Recognition of the Finite Simple Groups F 4(2m) by Spectrum

The spectrum of a finite group is the set of its element orders. A finite group G is said to be recognizable by spectrum, if every finite group with the same spectrum as G is isomorphic to G. The purpose of the paper is to prove that for every natural m the finite simple Chevalley group F ₄(2 ^m ) is recognizable by spectrum.