Pairwise Strategy-Proofness and Self-Enforcing Manipulation

“Strategy-proofness” is one of the axioms that are most frequently used in the recent literature on social choice theory. It requires that by misrepresenting his preferences, no agent can manipulate the outcome of the social choice rule in his favor. The stronger requirement of “group strategy-proofness” is also often employed to obtain clear characterization results of social choice rules. Group strategy-proofness requires that no group of agents can manipulate the outcome in their favors. In this paper, we advocate “effective pairwise strategy-proofness.” It is the requirement that the social choice rule should be immune to unilateral manipulation and “self-enforcing” pairwise manipulation in the sense that no agent of a pair has the incentive to betray his partner. We apply the axiom of effective pairwise strategy-proofness to three types of economies: public good economy, pure exchange economy, and allotment economy. Although effective pairwise strategy-proofness is seemingly a much weaker axiom than group strategy-proofness, effective pairwise strategy-proofness characterizes social choice rules that are analyzed by using different axioms in the literature.     

Consistency between tastes and values: A universalization approach

The object of this paper is to propose a consistency test for an individual involved in collective choice process. Collective choice processes considered in the paper are those that transform individuals ‘tastes’– which reflect the self-interested view point of the individuals – into (social) ranking of alternatives. In addition to her tastes, an individual has values about the way by which collective decision should be made. We distinguish two categories of such values. First, there are end-values that restrict the class of social rankings that the individual considers ethically acceptable. Second there are aggregation-values that specify the way by which the social ranking should depend upon the individuals tastes. The consistency test stands on an hypothetical operation of universalization of the individual tastes to everyone. Five illustrations of the potential usefulness of our approach for interpreting social choice theory and welfare economics are proposed. These illustrations deal with utilitarian aggregation in the presence of income inequality aversion, the so-called ‘ethics of responsibility’ and the aggregation of individual ranking of opportunity sets based on their freedom of choice. A discussion of the relevance of the consistency test for addressing the problem of ‘laundering’ individual preferences is also provided. Received: 25 June 1998/Accepted: 16 March 1999     

A generalization of Campbell and Kelly’s trade-off theorem

This article considers social choice theory without the Pareto principle. We revisit the trade-off theorem developed by Campbell and Kelly (Econometrica 61:1355–1365, 1993) and generalize their result. By introducing an alternative measure of decisive structure, a dominance relation, we show that if a social welfare function dominates another social welfare function, then the number of pairs of alternatives which social ranking is independently of individual preferences under the former is not more than that under the latter. Moreover, we offer two applications of our main result.     

Choosing subsets: a size-independent probabilistic model and the quest for a social welfare ordering

“Subset voting” denotes a choice situation where one fixed set of choice alternatives (candidates, products) is offered to a group of decision makers, each of whom is requested to pick a subset containing any number of alternatives. In the context of subset voting we merge three choice paradigms, “approval voting“ from political science, the “weak utility model” from mathematical psychology, and “social welfare orderings” from social choice theory. We use a probabilistic choice model proposed by Falmagne and Regenwetter (1996) built upon the notion that each voter has a personal ranking of the alternatives and chooses a subset at the top of the ranking. Using an extension of Sen's (1966) theorem about value restriction, we provide necessary and sufficient conditions for this empirically testable choice model to yield a social welfare ordering. Furthermore, we develop a method to compute Borda scores and Condorcet winners from subset choice probabilities. The technique is illustrated on an election of the Mathematical Association of America (Brams, 1988). Received: 18 August 1995 / Accepted: 13 February 1997     

The borda and condorcet principles: Three medieval applications

We report three medieval works, hitherto unknown to social choice, which discuss procedures for elections when there are more than two candidates. Two of the three propose Borda methods and the third a Condorcet method of successive pairwise comparison. All three discuss problems of manipulation. One of them displays a matrix for pairwise comparisons; this is a work written in 1299, nearly 600 years before the matrix notation was believed to have been invented by C. L. Dodgson. We conclude with a review of the theory of voting in medieval Europe.We acknowledge with gratitude the support of the Leverhulme Trust for IMcL's work on the history of social choice; William Riker for an initial lead on Nicolas Cusanus; Alexander Murray for translating Cusanus and reviewing IMcL's translation of Lull's Latin text; and Robert Pring-Mill for reviewing JL's translation of Lull's Catalan text.     

Paired comparisons analysis: an axiomatic approach to ranking methods

In this paper we present an axiomatic analysis of several ranking methods for general tournaments. We find that the ranking method obtained by applying maximum likelihood to the (Zermelo-)Bradley-Terry model, the most common method in statistics and psychology, is one of the ranking methods that perform best with respect to the set of properties under consideration. A less known ranking method, generalised row sum, performs well too. We also study, among others, the fair bets ranking method, widely studied in social choice, and the least squares method.     

Monotonicity of ‘ranking by choosing’: A progress report

Procedures designed to select alternatives on the basis of the results of pairwise contests between them have received much attention in literature. The particular case of tournaments has been studied in depth. More recently weak tournaments and valued generalizations thereof have been investigated.The purpose of this paper is to investigate to what extent these choice procedures may be meaningfully used to define ranking procedures via their repeated use, i.e. when the equivalence classes of the ranking are determined by successive applications of the choice procedure. This is what we call ranking by choosing. As could be expected, such ranking procedures raise monotonicity problems. We analyze these problems and show that it is nevertheless possible to isolate a large class of well-behaved choice procedures for which failures of monotonicity are not overly serious. The hope of finding really attractive ranking by choosing procedures is however shown to be limited. Our results are illustrated on the case of tournaments.I am grateful to Hervé Raynaud and Jean-Claude Vansnick for stimulating discussions. Jean-François Laslier, Thierry Marchant, Bernard Monjardet, Xavier Juret and an anonymous referee made very helpful comments on earlier drafts of this text. Special thanks go to Patrice Perny who introduced me to the subject and to Olivier Hudry for his help with Slater orders. The usual caveat applies. Part of this work was accomplished while I was visiting the Service de Mathématiques de la Gestion at the Université Libre de Bruxelles (Brussels, Belgium). I gratefully acknowledge the warm hospitality of the Service de Mathématique de la Gestion as well as the support from the Belgian Fonds National de la Recherche Scientifique and the Brussels-Capital Region through a Research in Brussels action grant.     

Extended preferences and freedom of choice

The common choice theory in economics is based on the assumption that an individual is defined in terms of a binary preference relation. This preference relation is defined over alternatives without taking into account menu dependence and, in particular, freedom of choice or, more generally, the set that contains the alternatives. In this study we clarify the nature and the significance of freedom of choice which may positively or negatively affect the individual's welfare. Our proposed extended preference relation of the individual takes into account both the particular alternative and the opportunity set that he faces. This extended relation does not induce ranking of opportunity sets. Its restriction to a particular opportunity set is the paradigmatic preference relation and it can capture the dependence of preferences on freedom of choice. Our main result establishes the inconsistency between dependence of extended preferences on freedom of choice and the existence of a utility that represents the paradigmatic preference relation and any of its restrictions. Received: 30 December 1997/Accepted: 6 September 1999     

Choosing from a tournament

A tournament is any complete asymmetric relation over a finite set A of outcomes describing pairwise comparisons. A choice correspondence assigns to every tournament on A a subset of winners. Miller's uncovered set is an example for which we propose an axiomatic characterization. The set of Copeland winners (outcomes with maximal scores) is another example; it is a subset of the uncovered set: we note that it can be a dominated subset. A third example is derived from the sophisticated agenda algorithm; we argue that it is a better choice correspondence than the Copeland set.     

The Borda dictionary

Forn candidates, a profile of voters defines a unique Borda election ranking for each of the 2 ⁿ – (n + 1) subsets of two or more candidates. The Borda Dictionary is the set of all of these election listings that occur for any choice of a profile. As such, the dictionary contains all positive features, all flaws, and all paradoxes that can occur with single profile, sincere Borda elections. After the Borda Dictionary is characterized, it is used to show in what ways the Borda Count (BC) is an improvement over other positional voting methods and to derive several new BC properties. These properties include several new characterizations of the BC expressed in terms of axiomatic representations of social choice functions, as well as showing, for example, that the BC ranking ofn candidates can be uniquely determined by the BC rankings of all sets ofk <n candidates for any choice ofk between 2 andn.This research was supported, in part, by NSF grants IRI8415348, IRI-8803505 and a Fellowship from the Guggenheim Memorial Foundation.     

A prudent characterization of the Ranked Pairs Rule

We show that the Ranked Pairs Rule is equivalent to selecting the maximal linear orders with respect to a DiscriMin relation, which is a natural refinement of the Min relation used to define Arrow and Raynaud’s prudent orders. We provide an axiomatic characterization of the Ranked Pairs Rule by building on an earlier characterization of the prudent order ranking rule. We conclude that a monotonicity criterion is the main distinction between the two ranking rules.     

Quasi-transitive and Suzumura consistent relations

We examine properties of binary relations that complement quasi-transitivity and Suzumura consistency in the sense that they, in conjunction with the original axiom(s), are equivalent to transitivity. In general, the conjunction of quasi-transitivity and Suzumura consistency is weaker than transitivity but in the case of collective choice rules that satisfy further properties, this conjunction implies transitivity of the social relation. We prove this observation by characterizing the Pareto rule as the only collective choice rule such that collective preference relations are quasi-transitive and Suzumura consistent, and standard social choice axioms are satisfied.     

Strategic behaviour and a notion of ex ante efficiency in a voting model

A person is said to prefer in the stochastic dominance sense one lottery-over-outcomes over another lottery-over-outcomes if the probability of his (at least) first choice being selected in the first lottery is greater than or equal to the analogous probability in the second lottery, the probability of his at least second choice being selected in the first lottery is greater than or equal to the analogous probability in the second lottery, and so on, with at least one strict inequality. This (partial) preference relation is used to define straightforwardness of a social choice function that maps profiles of ordinal preferences into lotteries over outcomes. Given a prior probability distribution on profiles this partial preference ordering (taking into account the additional randomness) is used to induce a partial preference ordering over social choice functions for each individual. These are used in turn to define ex ante Pareto undominated (efficient) social choice functions. The main result is that it is impossible for a social choice function to be both ex ante efficient and straightforward. We also extend the result to cardinal preferences and expected utility evaluations.This work was supported by Grant #SOC 77-27403 and #SES 80-26086 from the National Science Foundation. It has been prepared at the University of Illinois and the University of Pennsylvania. We want to thank Steve Matthews and an anonymous referee for helpful comments     

The direct social preference relation in the theory of public expenditure

It is shown that if there is a finite number of private goods, a single public good, and the individual preferences satisfy certain monotonicity and separability conditions then there is a unique and complete social preference relation defined on the set of allocations by the requirement that the relation is individualistic in terms of the individual ordinal preferences. This relation, called the direct social preference relation, is derived without imposing interpersonal welfare comparisons and all its ordinal properties are inherited directly from those of the individual preferences. However, an allocation which is maximal in terms of the direct social preference relation on the set of feasible allocations is in general not Pareto optimal and the relation may therefore not be suitable as a guide to optimizing social choice.This version of the paper has benefitted from J. Weymark's insightful and detailed comments. In addition, valuable suggestions have been received from G. C. Archibald, C. Blackorby, D. Donaldson and D. Primont. All remaining errors are the sole responsibility of the author     

On randomized rationality

In contrast to the traditional notion of rationalizability of stochastic choice which requires the preference relations to be strict, we propose a notion of rationalizability without requiring the preference relations to be strict. Our definition is based on the simple hypothesis of a two-stage choice process: stage (i) a preference relation R is drawn according to a probability assignment; stage (ii) an alternative is picked from each feasible set according to a uniform lottery over the R-greatest set in it. We provide a necessary and sufficient condition for rationalizability of stochastic choice. Since our framework is general enough to subsume the traditional case, our result also provides an alternative characterization of the traditional notion of rationalizability. We also show the equivalence between the two notions of rationalizability in a specific case.     

On real economic freedom

Among the various concepts of freedom important for economics, ranking or measuring the freedom of choice provided by budget sets has an important place. The volume ranking has strange properties and cannot be justified by unit invariance and symmetry. The pointed distance (of the budget hyperplane from the origin along some line) provides a measure or ranking that coincides with the standard “purchasing power” or real income. The linear price index is practically unavoidable for measuring or ranking freedom. This is applied to the determination of income distribution and taxation implied by the equal freedom of choice of different domains. Concepts of equal or compared potential freedoms and utility-freedom relate freedom analysis to the basic classical concepts of fair allocation (equity-no-envy, egalitarian equivalence, etc.). The crucial difference between the two opposite concepts of invariance in comparisons is emphasized.     

Factors affecting the structure of horticulture in the Vale of Evesham,U.K.: a behavioural interpretation

Horticulture in the Vale of Evesham is examined in relation to a set of grower and structural characteristics. Adopting a behavioural perspective, the relative importance of decision-making factors is assessed. Whilst physical factors dominate the ranking, socio-personal factors came first and third, with experience and such personal values as independence and doing the work you like influencing the decision behaviour of the horticulturists. The average ranking of economic factors reflects the problems facing the industry today. The importance of satisfaction is demonstrated and attention is drawn to the role of ‘opportunity cost’ and ‘social inertia’ in preventing a more rapid rate of decline.     

Unlikelihood of Condorcet’s paradox in a large society

We provide intuitive, formal, and computational evidence that in a large society Condorcet’s paradox (the intransitivity of social preference obtained by pairwise vote) can hardly occur. For that purpose, we compare two models of social choice, one based on voting and another one based on summing individual cardinal utilities, expressed either in reals, or integers. We show that in a probabilistic model with a large number of independent individuals both models, almost surely, provide the same decision results. This implies that Condorcet’s and Borda’s methods tend to give the same decisions as the number of voters increases. Therefore, in the model with a large number of voters, the transitivity of the Borda preference is inherent in a majority preference as well. Received: 26 June 1998/Accepted: 16 April 1999     

Unequivocal majority and Maskin-monotonicity

The unequivocal majority of a social choice rule is a number of agents such that whenever at least this many agents agree on the top alternative, then this alternative (and only this) is chosen. The smaller the unequivocal majority is, the closer it is to the standard (and accepted) majority concept. The question is how small can the unequivocal majority be and still permit the Nash-implementability of the social choice rule; i.e., its Maskin-monotonicity. We show that the smallest unequivocal majority compatible with Maskin-monotonicity is n- ë \fracn-1m û{n-\left\lfloor \frac{n-1}{m} \right\rfloor} , where n ≥ 3 is the number of agents and m ≥ 3 is the number of alternatives. This value is equal to the minimal number required for a majority to ensure the non-existence of cycles in pairwise comparisons. Our result has a twofold implication: (1) there is no Condorcet consistent social choice rule satisfying Maskin-monotonicity and (2) a social choice rule satisfies k-Condorcet consistency and Maskin-monotonicity if and only if k 3 n- ë \fracn-1m û{k\geq n-\left\lfloor \frac{n-1}{m}\right\rfloor}.     

Rationalizability of choice functions on general domains without full transitivity

The rationalizability of a choice function by means of a transitive relation has been analyzed thoroughly in the literature. However, not much seems to be known when transitivity is weakened to quasi-transitivity or acyclicity. Such weakenings are particularly relevant in the context of social choice. We describe the logical relationships between the different notions of rationalizability involving, for example, the transitivity, quasi-transitivity, or acyclicity of the rationalizing relation. Furthermore, we discuss sufficient conditions and necessary conditions for rational choice on arbitrary domains. Transitive, quasi-transitive, and acyclical rationalizability are fully characterized for domains that contain all singletons and all two-element subsets of the universal set.