On the representation of preference orders on sequence spaces

A set of sufficient conditions for representability of preference orders on real sequence spaces is analyzed. In particular, monotonicity and continuity of the order is not assumed. Two applications are worked out to demonstrate how such a result might be useful.     

General concepts of value restriction and preference majority

Regenwetter and Grofman [17] offer a probabilistic generalization of Sen's [25, 27] classic value restriction condition when individual preferences are linear orders. They provide necessary and sufficient conditions for transitive majority preferences on linear orders. They call these conditions net value restriction and net preference majority. We study parallel generalizations for general binary relations. In general, neither net value restriction nor net preference majority is necessary for transitive majority preferences. Net value restriction is sufficient for transitive strict majority preferences, but not sufficient for transitive weak majority preferences. Net majority is sufficient for transitive majorities only if the preference relation with a net majority is a weak order. An application of our results to four U.S. National Election Study data sets reveals, in each case, transitive majorities despite a violation of Sen's original value restriction condition. We thank the National Science Foundation for funding this collaborative research through NSF grants SBR 97-30076 to Regenwetter and SBR 97-30578 to Grofman and Marley. We are indebted to the Interuniversity Consortium for Political and Social Research (ICPSR) for access to the 1968, 1980, 1992 and 1996 U.S. National Election Study (NES) data. We thank Mark Berger for helping us with the necessary data extraction. We are grateful to the action editor and the referees for extensive and helpful comments. Most of this work was carried out while the first author was a faculty member at the Fuqua School of Business, Duke University, which has generously supported our collaboration. Marley was a fellow at the Hanse-Wissenschaftskolleg, Germany, during the paper's completion.     

A necessary and sufficient condition for stable matching rules to be strategy-proof

We study one-to-one matching problems and analyze conditions on preference domains that admit the existence of stable and strategy-proof rules. In this context, when a preference domain is unrestricted, it is known that no stable rule is strategy-proof. We introduce the notion of the no-detour condition, and show that under this condition, there is a stable and group strategy-proof rule. In addition, we show that when the men’s preference domain is unrestricted, the no-detour condition is also a necessary condition for the existence of stable and strategy-proof rules. As a result, under the assumption that the men’s preference domain is unrestricted, the following three statements are equivalent: (i) a preference domain satisfies the no-detour condition, (ii) there is a stable and group strategy-proof rule, (iii) there is a stable and strategy-proof rule.     

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.     

Path independent choice and the ranking of opportunity sets

The indirect utility principle provides an instrumentalist basis for ranking opportunity sets, given an underlying preference ranking on alternatives. Opportunity set A is weakly preferred to B if A includes at least one preference-maximising element from $A\cup B$ . We introduce the Plott consistency principle as a natural extension of this logic to decision-makers who choose amongst alternatives according to a path independent choice function. Such choice functions need not be rationalisable by a preference order. Plott consistency requires that A is an acceptable choice from $\left\{ A, B\right\} $ if A includes at least one element from the set of acceptable choices from $A\cup B$ . We explore necessary and sufficient conditions (imposed on a choice function defined on collections of opportunity sets) for Plott consistency.     

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.     

A characterization of the single-peaked domain

We provide in this paper two properties that are both necessary and sufficient to characterize the domain of single-peaked preference profiles. This characterization allows for a definition of single-peaked preference profiles without using an ad hoc underlying order of the alternatives and also sheds light on the structure of single-peaked profiles. Considering the larger domain of value-restricted preference profiles (Sen, Econometrica 34:491–499, 1966) we also provide necessary and sufficient conditions for a preference profile to be single-caved or group-separable. Our results show that for single-peaked, single-caved and group-separable profiles it is sufficient to restrict to profiles containing of either three individuals and three alternatives or two individuals and four alternatives.     

Dominant strategy implementation with a convex product space of valuations

A necessary and sufficient condition for dominant strategy implementability when preferences are quasilinear is that, for every individual i and every choice of the types of the other individuals, all k-cycles in i’s allocation graph have nonnegative length for every integer k ≥ 2. Saks and Yu (Proceedings of the 6th ACM conference on electronic commerce (EC’05), pp 286–293, 2005) have shown that when the number of outcomes is finite and i’s valuation type space is convex, nonnegativity of the length of all 2-cycles is sufficient for the nonnegativity of the length of all k-cycles. In this article, it is shown that if each individual’s valuation type space is a full-dimensional convex product space and a mild domain regularity condition is satisfied, then (i) the nonnegativity of all 2-cycles implies that all k-cycles have zero length and (ii) all 2-cycles having zero length is necessary and sufficient for dominant strategy implementability.     

On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets

We consider two-sided many-to-many matching markets in which each worker may work for multiple firms and each firm may hire multiple workers. We study individual and group manipulations in centralized markets that employ (pairwise) stable mechanisms and that require participants to submit rank order lists of agents on the other side of the market. We are interested in simple preference manipulations that have been reported and studied in empirical and theoretical work: truncation strategies, which are the lists obtained by removing a tail of least preferred partners from a preference list, and the more general dropping strategies, which are the lists obtained by only removing partners from a preference list (i.e., no reshuffling). We study when truncation/dropping strategies are exhaustive for a group of agents on the same side of the market, i.e., when each match resulting from preference manipulations can be replicated or improved upon by some truncation/dropping strategies. We prove that for each stable mechanism, dropping strategies are exhaustive for each group of agents on the same side of the market (Theorem 1), i.e., independently of the quotas. Then, we show that for each stable mechanism, truncation strategies are exhaustive for each agent with quota 1 (Theorem 2). Finally, we show that this result cannot be extended neither to individual manipulations when the agent’s quota is larger than 1 (even when all other agents’ quotas equal 1—Example 1), nor to group manipulations (even when all quotas equal 1—Example 2).     

The relation between monotonicity and strategy-proofness

The Muller–Satterthwaite Theorem (J Econ Theory 14:412–418, 1977) establishes the equivalence between Maskin monotonicity and strategy-proofness, two cornerstone conditions for the decentralization of social choice rules. We consider a general model that covers public goods economies as in Muller–Satterthwaite (J Econ Theory 14:412–418, 1977) as well as private goods economies. For private goods economies, we use a weaker condition than Maskin monotonicity that we call unilateral monotonicity. We introduce two easy-to-check preference domain conditions which separately guarantee that (i) unilateral/Maskin monotonicity implies strategy-proofness (Theorem 1) and (ii) strategy-proofness implies unilateral/Maskin monotonicity (Theorem 2). We introduce and discuss various classical single-peaked preference domains and show which of the domain conditions they satisfy (see Propositions 1 and 2 and an overview in Table 1). As a by-product of our analysis, we obtain some extensions of the Muller–Satterthwaite Theorem as summarized in Theorem 3. We also discuss some new “Muller–Satterthwaite preference domains” (e.g., Proposition 3).     

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.     

A robust theory of resource allocation

The theory of social choice introduced in [5, 6] is robust: it is completely independent of the choice of topology on spaces of preferences. This theory has been fruitful in linking diverse forms of resource allocation: it has been shown [17] that contractibility is necessary and sufficient for solving the social choice paradox; this condition is equivalent [11] to another — limited arbitrage — which is necessary and sufficient for the existence of a competitive equilibrium and the core of an economy [13, 14, 15, 16, 17]. The space of monotone preferences is contractible; as shown already in [6, 17] such spaces admit social choice rules. However, monotone preferences are of little interest in social choice theory because the essence of the social choice problem, such as Condorcet triples, rules out monotonicity.The author is Director, Program on Information and Resources, and Professor of Economics, Columbia University. 1994-5 Salinbemi Professor, University of Siena, Italy. Research support from NSF grants Nos. 92 16928 and from the Leif Johansen Award at the University of Oslo, Norway, are gratefully acknowledged.     

On the multi-preference approach to evaluating opportunities

The purpose of the paper is to provide a general framework for analyzing “preference for opportunities.” Based on two simple axioms a fundamental result due to Kreps is used in order to represent rankings of opportunity sets in terms of multiple preferences. The paper provides several refinements of the basic representation theorem. In particular, a condition of “closedness under compromise” is suggested in order to distinguish the flexibility interpretation of the model from normative interpretations which play a crucial role in justifying the intrinsic value of opportunities. Moreover, the paper clarifies the link between the multiple preference approach and the “choice function” approach to evaluating opportunities. In particular, it is shown how the well-known Aizerman/Malishevski result on rationalizability of choice functions can be obtained as a corollary from the more general multiple preference representation of a ranking of opportunity sets. Received: 3 September 1996 / Accepted: 18 August 1997     

On the manipulability of approval voting and related scoring rules

We characterize all preference profiles at which the approval (voting) rule is manipulable, under three extensions of preferences to sets of candidates: by comparison of worst candidates, best candidates, or by comparison based on stochastic dominance. We perform a similar exercise for k-approval rules, where voters approve of a fixed number k of candidates. These results can be used to compare (k-)approval rules with respect to their manipulability. Analytical results are obtained for the case of two voters, specifically, the values of k for which the k-approval rule is minimally manipulable—has the smallest number of manipulable preference profiles—under the various preference extensions are determined. For the number of voters going to infinity, an asymptotic result is that the k-approval rule with k around half the number of candidates is minimally manipulable among all scoring rules. Further results are obtained by simulation and indicate that k-approval rules may improve on the approval rule as far as manipulability is concerned.     

Implementation in generic environments

In this paper, we study implementation in “economic environments”. It is shown that there is a dense subset of the set of preference profiles such that given an arbitrary social choice function, f, and ε>0, there exists another social choice function, f _ε, within ε of f uniformly and implementable in Nash equilibrium on the dense subset.     

On the core of characteristic function games associated with exchange networks

An exchange network is a social system in which the actors gain valued resources from bilateral transactions, but an opportunity to negotiate a deal is given only to those pairs of actors whose positions are tied with each other in a fixed communication network. A transaction consists in a mutually agreed-on division of a resource pool assigned to a network line. An additional constraint imposed on such a network restricts the range of transaction sets which may happen in a single negotiation round to those consistent with a given “exchange regime.” Under the one-exchange regime every actor is permitted to make no more than one deal per round. Bienenstock and Bonacich [Bienenstock, E.J., Bonacich, P., 1992. The core as a solution to exclusionary networks. Social Networks 14, 231–243] proposed to represent a one-exchange network with an n-person game in characteristic function form. The aim of this paper is to develop a mathematical theory of games associated with homogenous one-exchange networks (network homogeneity means that all lines are assigned resource pools of the same size). The focus is on the core, the type of solution considered most important in game theory. In particular, all earlier results obtained by Bonacich are re-examined and there is given a new graph-theoretic necessary and sufficient condition for the existence of nonempty core for the game representing a homogenous one-exchange network.     

Choice functions over a finite set: A summary

A choice function picks some outcome(s) from every issue (subset of a fixed set A of outcomes). When is this function derived from one preference relation on A (the choice set being then made up of the best preferred outcomes within the issue), or from several preference relations (the choice set being then the Pareto optimal outcome within the issue, or the union of the best preferred outcomes for each preference relation)? A complete and unified treatment of these problems is given based on three functional properties of the choice function. None of the main results is original.     

Dictatorial domains in preference aggregation

We call a domain of preference orderings “dictatorial” if there exists no Arrovian (Pareto optimal, IIA and non-dictatorial) social welfare function defined over that domain. In a finite world of alternatives where indifferences are ruled out, we identify a condition which implies the dictatoriality of a domain. This condition, to which we refer as “being essentially saturated”, is fairly weak. In fact, independent of the number of alternatives, there exists an essentially saturated (hence dictatorial) domain which consists of precisely six orderings. Moreover, this domain exhibits the superdictatoriality property, i.e., every superdomain of it is also dictatorial. Thus, given m alternatives, the ratio of the size of a superdictatorial domain to the size of the full domain may be as small as 6/m!, converging to zero as m increases.     

Popular support for social evaluation functions

This paper provides sufficient conditions under which the preferences of a social decision maker accord with majority voting. We show that an additive and monotone utilitarian social evaluation function is consistent with the outcomes of majority voting for the class of income distributions that are symmetric under a strictly increasing transformation. An example is the lognormal distribution. The required symmetry condition is generally accepted employing panel data for 116 countries from the World Bank’s POVCAL database.In this manner, the proposed methodology provides the consistent degree of inequality aversion and shows that median income is a good proxy for welfare.