Choice under complete uncertainty: axiomatic characterizations of some decision rules

Summary. We provide characterizations of four new rules for individual decision-making under complete uncertainty. They are what we call the min-max rule, the max-min rule, the lexicographic min-max rule and the lexicographic max-min rule. These rules provide orderings of the sets of possible outcomes associated with uncertain prospects. They provide significant alternatives to commonly-used rules that focus on worst outcomes or best outcomes only, and lexicographic versions of those rules. Received: August 20, 1998; revised version: November 3, 1999     

Evolutionary stability and lexicographic preferences

We explore the interaction between evolutionary stability and lexicographic preferences. To do so, we define a limit Nash equilibrium for a lexicographic game as the limit of Nash equilibria of nearby games with continuous preferences. Nash equilibria of lexicographic games are limit Nash equilibria, but not conversely. Modified evolutionarily stable strategies (Binmore and Samuelson, 1992. J. Econ. Theory 57, 278–305) are limit Nash equilibria. Modified evolutionary stability differs from “lexicographic evolutionarily stability” (defined by extending the common characterization of evolutionary stability to lexicographic preferences) in the order in which limits in the payoff space and the space of invasion barriers are taken.     

A general impossibility result on strategy-proof social choice hyperfunctions

A social choice hyperfunction picks a non-empty set of alternatives at each admissible preference profile over sets of alternatives. We analyze the manipulability of social choice hyperfunctions. We identify a domain D^λ of lexicographic orderings which exhibits an impossibility of the Gibbard–Satterthwaite type. Moreover, this impossibility is inherited by all well-known superdomains of D^λ. As most of the standard extension axioms induce superdomains of D^λ while social choice correspondences are particular social choice hyperfunctions, we are able to generalize many impossibility results in the literature.     

Symmetry and impartial lotteries

A prize is to be awarded, so each candidate designates one of his peers on a ballot. The ballots determine the lottery that selects the winner, and impartiality requires that no candidate's choice of designee impacts his own chance of winning, removing incentives for strategic ballot submission. The primary results are (1) a characterization of all impartial rules that treat agents symmetrically as voters, and (2) a characterization of all impartial rules that treat agents symmetrically as candidates. Each rule in either class may be represented as a randomization over a finite set of simple rules. These results have immediate interpretation in a second context: the division of surplus among team members. Corollaries include the constant rule impossibility of Holzman and Moulin (2013), a new dictatorship impossibility, and the first axiomatic characterization of uniform random dictatorship.     

A characterization of consistent collective choice rules

We characterize a class of collective choice rules such that collective preference relations are consistent. Consistency is a weakening of transitivity and a strengthening of acyclicity requiring that there be no cycles with at least one strict preference, which excludes the possibility of a “money pump.” The properties of collective choice rules used in our characterization are unrestricted domain, strong Pareto, anonymity and neutrality. If there are at most as many individuals as there are alternatives, the axioms provide an alternative characterization of the Pareto rule. If there are more individuals than alternatives, however, further rules become available.     

A non-cooperative interpretation of the f-just rules of bankruptcy problems

First, we propose an axiomatic characterization of the f-just rules. Second, based on the result, a game is designed and a non-cooperative interpretation of the f-just rules is provided.     

Ranking opportunity sets in a simple intertemporal framework

We extend the problem of ranking subsets (opportunity sets) of a set of alternatives to an intertemporal setting, whereby the agent makes a sequence of choice decisions over time. In particular, we show in a simple two-period model that an agent who satisfies five plausible axioms ranks opportunity sets in a lexicographic fashion. That is, the agent ranks opportunity sets based solely on the relative desirability of their first-period alternatives, and only if the first-period alternatives are thought equally desirable does the agent consider the second-period alternatives. We discuss this strong time-discounting result and the role of the axioms, and also show that the popular “independence” axioms employed in the existing “static” literature are inconsistent with some reasonable axioms regarding intertemporal choice.      

A CLASS OF PERFORMANCE‐BASED SUBSIDY RULES*

We consider a benchmark static incentive scheme, i.e. a per unit subsidy, that induces a monopoly to produce a target output level. We show that the same output level can be achieved by a continuum of dynamic subsidy rules based on a performance indicator. The rules require only local information. The present value of the subsidies paid is smaller than the amount paid under the static subsidy. Each of the dynamic subsidy rules results at each moment in a lower per unit subsidy than the static subsidy. The subsidy rate depends on a state variable that reflects the monopolist's performance history.     

Ex-post implementation and preference aggregation via potentials

We introduce several notions of potentials for mechanism design problems with interdependent values, and relate them to implementation in ex-post equilibrium. Whereas ex-post implementation is closely linked to the ordinal concept of best-alternative potentials, the celebrated Vickrey–Clarke–Groves mechanism corresponds to the stronger notion of a cardinal potential: agents agree not only on the best alternative, but also on the quantitative differences between all alternatives. We characterize all valuations that allow for cardinal potentials, and use this characterization for: (1) Identifying valuations for which ex-post implementation is possible; (2) Identifying classes of valuations for which all ex-post implementable choice rules correspond to cardinal potentials. The latter allows us to extend to interdependent valuations a result for dominant strategy implementation in private values settings, due to Roberts (The Characterization of Implementable Choice Rules, North-Holland, Amsterdam, 1979). We wish to thank an associate editor, two anonymous referees, Paul Milgrom and Burkhard Schipper for helpful comments and stimulating remarks.     

Enumeration of Nash equilibria for two-player games

This paper describes algorithms for finding all Nash equilibria of a two-player game in strategic form. We present two algorithms that extend earlier work. Our presentation is self-contained, and explains the two methods in a unified framework using faces of best-response polyhedra. The first method lrsnash is based on the known vertex enumeration program lrs, for “lexicographic reverse search”. It enumerates the vertices of only one best-response polytope, and the vertices of the complementary faces that correspond to these vertices (if they are not empty) in the other polytope. The second method is a modification of the known EEE algorithm, for “enumeration of extreme equilibria”. We also describe a second, as yet not implemented, variant that is space efficient. We discuss details of implementations of lrsnash and EEE, and report on computational experiments that compare the two algorithms, which show that both have their strengths and weaknesses.     

Stable lexicographic rules for shortest path games

For the class of shortest path games, we propose a family of new cost sharing rules satisfying core selection. These rules allocate shares according to some lexicographic preference relation. A computational procedure is provided. Our results relate to those of Tijs et al. (2011).     

Extensive Form Implementation in Incomplete Information Environments

We study the implementation of social choice rules in incomplete information environments. A sufficiency condition calledposterior reversalis given for extensive form implementation. The condition has a natural interpretation in signaling terms: Consistent posterior distributions under truth-telling are different from consistent posteriors under deception. This variation in the distribution over player types leads to variation in the distribution over actions and outcomes (comparing truth-telling and deception). We exploit this feature to implement social choice rules.Journal of Economic LiteratureClassification Numbers: D78, D82.     

The communication requirements of social choice rules and supporting budget sets

The paper examines the communication requirements of social choice rules when the (sincere) agents privately know their preferences. It shows that for a large class of choice rules, any minimally informative way to verify that a given alternative is in the choice rule is by verifying a “budget equilibrium”, i.e., that the alternative is optimal to each agent within a “budget set” given to him. Therefore, any communication mechanism realizing the choice rule must find a supporting budget equilibrium. We characterize the class of choice rules that have this property. Furthermore, for any rule from the class, we characterize the minimally informative messages (budget equilibria) verifying it. This characterization is used to identify the amount of communication needed to realize a choice rule, measured with the number of transmitted bits or real variables. Applications include efficiency in convex economies, exact or approximate surplus maximization in combinatorial auctions, the core in indivisible-good economies, and stable many-to-one matchings.     

Counting combinatorial choice rules

I count the number of combinatorial choice rules that satisfy certain properties: Kelso–Crawford substitutability, and independence of irrelevant alternatives. The results are important for two-sided matching theory, where agents are modeled by combinatorial choice rules with these properties. The rules are a small, and asymptotically vanishing, fraction of all choice rules. But they are still exponentially more than the preference relations over individual agents—which has positive implications for the Gale–Shapley algorithm of matching theory.     

FAIR ALLOCATION OF DISPUTED PROPERTIES

We model problems of allocating disputed properties as generalized exchange economies. Therein, agents have preferences and claims over multiple goods, and the social endowment of each good may not be sufficient to satisfy all individual claims. We focus on market‐based allocation rules that impose a two‐step procedure: assignment of rights based on claims first and voluntary exchange based on the assigned rights afterward. We characterize three focal egalitarian rights‐assignment rules that guarantee that the allocation rules are fair. We apply our results to problems of greenhouse gas emissions and contested water rights.     

Profit sharing in unique Nash equilibrium: Characterization in the two-agent case

Two agents jointly operate a decreasing marginal returns technology to produce a private good. We characterize the class of output-sharing rules for which the labor-supply game has a unique Nash equilibrium. It consists of two families: rules of the serial type which protect a small user from the negative externality imposed by a large user, and rules of the reverse serial type, where one agent effectively employs the other agent's labor. Exactly two rules satisfy symmetry; a result in sharp contrast with Moulin and Shenker's characterization of their serial mechanism as the unique cost-sharing rule satisfying the same incentives property [Moulin, H., Shenker, S., 1992. Serial cost sharing. Econometrica 60 (5), 1009–1037]. We also show that the familiar stand-alone test characterizes the class of fixed-path methods under our incentives criterion [Friedman, E.J., 2004. Strong monotonicity in surplus sharing. Econ. Theory 23, 643–658].     

Designer path independent choice functions

Summary. This paper provides an algorithm for the construction of all PICFs on a finite set of alternatives, V, designed by an a priori given set I of initial choices as well as the determination of whether the initial set I is consistent with path independence. The algorithm is based on a new characterization result for path independent choice functions (PICF) on finite domains and uses that characterization as the basis of the algorithm. The characterization result identifies two properties of a partition of the Boolean algebra as necessary and sufficient for a choice function C to be a PICF: (i): For every subset A of V the set is an interval in the Boolean algebra 2 ^V . (ii): If A/B is an interval in the Boolean algebra such that C(A) = C(B) and if M/N is an upper transpose of A/B then C(M) = C(N). The algorithm proceeds by expanding on the implications of these two properties.Received: 5 November 2003, Revised: 20 July 2004, JEL Classification Numbers: D00, D70.     

The most ordinally egalitarian of random voting rules

Aziz and Stursberg propose an “Egalitarian Simultaneous Reservation” rule (ESR), a generalization of Serial rule, one of the most discussed mechanisms in the random assignment problem, to the more general random social choice domain. This article provides an alternative definition, or characterization, of ESR as the unique most ordinally egalitarian one. Specifically, given a lottery p over alternatives, for each agent i the author considers the total probability share in p of objects from her first k indifference classes. ESR is shown to be the unique one which leximin maximizes the vector of all such shares (calculated for all i, k). Serial rule is known to be characterized by the same property. Thus, the author provides an alternative way to show that ESR, indeed, coincides with Serial rule on the assignment domain. Moreover, since both rules are defined as the unique most ordinally egalitarian ones, the result shows that ESR is “the right way” to think about generalizing Serial rule.     

The Choquet Bargaining Solutions

We axiomatically investigate the problem of rationalizing bargaining solutions by social welfare functions that are linear in every rank-ordered subset of Rⁿ₊ . Such functions, the so-called Choquet integrals, have been widely used in the theories of collective and individual choice. We refer to bargaining solutions that can be rationalized by Choquet integrals as Choquet bargaining solutions. Our main result is a complete characterization of Choquet bargaining solutions. As a corollary of our main result, we also obtain a characterization of the generalized Gini bargaining solutions introduced by Blackorby et al. (1994, Econometrica62, 1161–1178). Journal of Economic Literature Classification Numbers: D71, C78.     

A leximin characterization of strategy-proof and non-resolute social choice procedures

Summary. We characterize strategy-proof social choice procedures when choice sets need not be singletons. Sets are compared by leximin. For a strategy-proof rule g, there is a positive integer k such that either (i) the choice sets g(r) for all profiles r have the same cardinality k and there is an individual i such that g(r) is the set of alternatives that are the k highest ranking in i's preference ordering, or (ii) all sets of cardinality 1 to k are chosen and there is a coalition L of cardinality k such that g(r) is the union of the tops for the individuals in L. There do not exist any strategy-proof rules such that the choice sets are all of cardinality to k where . Received: November 8, 1999; revised version: September 18, 2001