Strong equilibrium outcomes of voting games ¶are the generalized Condorcet winners

We consider voting games induced by anonymous and top-unanimous social choice functions. The class of such social choice functions is quite broad, including every t-refinement of the Plurality Rule, Plurality with a Runoff, the Majoritarian Compromise and the Single Transferable Vote, i.e., any selection from either of these social choice rules which is obtained via tie-breaking among candidates according to any total order t on the set of alternatives. As announced in our title, the strong equilibrium outcomes of the voting games determined by such social choice functions turn out to be nothing but generalized Condorcet winners, namely the (n,q)-Condorcet winners. In the case of social choice functions (such as those just listed) which are furthermore top-majoritarian, they coincide with the classical Condorcet winners.The non-alphabetic ordering of names has a reason deserving to be explained. Murat R. Sertel, this man from the Bosphorus whose contributions put Turkey on the academic map of Economic Theory, passed away on January 25, 2003, while this paper was in print. His untimely death was met with deep sorrow by his colleagues, friends and students all over the world. Murat R. Sertel was one of the forerunners of the Age of Economic Design. He was a genuine scholar, brilliant intellectual, excellent teacher, beloved friend, a wonderful company, a devoted son and an affectionate father. May he rest in peace.¶The authors thank Semih Koray, Ipek Sanver, Fuad Aleskerov, Ahmet Alkan, Hakan Inal, Hervé Moulin, Bezalel Peleg, Robert Wilson, Muhamet Yldz and two anonymous referees for their helpful comments. Remzi Sanver gratefully acknowledges partial support from Istanbul Bilgi University, BÜVAK (Boaziçi University Foundation) and Serem Ltd.1999), Danilov (1992) for Nash implementation; Maskin (1979), Dutta and Sen (1991) for strong implementation; Moore and Repullo (1988), Abreu and Sen (1990) for subgame perfect implementation; Palfrey and Srivastava (1991), Jackson, Palfrey and Srivastava (1994) for undominated Nash implementation; Jackson (1991), Dutta and Sen (1994) for Bayesian implementation. So we know a lot about what is implementable, and what is not, via various solution concepts. In particular, Maskin (1979) shows that strong implementability of a social choice correspondence is inconsistent with the weak no veto power condition. ysis regarding the Nash equilibrium allocations of an allocation rule with wealth-regressive tax rates.The authors thank Semih Koray, Ipek Sanver, Fuad Aleskerov, Ahmet Alkan, Hakan Inal, Hervé Moulin, Bezalel Peleg, Robert Wilson, Muhamet Yldz and two anonymous referees for their helpful comments. Remzi Sanver gratefully acknowledges partial support from Istanbul Bilgi University, BÜVAK (Boaziçi University Foundation) and Serem Ltd.3 December 2001     

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     

Free triples,large indifference classes and the majority rule

We study classes of voting situations where agents may exhibit a systematic inability to distinguish between the elements of certain sets of alternatives. These sets of alternatives may differ from voter to voter, thus resulting in personalized families of preferences. We study the properties of the majority relation when defined on restricted domains that are the cartesian product of preference families, each one reflecting the corresponding agent’s objective indifferences, and otherwise allowing for all possible (strict) preference relations among alternatives. We present necessary and sufficient conditions on the preference domains of this type, guaranteeing that majority rule is quasi-transitive and thus the existence of Condorcet winners at any profile in the domain, and for any finite subset of alternatives. Finally, we compare our proposed restrictions with others in the literature, to conclude that they are independent of any previously discussed domain restriction.     

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.     

A comparison of Dodgson's method and Kemeny's rule

In an election without a Condorcet winner, Dodgson's method is designed to find the candidate that is “closest” to being a Condorcet winner. Similarly, if the head-to-head elections among all candidates do not give a complete transitive ranking, then Kemeny's Rule finds the “closest” transitive ranking. This paper uses geometric techniques to compare Dodgson's and Kemeny's notions of closeness and explain how conflict can arise between the two methods. Received: 19 October 1999/Accepted: 6 December 1999     

Justifiable preferences over opportunity sets

In this paper we say that a preference over opportunity sets is justifiable if there exists a reflexive and complete binary relation on the set of alternatives, such that one opportunity set is at least as good as a second, if and only if the there is at least one alternative from the first set which is no worse than any alternative of the two sets combined together, with respect to the binary relation on the alternatives. In keeping with the revered tradition set by von Neumann and Morgenstern we call a reflexive and complete binary relation, an abstract game (note: strictly speaking von Neumann and Morgenstern refer to the asymmetric part of a reflexive and complete binary relation as an abstract game; hence our terminology though analytically equivalent, leads to a harmless corruption of the original meaning). In this paper we obtain a necessary and sufficient condition for the justifiability of transitive and quasi transitive preferences over opportunity sets. I would like to thank Prasanta Pattanaik for motivation in this research. I would also like to thank Maurice Salles and an anonymous referee of this journal for useful suggestions leading to considerable improvement in the presentation. An earlier version of this paper was presented at the Sixth Annual Conference on Econometric Modeling for Africa, held at Pretoria from July 4–6, 2001. I would like to thank all the conference participants for their observations on my paper. However, the sole responsibility for errors that do remain is my own.     

Generating random weak orders and the probability of a Condorcet winner

We present an algorithm for generating a random weak order of m objects in which all possible weak orders are equally likely. The form of the algorithm suggests analytic expressions for the probability of a Condorcet winner both for linear and for weak preference orders. Received: 6 April 2000/Accepted: 31 January 2001     

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     

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     

Majority rule in multi-dimensional spatial models

A sufficient condition is derived for a policy y to be a Condorcet winner, when the set of feasible policies is some subsety ofR ^N with non-empty interior. Voters are assumed to differ in some scalar characteristic w. The sufficient condition refers only to voters' preferences over the set of preferred policies (of the various other voters). This set is a one-dimensional curve inR ^N> . The condition is that the indifference curves of each typew through the preferred policyy ^* (v) of any typev all be collinear. If the condition holds, then the preferred policyy ^* (m) of the median type of voter will be a Condorcet winner. If there are only three types of voter, then the above condition is also necessary for the existence of a Condorcet winner.This paper is a revision of the first part of my earlier Majority Rule with Multidimensional Economic Choices. I thank Ted Bergstrom, David Donaldson, and Greg Dow for very valuable comments on versions of that earlier paper, without implicating them in this current incarnation.     

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.     

On removing Condorcet effects from pairwise election tallies

Condorcet profiles are responsible for a number of well known preference aggregation paradoxes. It is reasonable to claim that these profiles represent complete ties between the candidates and should therefore be excluded to determine election outcomes. Established profile decomposition techniques are of limited usefulness in extracting and removing Condorcet effects, because of the computational complexity involved, even if complete knowledge of voters’ rankings of all candidates are available. The paper discusses an easily implementable method of removing or reducing Condorcet effects from pairwise scores. Pairwise scores (and not complete knowledge of voters’ rankings) are often the only available data based on which an election winner has to be determined.     

A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method

In recent years, the Pirate Party of Sweden, the Wikimedia Foundation, the Debian project, the “Software in the Public Interest” project, the Gentoo project, and many other private organizations adopted a new single-winner election method for internal elections and referendums. In this article, we will introduce this method, demonstrate that it satisfies, e.g., resolvability, Condorcet, Pareto, reversal symmetry, monotonicity, and independence of clones and present an O(C^3) algorithm to calculate the winner, where C is the number of alternatives.     

Condorcet efficiency: A preference for indifference

The Condorcet winner in an election is the candidate who would be able to defeat all other candidates in a series of pairwise elections. The Condorcet efficiency of a voting procedure is the conditional probability that it will elect the Condorcet winner, given that a Condorcet winner exists. The study considers the Condorcet efficiency of weighted scoring rules (WSR's) on three candidates for large electorates when voter indifference between candidates is allowed. It is shown that increasing the proportion of voters who have partial indifference will increase the probability that a Condorcet winner exists, and will also increase the Condorcet efficiency of all WSR's. The same observation is observed when the proportion of voters with complete preferences on candidates is reduced. Borda Rule is shown to be the WSR with maximum Condorcet efficiency over a broad range of assumptions related to voter preferences. The result of forcing voters to completely rank all candidates, by randomly breaking ties on candidates that are viewed as indifferent, leads to a reduction in the probability that a Condorcet winner exists and to a reduction in the Condorcet efficiency of all WSR's. Received: 31 July 1999/Accepted: 11 February 2000     

Generalized condorcet-winners for single peaked and single-plateau preferences

When preferences are single peaked the choice functions that are independent of irrelevant alternatives both in Nash's and in Arrow's sense are characterized. They take the Condorcet winner of the n individual peaks plus at most n-1 fixed ballots (phantom voters). These choice functions are also coalitionally strategy-proof.Next the domain of individual preferences is enlarged to allow for singleplateau preferences: again, Nash's IIA and Arrow's IIA uniquely characterize a class of generalized Condorcet winners choice functions. These are, again, coalitionally strategy-proof.     

Arrovian impossibilities in aggregating preferences over non-resolute outcomes

Let A be a set of alternatives whose power set is . Elements of are interpreted as non-resolute outcomes. We consider the aggregation of preference profiles over into a (social) preference over . In case we allow individuals to have any complete and transitive preference over , Arrow’s impossibility theorem naturally applies. However, the Arrovian impossibility prevails, even when the set of admissible preferences over is severely restricted. In fact, we identify a mild “regularity” condition which ensures the dictatoriality of a domain. Regularity is compatible with almost all standard extension axioms of the literature. Thus, we interpret our results as the strong prevalence of Arrow’s impossibility theorem in aggregating preferences over non-resolute outcomes. This paper is part of a project entitled “Social Perception—A Social Choice Perspective”, supported by Istanbul Bilgi University Research Fund. It has been completed while Remzi Sanver was visiting Ecole Polytechnique, Paris. We are grateful to both institutions. We thank Nick Baigent, two anonymous referees and an anonymous associate editor for their valuable comments.     

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.     

Voces populi and the art of listening

The strategy most damaging to many preferential election methods is to give insincerely low rank to the main opponent of one’s favourite candidate. Theorem 1 determines the 3-candidate Condorcet method that minimizes the number of noncyclic profiles allowing the strategic use of a given cyclic profile. Theorems 2, 3 and 4 establish conditions for an anonymous and neutral 3-candidate single-seat election to be monotonic and still avoid this strategy completely. Plurality elections combine these properties; among the others ‘conditional IRV’ gives the strongest challenge to the plurality winner. Conditional IRV is extended to any number of candidates. Theorem 5 is an impossibility of Gibbard–Satterthwaite type, describing three specific strategies that cannot all be avoided in meaningful anonymous and neutral election methods.     

Nash Implementation with Lottery Mechanisms

Consider the problem of exact Nash Implementation of social choice correspondences. Define a lottery mechanism as a mechanism in which the planner can randomize on alternatives out of equilibrium while pure alternatives are always chosen in equilibrium. When preferences over alternatives are strict, we show that Maskin monotonicity (Maskin in Rev Econ stud 66: 23–38, 1999) is both necessary and sufficient for a social choice correspondence to be Nash implementable. We discuss how to relax the assumption of strict preferences. Next, we examine social choice correspondences with private components. Finally, we apply our method to the issue of voluntary implementation (Jackon and Palfrey in J Econ Theory 98: 1–25, 2001).I thank Toyo Sakai for his comments on a previous draft. I also thank two anonymous referees and an editor of this journal for helpful comments that improved this paper. A previous version circulated as “A note on Maskin monotonicity”. After the results presented here were obtained, I became aware of a new unpublished paper by Benoit and Ok (2004). The result of Theorem 2 and the discussion that follows is partially similar to their Theorem 1.