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     

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     

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     

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     

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.     

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     

A nail-biting election

In the first competitive election for President of the Social Choice and Welfare Society, the (official) approval-voting winner differed from the (hypothetical) Borda count winner, who was also the Condorcet winner. But because the election was essentially a toss-up, it is impossible to say who should have won. The election for Council was more true to form of other professional-society elections, with the winners identical, and even their rankings almost duplicative, under both voting systems. Received: 11 April 2000/Accepted: 26 March 2001     

A geometric examination of Kemeny's rule

By using geometry, a fairly complete analysis of Kemeny's rule (KR) is obtained. It is shown that the Borda Count (BC) always ranks the KR winner above the KR loser, and, conversely, KR always ranks the BC winner above the BC loser. Such KR relationships fail to hold for other positional methods. The geometric reasons why KR enjoys remarkably consistent election rankings as candidates are added or dropped are explained. The power of this KR consistency is demonstrated by comparing KR and BC outcomes. But KR's consistency carries a heavy cost; it requires KR to partially dismiss the crucial “individual rationality of voters” assumption. Received: 5 February 1998/Accepted: 26 May 1999     

Oligopolization in collective rent-seeking

In this paper we discuss the issue of when oligopolization in collective rent-seeking occurs, that is, when some groups retire from rent-seeking. A complete characterization of the pure-strategy Nash equilibrium in a collective rent-seeking game among m (≥2) heterogeneous groups is derived. The conditions of oligopolization are derived by using this result and related to the works of Nitzan [9, 10] and Hillman and Riley [3]. Also, the subgame perfect equilibrium of a simple two-stage collective rent-seeking game (Lee [7]) is fully characterized. In this game, it is confirmed that no group retires from the contest in the second stage and oligopolization never occurs. An example of the two-stage collective rent-seeking game with monitoring costs is devised to show the possibilities of oligopolization. Received: 21 September 1999/Accepted: 27 March 2001     

Representation of effectivity functions in coalition proof Nash equilibrium: A complete characterization

The concept of coalition proof Nash equilibrium was introduced by Bernheim et al. [5]. In the present paper, we consider the representation problem for coalition proof Nash equilibrium: For a given effectivity function, describing the power structure or the system of rights of coalitions in society, it is investigated whether there is a game form which gives rise to this effectivity function and which is such that for any preference assignment, there is a coalition proof Nash equilibrium.  It is shown that the effectivity functions which can be represented in coalition proof Nash equilibrium are exactly those which satisfy the well-known properties of maximality and superadditivity. As a corollary of the result, we obtain necessary conditions for implementation of a social choice correspondence in coalition proof Nash equilibrium which can be formulated in terms of the associated effectivity function. Received: 24 June 1999/Accepted: 20 September 2000     

‘One and a Half Dimensional’ Preferences and Majority Rule

I examine a model of majority rule in which alternatives are described by two characteristics: (1) their position in a standard, left-right dimension, and (2) their position in a good-bad dimension, over which voters have identical preferences. I show that when voters’ preferences are single-peaked and concave over the first dimension, majority rule is transitive, and the majority’s preferences are identical to the median voter’s. Thus, Black’s (The theory of committees and elections, 1958) theorem extends to such a “one and a half” dimensional framework. Meanwhile, another well-known result of majority rule, Downs’ (An economic theory of democracy, 1957) electoral competition model, does not extend to the framework. The condition that preferences can be represented in a one-and-a-half-dimensional framework is strictly weaker than the condition that preferences be single-peaked and symmetric. The condition is strictly stronger than the condition that preferences be order-restricted, as defined by Rothstein (Soc Choice Welf 7:331–342;1990).     

A smallest tournament for which the Banks set and the Copeland set are disjoint

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T; a Copeland winner of T is a vertex with a maximum out-degree. In this paper, we show that 13 is the minimum number of vertices that a tournament must have so that none of its Copeland winners is a Banks winner: for any tournament with less than 13 vertices, there is always at least one vertex which is a Copeland winner and a Banks winner simultaneously. Received: 2 May 1997 / Accepted: 30 September 1997     

Social Welfare Functions which preserve distances

The notion of keeping distances, introduced by N. Baigent in [2], avoids the need to introduce topological concepts when defining Social Welfare Functions with requirements analogous to those established by Chichilnsky in [3]. In the following study we propose an extension of the results of Baigent, in a non topological framework, to a much broader class of metrics which enables the case of infinite agents to be considered in a natural fashion. Received: 14 June 1999/Accepted: 4 November 1999     

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.     

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 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.     

Approximability of Dodgson’s rule

It is known that Dodgson’s rule is computationally very demanding. Tideman (Soc Choice Welf 4:185–206, 1987) suggested an approximation to it but did not investigate how often his approximation selects the Dodgson winner. We show that under the Impartial Culture assumption the probability that the Tideman winner is the Dodgson winner converges to 1 as the number of voters increase. However we show that this convergence is not exponentially fast. We suggest another approximation—we call it Dodgson Quick—for which this convergence is exponentially fast. Also we show that the Simpson and Dodgson rules are asymptotically different.     

Modeling large electorates with Fourier series, with applications to Nash equilibria in proximity and directional models of spatial competition

 In this paper we introduce harmonic analysis (Fourier series) as a tool for characterizing the existence of Nash equilibria in two-dimensional spatial majority rule voting games with large electorates. We apply our methods both to traditional proximity models and to directional models. In the latter voters exhibit preferences over directions rather than over alternatives, per se. A directional equilibrium can be characterized as a Condorcet direction, in analogy to the Condorcet (majority) winner in the usual voting models, i.e., a direction which is preferred by a majority to (or at least is not beaten by) any other direction. We provide a parallel treatment of the total median condition for equilibrium under proximity voting and equilibrium conditions for directional voting that shows that the former result is in terms of a strict equality (a knife-edge result very unlikely to hold) while the latter is in terms of an inequality which is relatively easy to satisfy. For the Matthews [3] directional model and a variant of the Rabinowitz and Macdonald [7] directional model, we present a sufficiency condition for the existence of a Condorcet directional vector in terms of the odd-numbered components of the Fourier series representing the density distribution of the voter points. We interpret our theoretical results by looking at real-world voter distributions and direction fields among voter points derived from U.S. and Norwegian survey data. Received: 7 July 1995 / Accepted: 14 May 1996     

The sensitivity of weight selection for scoring rules to profile proximity to single-peaked preferences

Niemi (Am Polit Sci Rev 63:488–497, 1969) proposed a simple measure of the cohesiveness of a group of n voters’ preferences that reflects the proximity of their preferences to single-peakedness. For three-candidate elections, this measure, k, reduces to the minimum number of voters who rank one of the candidates as being least preferred. The current study develops closed form representations for the conditional probability, PASW(n,IAC|k), that all weighted scoring rules will elect the Condorcet winner in an election, given a specified value of k. Results show a very strong relationship between PASW(n,IAC|k) and k, such that the determination of the voting rule to be used in an election becomes significantly less critical relative to the likelihood of electing the Condorcet winner as voters in a society have more structured preferences. As voters’ preferences become more unstructured as measured by their distance from single-peakedness, it becomes much more likely that different voting rules will select different winners.A preliminary version of this paper was presented at the European Public Choice Society Conference in Berlin, Germany, April 15–18, 2004.     

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.