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.     

Choosing the level of a public good when agents have an outside option

The work examines strategy-proof social choice functions which select a level or the location of a public good when its consumption is not compulsory. We assume that agents have single-peaked preferences on the consumption of the public good as well as a reservation utility. Agents opt out of the good whenever they get a utility smaller than their reservation utility. We characterize strategy-proof and efficient social choice functions as well as the ones which are anonymous and group strategy-proof. Finally, we observe that for given preferences a Condorcet winner may not exist.This article constitutes the first chapter of my Ph.D. dissertation at Universitat Autònoma de Barcelona. I wish to thank especially Jordi Massó for supervising my research, Dolors Berga and Matthew Jackson. I also thank José Alcalde, Salvador Barberà, Carmen Beviá, Jeremy Heald, Hervé Moulin, Antonio Romero-Medina and an anonymous referee for their comments and suggestions. The European Commission is gratefully acknowledged for its financial support through the T.M.R. fellowship ERBFMICT960619.     

Generalized median social welfare functions

The article considers the construction of social welfare functions when the set of alternatives is the two-dimensional nonnegative orthant, as would be the case if there are two divisible public goods which can be consumed in any nonnegative quantities. With individual and social preferences required to be linear and strictly monotonic, but otherwise unrestricted, we characterize all of the social welfare functions which satisfy binary independence of irrelevant alternatives and anonymity and which satisfy binary independence of irrelevant alternatives, anonymity, and weak Pareto. These classes of social welfare functions are shown to be formally equivalent to the classes of social choice functions characterized by Moulin in his study of strategy-proof social choice with single-peaked preferences.We are grateful to Charles Blackorby, Hervé Moulin, and an anonymous referee for their comments.     

A systematic approach to the construction of non-empty choice sets

Suppose a strict preference relation fails to possess maximal elements, so that a choice is not clearly defined. I propose to delete particular instances of strict preferences until the resulting relation satisfies one of a number of known regularity properties (transitivity, acyclicity, or negative transitivity), and to unify the choices generated by different orders of deletion. Removal of strict preferences until the subrelation is transitive yields a new solution with close connections to the “uncovered set” from the political science literature and the literature on tournaments. Weakening transitivity to acyclicity yields a new solution nested between the strong and weak top cycle sets. When the original preference relation admits no indifferences, this solution coincides with the familiar top cycle set. The set of alternatives generated by the restriction of negative transitivity is equivalent to the weak top cycle set.     

Fuzzy choice functions

The R-greatest and maximal sets of standard choice theory are extended to fuzzy R-greatest and fuzzy maximal sets. Unlike the precise counterparts of these concepts, these two sets do not in general coincide when preferences are reflexive and connected. A stronger than usual version of connectedness under which the two sets are equal is provided. The concept of a fuzzy choice function is introduced and conditions under which a fuzzy choice function may be rationalized as a fuzzy R-greatest or a fuzzy maximal set are discussed. Rationalizability with transitive and weakly transitive fuzzy preference relations is also considered.We are indebted to Professor P. K. Pattanaik for his comments on an earlier version of this paper. We also wish to acknowledge comments made by an anonymous referee from which this paper has benefited greatly. The usual caveat about errors applies.     

On the generic emptiness of the local core of voting games

The local core of voting games is investigated from a genericity point of view. There exist preference profiles for which it is empty and there exist preference profiles for which the local core and its complement are both dense in the set of alternatives. Furthermore the subset of profiles having an empty local core is dense in the whole set of profiles. Some remarks on the choice of the topology are provided.We are grateful to the French Commissariat Général du Plan for financial support and to Norman Schofield for having the opportunity to read McKelvey and Schofield (1986) before the publication. We are indebted to two anonymous referees for helpful suggestions and to Jerry Kelly for important comments and for correcting our English.     

A characterization of strategy-proof social choice functions for economies with pure public goods

We characterize strategy-proof social choice functions when individuals have strictly quasi-concave, continuous and satiated utility functions on convex subsets of IR ^m , representing preferences for the provision of m pure public goods. When specialized to the case m=1, these assumptions amount to requiring that preferences are single peaked, and for such a domain there exists a wide class of strategy-proof social choice functions. These were studied by Moulin (1980) under strong additional assumptions. Our first results characterize the complete class, after an appropriate extension of the single-peakedness condition. The new characterization retains the flavour of Moulin's elegant representation theorem. For the general m-dimensional case, previous results have shown that there is no efficient, strategy-proof, nondictatorial social choice function, even within the domain restrictions under consideration (Border and Jordan 1983; Zhou 1991). In fact, Zhou's powerful result indicates that nondictatorial strategy-proof s.c.f.'s will have a range of dimension one. This allows us to conclude with a complete characterization of all strategy-proof s.c.f.'s on IR ^m , because restrictions of preferences from our admissible class to one dimensional subsets satisfy the slightly generalized notion of single-peakedness that is used in our characterization for the case m=1. We feel that a complete knowledge of the class of strategy-proof mechanisms, in this as well as in other contexts, is an important step in the analysis of the trade-offs between strategy-proofness and other performance criteria, like efficiency.This paper was written while both authors were visiting GREMAQ, Université des Sciences Sociales de Toulouse. We are thankful for its hospitality and good research atmosphere. Barberà's work is supported by the Instituto de Estudios Fiscales and by research grant PB89-0294 from the Secretaría de Estado de Universidades e Investigación, Spain. Jackson acknowledges the support of NSF grant SES8921409. We thank Jacques Crémer, Beth Allen, John Weymark and two anonymous referees for helpful comments on earlier drafts.     

A new old solution for weak tournaments

This article uncovers dynamic properties of the von Neumann–Morgenstern solution in weak tournaments and majoritarian games. We propose a new procedure for the construction of choice sets from weak tournaments, based on dynamic stability criteria. The idea is to analyze dynamic versions of tournament games. The exploration of a specific class of Markov perfect equilibria in these “dynamic tournament games” yields a new solution concept for weak tournaments—the A-stable set. The alternatives in an A-stable set constitute persistent, long-run policy outcomes in the corresponding dynamic tournament games. We find that, in any weak tournament, the class of A-stable sets coincides with that of von Neumann–Morgenstern stable sets.     

Factorization of fuzzy preferences

In the ordinary framework, the factorization of a weak preference relation into a strict preference relation and an indifference relation is unique. However, in fuzzy set theory, the intersection and the union of fuzzy sets can be represented different ways. Furthermore, some equivalent properties in the ordinary case have generalizations in the fuzzy framework that may be not equivalent. For these reasons there exist in the literature several factorizations of a fuzzy weak preference relation. In this paper we obtain and characterize different factorizations of fuzzy weak preference relations by means of two courses of action which are equivalent in the ordinary framework: axioms and definitions of strict preference and indifference.This work is partially financed by the Junta de Castilla y León (Consejería de Educación y Cultura, Proyecto VA057/02), Ministerio de Ciencia y Tecnología, Plan Nacional de Investigación, Desarrollo e Innovación Tecnológica (I+D+I) (Proyecto BEC2001-2253) and ERDF. I am indebted to José Luis García-Lapresta and an anonymous referee for his helpful comments.     

A PRIMER ON CARDINAL VERSUS ORDINAL TOURNAMENTS

This paper fills in a gap in the tournament literature by developing a framework that can be used to analyze both cardinal and ordinal tournaments, as well as piece rates. The analysis aims to obtain a Pareto ranking of cardinal versus ordinal tournaments, which is an open question in the literature. The analysis shows that, surprisingly, cardinal tournaments are superior to ordinal tournaments. The rationale is that, by utilizing all the available information more efficiently, cardinal tournaments allow the principal to implement higher power incentives, which makes them superior even though they restrict the form of the contract more than ordinal tournaments. (JEL D82, D21)     

Composition-consistent tournament solutions and social choice functions

This paper introduces a new axiom for choice in preference profiles and tournaments, called composition-consistency. A social choice function is composition-consistent if it is non-sensitive to the cloning of one or several outcomes. The key feature of the composition consistency property is an operation concept called multiple composition product of profiles. The paper provides a brief overview of some social choice functions studied in the literature. Concerning the tournament solutions, it is proved that the Top Cycle, the Slater and the Copeland solutions are not composition-consistent, whereas the Banks, Uncovered Set, TEQ, Minimal Covering Set are composition-consistent. Moreover, we define the composition-consistent hull of a solution as the smallest composition-consistent solution containing . The composition-consistent hulls of the Top cycle and Copeland solutions are specified, and we give some hints about the location of the hull of the Slater set. Concerning social choice functions, it is shown that Kemeny, Borda and Minimax social choice functions are not composition-consistent, whereas the Paretian one is composition-consistent. Moreover, we prove that the latter is the composition-consistent hull of the Borda and Minimax functions.     

Acyclic sets of linear orders via the Bruhat orders

We describe Abello’s acyclic sets of linear orders [SIAM J Discr Math 4(1):1–16, 1991] as the permutations visited by commuting equivalence classes of maximal reduced decompositions. This allows us to strengthen Abello’s structural result: we show that acyclic sets arising from this construction are distributive sublattices of the weak Bruhat order. This, in turn, shows that Abello’s acyclic sets are, in fact, the same as Chameni-Nembua’s distributive covering sublattices (S.T.D.C s). Fishburn’s alternating scheme is shown to be a special case of the Abello/Chameni-Nembua acyclic sets. Any acyclic set that arises in this way can be represented by an arrangement of pseudolines, and we use this representation to derive a simple closed form for the cardinality of the alternating scheme. The higher Bruhat orders prove to be a natural mathematical framework for this approach to the acyclic sets problem. We would like to thank the Editor, Professor Bernard Monjardet, and two anonymous referees for their comments and additional references.     

Comparison functions and choice correspondences

In this paper, we introduce the concept of a comparison function, which is a mapping g that assigns numbers to ordered pairs of alternatives (x,y) with the property that g(x,y)=−g(y,x). The paper discusses how some well-known choice correspondences on tournaments such as the uncovered set, the minimal covering set and the bipartisan set can be extended to this general framework. Axiomatic characterizations and properties are studied for these correspondences. Received: 4 November 1996/Accepted: 13 April 1998     

Arrow’s Axiom and Full Rationality for Fuzzy Choice Functions

A classical result for crisp choice functions shows the equivalence between Arrow axiom and the property of full rationality. In this paper we study a fuzzy form of Arrow axiom formulated in terms of the subsethood degree and of the degree of equality (of fuzzy sets). We prove that a fuzzy choice function satisfies Fuzzy Arrow Axiom if and only if it is (fuzzy) full rational. We also show that these conditions are also equivalent with weak and strong fuzzy congruence axioms WFCA and SFCA. It is studied the Arrow index, a new concept that indicates the degree to which a fuzzy choice function satisfies the Fuzzy Arrow Axiom. The author wishes to express her gratitude to the two anonymous reviewers for their valuable comments and discussions that contributed to a higher quality of the paper. Some of their comments can be found in the final version of the paper. An abstract of this paper was presented at the First Spain Italy Netherlands Meeting on Game Theory SING, Maastricht, The Netherlands, June 2005.     

Reference functions and possibility theorems for cardinal social choice problems

 In this paper, we provide axiomatic foundations for social choice rules on a domain of convex and comprehensive social choice problems when agents have cardinal utility functions. We translate the axioms of three well known approaches in bargaining theory (Nash 1950; Kalai and Smorodinsky 1975; Kalai 1977) to the domain of social choice problems and provide an impossibility result for each. We then introduce the concept of a reference function which, for each social choice set, selects a point from which relative gains are measured. By restricting the invariance and comparison axioms so that they only apply to sets with the same reference point, we obtain characterizations of social choice rules that are natural analogues of the bargaining theory solutions. Received: 8 August 1994/Accepted: 12 February 1996     

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     

Is a continuous rational social aggregation impossible on continuum spaces?

This paper provides a global topological setting for the social choice theory on continuum spaces of alternatives, in contrast to the local differentiable setting of Chichilnisky. Chichilnisky proved that a rational continuous social choice must be discontinuous in her setting. Our paper revisits her theorem to trace the source of this discontinuity. We find that the discontinuity is irrelevant to social aggregation, per se. The main theorem states that there exist a number of continuous social utility maps which are anonymous and satisfy the Pareto condition. As a corollary, we show that there exist corresponding continuous social welfare functions, if singularity is not separated from regular preferences in social preference topology. This extends the possibility result of Jonnes-Zhang-Simpson on linear preferences, to the general ones. The notion of singularity of preferences, relative to the given mathematical structure of an alternative space, is carefully studied.     

Implementation of allocation rules under perfect information

We study subgame perfect implementation through perfect information mechanisms in economic environments. We assume that worst bundles exist for each agent and can be assigned to them independently of the bundle assigned to at least one other agent. We restrict our attention to allocation rules that are anonymous, efficient on their own range, single-valued in welfare, and that induce agents' participation. We define a class of mechanisms, which satisfy properties of minimal path length and finiteness of message dimensions. We characterize the class of allocation rules which can be implemented through those mechanisms.I would like to thank Bhaskar Dutta, Louis Gevers, Matthew Jackson, Ozgur Kibris, Hervé Moulin and Arunava Sen for stimulating discussions, seminar participants at Université de Montréal (the Axiomatic Theory of Resource Allocation meeting, May 1996), Universitat Autonoma de Barcelona, Universitad Carlos III de Madrid and Université de Paris Dauphine for their comments, and Frédéric Gaspart, Tarik Kara, James Schummer, William Thomson and an anonymous referee for extremely useful comments and suggestions on earlier versions.     

Mixed refinements of Shapley's saddles and weak tournaments

We investigate refinements of two solutions, the saddle and the weak saddle, defined by Shapley (1964) for two-player zero-sum games. Applied to weak tournaments, the first refinement, the mixed saddle, is unique and gives us a new solution, generally lying between the GETCHA and GOTCHA sets of Schwartz (1972, 1986). In the absence of ties, all three solutions reduce to the usual top cycle set. The second refinement, the weak mixed saddle, is not generally unique, but, in the absence of ties, it is unique and coincides with the minimal covering set. Received: 14 August 1998/Accepted: 12 November 1999     

Egalitarian-equivalence and the Pareto principle for social preferences

The Pareto principle is often in conflict with the equity criteria in construction of social preferences: there exist two allocations x and y such that x Pareto dominates y, but y is an equitable allocation whereas x is not. The efficiency-first principle requires to rank an allocation x higher than y if (i) x Pareto dominates y or (ii) x and y are Pareto-noncomparable and x is equitable whereas y is not. The equity-first principle reverses the order of application of the two criteria. Adopting egalitarian-equivalence as the notion of equity, we examine rationality of the social preference functions based on the efficiency-first or the equity-first principle. The degrees of rationality vary widely depending on which principle is adopted, and depending on the range of egalitarian-reference bundles. We show several impossibility and possibility results as well as a characterization of the social preference function introduced by Pazner and Schmeidler (1978). We also identify the sets of maximal elements of the social preference relations in the set of feasible allocations. The results are contrasted with those in the case where no-envy is the notion of equity.This paper is a much extended version of a part of Tadenuma (1998). The author is grateful to Marc Fleurbaey, Serge-Chiristophe Kolm, Kotaro Suzumura, and William Thomson for helpful comments on the earlier version of the paper. ‘‘Financial support from the Ministry of Education, Culture, Sports, Science and Technology of Japan for the 21st Century Center of Excellence Project on the Normative Evaluation and Social Choice of Contemporary Economic Systems is gratefully acknowledged’’.