Subgame perfect implementation of voting rules via randomized mechanisms

We characterize completely ordinal and onto choice rules that are subgame perfect of Nash equilibrium (SPE) implementable via randomized mechanisms under strict preferences. The characterization is very operationalizable, and allows us to analyse SPE implementability of voting rules. We show that no scoring rule is SPE implementable. However, the top-cycle and the uncovered correspondences as well as plurality with runoff and any strongly Condorcet consistent voting rule can be SPE implemented. Therefore our results are favourable to majority based voting rules over scoring rules. Nevertheless, we show that many interesting Condorcet consistent but not strongly Condorcet consistent rules, such as the Copeland rule, the Kramer rule and the Simpson rule, cannot be SPE implemented.     

On the likelihood of Condorcet's profiles

Consider a group of individuals who have to collectively choose an outcome from a finite set of feasible alternatives. A scoring or positional rule is an aggregation procedure where each voter awards a given number of points, w _j, to the alternative she ranks in j ^th position in her preference ordering; The outcome chosen is then the alternative that receives the highest number of points. A Condorcet or majority winner is a candidate who obtains more votes than her opponents in any pairwise comparison. Condorcet [4] showed that all positional rules fail to satisfy the majority criterion. Furthermore, he supplied a famous example where all the positional rules select simultaneously the same winner while the majority rule picks another one. Let P ^* be the probability of such events in three-candidate elections. We apply the techniques of Merlin et al. [17] to evaluate P ^* for a large population under the Impartial Culture condition. With these assumptions, such a paradox occurs in 1.808% of the cases. Received: 30 April 1999/Accepted: 14 September 2000     

Condorcet efficiencies under the maximal culture condition

The Condorcet winner in an election is a candidate that could defeat each other candidate in a series of pairwise majority rule elections. The Condorcet efficiency of a voting rule is the conditional probability that the voting rule will elect the Condorcet winner, given that such a winner exists. The study considers the Condorcet efficiency of basic voting rules under various assumptions about how voter preference rankings are obtained. Particular attention is given to situations in which the maximal culture condition is used as a basis for obtaining voter preferences. Received: 4 February 1998/Accepted: 13 April 1998     

The Strong No Show Paradoxes are a common flaw in Condorcet voting correspondences

The No Show Paradox (there is a voter who would rather not vote) is known to affect every Condorcet voting function. This paper analyses two strong versions of this paradox in the context of Condorcet voting correspondences. The first says that there is a voter whose favorite candidate loses the election if she votes honestly, but gets elected if she abstains. The second says that there is a voter whose least preferred candidate gets elected if she votes honestly, but loses the election if she abstains. All Condorcet correspondences satisfying some weak domination properties are shown to be affected by these strong forms of the paradox. On the other hand, with the exception of the Simpson-Cramer Minmax and the Young rule, all the Condorcet correspondences that (to the best of our knowledge) are proposed in the literature suffer from these two paradoxes. Received: 30 November 1999/Accepted: 27 March 2000     

Rationalizations of Condorcet-consistent rules via distances of hamming type

In voting, the main idea of the distance rationalizability framework is to view the voters’ preferences as an imperfect approximation to some kind of consensus. This approach, which is deeply rooted in the social choice literature, allows one to define (“rationalize”) voting rules via a consensus class of elections and a distance: a candidate is said to be an election winner if she is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be distance-rationalized. In this article, we provide new results on distance rationalizability of several Condorcet-consistent voting rules. In particular, we distance-rationalize the Young rule and Maximin using distances similar to the Hamming distance. It has been claimed that the Young rule can be rationalized by the Condorcet consensus class and the Hamming distance; we show that this claim is incorrect and, in fact, this consensus class and distance yield a new rule, which has not been studied before. We prove that, similarly to the Young rule, this new rule has a computationally hard winner determination problem.     

Scoring rule voting games and dominance solvability

This article studies the dominance solvability (by iterated deletion of weakly dominated strategies) of general scoring rule voting games when there are three alternatives. The scoring rules we study include Plurality rule, Approval voting, Borda rule, and Relative Utilitarianism. We provide sufficient conditions for dominance solvability of general scoring rule voting games. The sufficient conditions that we provide for dominance solvability are in terms of one statistic of the game: sufficient agreement on the best alternative or on the worst alternative. We also show that the solutions coincide with the set of Condorcet Winners whenever the sufficient conditions for dominance solvability are satisfied. Approval Voting performs the best in terms of our criteria.     

The replacement principle for the provision of multiple public goods on tree networks

This article considers the provision of two public goods on tree networks where each agent has a single-peaked preference. We show that if there are at least four agents, then no social choice rule exists that satisfies efficiency and replacement-domination. In fact, these properties are incompatible, even if agents’ preferences are restricted to a smaller domain of symmetric single-peaked preferences. However, for rules on an interval, we prove that Miyagawa’s (Soc Choice Welf 18:527–541, 2001) characterization that only the left-peaks rule and the right-peaks rule satisfy both of these properties also holds on the domain of symmetric single-peaked preferences. Moreover, if agents’ peak locations are restricted to either the nodes or the endpoints of trees, rules exist on a subclass of trees. We provide a characterization of a family of such rules for this tree subclass.     

Allocating multiple estates among agents with single-peaked preferences

We consider the problem of allocating multiple social endowments (estates) of a perfectly divisible commodity among a group of agents with single-peaked preferences when each agent’s share can come from at most one estate. We inquire if well-known single-estate rules, such as the Uniform rule, the Proportional rule or the fixed-path rules can be coupled with a matching rule so as to achieve efficiency in the multi-estate level. On the class of problems where all agents have symmetric preferences, any efficient single-estate rule can be extended to an efficient multi-estate rule. If we allow asymmetric preferences however, this is no more the case. For nondictatorial single-estate rules that satisfy efficiency, strategy proofness, consistency, and resource monotonicity, an efficient extension to multiple estates is impossible. A similar impossibility also holds for single-estate rules that satisfy efficiency, peak-only, and a weak fairness property. We would like to express our gratitude to Bhaskar Dutta, Semih Koray, Hervé Moulin, and Yuntong Wang as well as an associate editor and two anonymous referees of this journal for detailed comments and suggestions. We also thank the seminar participants at Bilkent University, Indian Statistical Institute, Bilgi University, University of Warwick, ASSET 2003, and BWED XXVI.     

The sensitivity of weight selection on the Condorcet efficiency of weighted scoring rules

A weighted scoring rule, Rule λ, on three alternative elections selects the winner by awarding 1 point to each voter's first ranked candidate, λ points to the second ranked candidate, and zero to the third ranked candidate. The Condorcet winner is the candidate that would defeat each other candidate in a series of pairwise elections by majority rule. The Condorcet efficiency of Rule λ is the conditional probability that Rule λ selects the Condorcet winner, given that a Condorcet winner exists. Borda rule (λ=1/2) is the weighted scoring rule that maximizes Condorcet efficiency. The current study considers the conditional probability that Borda rule selects the Rule λ winner, given that Rule λ elects the Condorcet winner with a large electorate. Received: 21 August 1996 / Accepted: 7 January 1997     

On the selection of the same winner by all scoring rules

Different scoring rules can result in the selection of any of the k competing candidates, given the same preference profile, (Saari DG 2001, Chaotic elections! A mathematician looks at voting. American Mathematical Society, Providence, R.I.). It is also possible that a candidate, and even a Condorcet winning candidate, cannot be selected by any scoring rule, (Saari DG 2000 Econ Theory 15:55–101). These findings are balanced by Saari’s result (Saari DG 1992 Soc Choice Welf 9(4):277–306) that specifies the necessary and sufficient condition for the selection of the same candidate by all scoring rules. This condition is, however, indirect. We provide a sufficient condition that is stated directly in terms of the preference profile; therefore, its testability does not require the verdict of any voting rule.     

Aggregation of coarse preferences

We consider weak preference orderings over a set A _n of n alternatives. An individual preference is of refinement?≤n if it first partitions A _n into ? subsets of `tied' alternatives, and then ranks these subsets within a linear ordering. When ?<n, preferences are coarse. It is shown that, if the refinement of preferences does not exceed ?, a super majority rule (within non-abstaining voters) with rate 1− 1/? is necessary and sufficient to rule out Condorcet cycles of any length. It is argued moreover how the coarser the individual preferences, (1) the smaller the rate of super majority necessary to rule out cycles `in probability'; (2) the more probable the pairwise comparisons of alternatives, for any given super majority rule. Received: 29 June 1999/Accepted: 25 February 2000     

Simple manipulation-resistant voting systems designed to elect Condorcet candidates and suitable for large-scale public elections

This article focuses on voting systems that (i) aim to select the Condorcet candidate in the common case where one exists and (ii) impede manipulation by exploiting voter knowledge of electorate preferences. The systems are relatively simple, both mathematically and for voter understanding, and are fully workable for large-scale elections. Their designated equilibrium strategies, under which voters vote sincerely, involve discerning the top one or two candidates in the preference ordering of the electorate. One set of systems uses its ballot to obtain voters’ preference rankings plus approval votes, and tallies the latter if no Condorcet winner exists. It offers solid advantages vis-à-vis instant-runoff voting, which uses a kindred ballot and has attracted recent reformers. Another set of systems uses only approval voting, which is examined from a new angle.     

Does majoritarian approval matter in selecting a social choice rule? An exploratory panel study

This study is an attempt to empirically detect the public opinion concerning majoritarian approval axiom. A social choice rule respects majoritarian approval iff it chooses only those alternatives which are regarded by a majority of “voters” to be among the “better half” of the candidates available. We focus on three social choice rules, the Majoritarian Compromise, Borda’s Rule and Condorcet’s Method, among which the Majoritarian Compromise is the only social choice rule always respecting majoritarian approval. We confronted each of our 288 subjects with four hypothetical preference profiles of a hypothetical electorate over some abstract set of four alternatives. At each hypothetical preference profile, two representing the preferences of five and two other of seven voters, the subject was asked to indicate, from an impartial viewpoint, which of the four alternatives should be chosen whose preference profile was presented, which if that is unavailable, then which if both of the above are unavailable, and finally which alternative should be avoided especially. In each of these profiles there is a Majoritarian Compromise-winner, a Borda-winner and a Condorcet-winner, and the Majoritarian Compromise-winner is always distinct from both the Borda-winner and the Condorcet-winner, while the Borda- and Condorcet-winners sometimes coincide. If the Borda- and Condorcet-winners coincide then there are two dummy candidates, otherwise only one, and dummies coincide with neither of the Majoritarian Compromise-, Borda- or Condorcet-winner. We presented our subjects with various types of hypothetical preference profiles, some where Borda respecting majoritarian approval, some where it failed to do so, then again for Condorcet, some profiles it respected majoritarian approval and some where it did not. The main thing we wanted to see was whether subjects’ support for Borda and Condorcet was higher when this social choice rule respected majoritarian approval than it did not. Our unambiguous overall empirical finding is that our subjects’ support for Borda and Condorcet was significantly stronger as they respect majoritarian approval.     

Bargaining over a finite set of alternatives

We analyze bilateral bargaining over a finite set of alternatives. We look for "good" ordinal solutions to such problems and show that Unanimity Compromise and Rational Compromise are the only bargaining rules that satisfy a basic set of properties. We then extend our analysis to admit problems with countably infinite alternatives. We show that, on this class, no bargaining rule choosing finite subsets of alternatives can be neutral. When rephrased in the utility framework of Nash (1950), this implies that there is no ordinal bargaining rule that is finite-valued. Professor Sertel passed away on January 25, 2003.     

Sophisticated voting and equilibrium refinements under plurality rule

In this paper we show in the context of voting games with plurality rule that the “perfect” equilibrium concept does not appear restrictive enough, since, independently of preferences, it can exclude at most the election of only one candidate. Furthermore, some examples show that there are “perfect” equilibria that are not “proper”. However, also some “proper” outcome is eliminated by sophisticated voting, while Mertens' stable set fully satisfies such criterium, for generic plurality games. Moreover, we highlight a weakness of the simple sophisticated voting principle. Finally, we find that, for some games, sophisticated voting (and strategic stability) does not elect the Condorcet winner, neither it respects Duverger's law, even with a large number of voters. Received: 16 March 1999/Accepted: 25 September 1999     

A comparison of theoretical and empirical evaluations of the Borda Compromise

The Borda Compromise states that, if one has to choose among five popular voting rules that are not Condorcet consistent, one should always give preference to the Borda rule over the four other rules. We assess the theoretical as well as the empirical support for the Borda Compromise. We find that, despite considerable differences between the properties of the theoretical framework and the characteristics of two sets of observed ranking data, all three analyses provide considerable support for the Borda Compromise.     

Some startling inconsistencies when electing committees

We generalize the idea of a Condorcet winner to committee elections to select a Condorcet committee of size m. As in the case of a Condorcet winner, the Condorcet committee need not exist. We adapt two methods to measure how far a set of m candidates is from being the Condorcet committee. In particular, we generalize a procedure proposed by Lewis Carroll for selecting the candidate that is closest to being the Condorcet winner to allow the selection of a committee. We also generalize Kemenys method, which gives a complete transitive ranking, to the selection of committees and show that it is closely related to the first method.We show that these methods lead to some surprising inconsistencies. For example, the committee of size k may be disjoint from the committee of size j or they may overlap in any manner, the committee arising from Carrolls method may appear at any locations in the Kemeny ranking, and except for two highly restrictive cases, the members of the committee arising from Kemenys method may appear at any location in the Kemeny ranking. The author wishes to express his thanks to Don Saari for his conversations and suggestions for the paper and to the Institute for Mathematical Behavioral Sciences at the University of California at Irvine where the initial work for this paper took place. He also wishes to thank the anonymous reviewer whose careful reading and suggestions greatly improved the paper.     

Cycling of simple rules in the spatial model

McKelvey [4] proved that for strong simple preference aggregation rules applied to multidimensional sets of alternatives, the typical situation is that either the core is nonempty or the top-cycle set includes all available alternatives. But the requirement that the rule be strong excludes, inter alia, all supermajority rules. In this note, we show that McKelvey's theorem further implies that the typical situation for any simple rule is that either the core is nonempty or the weak top-cycle set (equivalently, the core of the transitive closure of the rule) includes all available alternatives. Moreover, it is often the case that both of these statements obtain. Received: 13 October 1997/Accepted: 24 August 1998     

Some issues related to the topological aggregation of preferences

This paper deals with the topological approach to social choice theory initiated by Chichilnisky. We study several issues concerning the existence and uniqueness of Chichilnisky rules defined on preference spaces. We show that on topological vector spaces the only additive, anonymous, and unanimous aggregation n-rule is the convex mean. We study the case of infinite agents and show that an infinite Chichilnisky rule might be considered as the limit of rules for finitely many agents. Finally, we show that under some restrictions on the preference space, the existence of a Chichilnisky rule for every finite case implies the existence of a weak Chichilnisky rule for the infinite case.     

A comparison of pricing rules for auctions and fair division games

Consider an auction or fair division game where every bidder knows his true value of the single object but is only incompletely informed about the true values of his competitors. By imposing the axiom of envy freeness with respect to stated preferences the set of pricing rules is restricted to the prices between the highest and second highest bid. Whereas for auctions one also can satisfy incentive compatibility, the same is not true for fair division games. We analyse and compare the different pricing rules, partly incentive compatible and partly not, by deriving the optimal bidding strategies. By comparing the payoff expectations induced by the various pricing rules we can prove directly a special equivalence statement saying that expected payoffs do not depend on the pricing rule. It is interesting that in fair division games equivalence of pricing rules is only valid if information is sufficiently incomplete.The authors gratefully acknowledge the helpful comments of an anonymous referee