Probabilistic assignment of objects: Characterizing the serial rule

We study the problem of assigning a set of objects to a set of agents, when each agent receives one object and has strict preferences over the objects. In the absence of monetary transfers, we focus on the probabilistic rules, which take the ordinal preferences as input. We characterize the serial rule, proposed by Bogomolnaia and Moulin (2001) [2]: it is the only rule satisfying sd efficiency, sd no-envy, and bounded invariance. A special representation of feasible assignment matrices by means of consumption processes is the key to the simple and intuitive proof of our main result.     

A solution to the random assignment problem on the full preference domain

We consider the problem of allocating a set of indivisible objects to agents in a fair and efficient manner. In a recent paper, Bogomolnaia and Moulin consider the case in which all agents have strict preferences, and propose the probabilistic serial (PS) mechanism; they define a new notion of efficiency, called ordinal efficiency, and prove that the probabilistic serial mechanism finds an envy-free ordinally efficient assignment. However, the restrictive assumption of strict preferences is critical to their algorithm. Our main contribution is an analogous algorithm for the full preference domain in which agents are allowed to be indifferent between objects. Our algorithm is based on a reinterpretation of the PS mechanism as an iterative algorithm to compute a “flow” in an associated network. In addition we show that on the full preference domain it is impossible for even a weak strategyproof mechanism to find a random assignment that is both ordinally efficient and envy-free.     

Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem

We study problems in which each of finitely many agents must be allocated a single object, based on the agents' rankings of pure outcomes. A random allocation is ordinally efficient if it is not ordinally dominated in the sense of there being another random assignment that gives each agent a first order stochastically dominant distribution of objects. We show that any ordinally efficient random assignment maximizes the sum of expected utilities for some vector of vNM utility functions that are consistent with the given ordinal preferences. One method of proof uses a new version of the separating hyperplane theorem for polyhedra. Journal of Economic Literature Classification Numbers: C78, D61.     

A simple random assignment problem with a unique solution

Summary. All agents have the same ordinal ranking over all objects, receiving no object (opting out) may be preferable to some objects, agents differ on which objects are worse than opting out, and the latter information is private. The Probabilistic Serial assignment, improves upon (in the Pareto sense) the Random Priority assignment, that randomly orders the agents and offers them successively the most valuable remaining object. We characterize Probabilistic Serial by efficiency in an ordinal sense, and envy-freeness. We characterize it also by ordinal efficiency, strategyproofness and equal treatment of equals. Received: October 5, 1999; revised version: December 20, 2000     

Ordinal efficiency and dominated sets of assignments

Using lotteries is a common tool for allocating indivisible goods. Since obtaining preferences over lotteries is often difficult, real-life mechanisms usually rely on ordinal preferences over deterministic outcomes. Bogomolnaia and Moulin (J. Econom. Theory 19 (2002) 623) show that the outcome of an ex post efficient mechanism may be stochastically dominated. They define a random assignment to be ordinally efficient if and only if it is not stochastically dominated. In this paper we investigate the relation between ex post efficiency and ordinal efficiency. We introduce a new notion of domination defined over sets of assignments and show that a lottery induces an ordinally efficient random assignment if and only if each subset of the full support of the lottery is undominated.     

Probabilistic representation of complexity

We introduce a framework to study individuals’ behavior in environments that are deterministic, but too complex to permit tractable deterministic representations. An agent in these environments uses a probabilistic model to cope with his inability to think through all contingencies in advance. We interpret this probabilistic model as embodying all patterns the agent perceives, yet allowing for the possibility that there may be important details he had missed. Although the implied behavior is rational, it is consistent with an agent who believes his environment is too complex to warrant precise planning, foregoes finely detailed contingent rules in favor of vaguer plans, and expresses a preference for flexibility.     

An alternative characterization of top trading cycles

This paper introduces two new characterizations of the top trading cycles algorithm. The key to our characterizations is a new condition, independence of irrelevant rankings (IIR). Intuitively, a mechanism satisfies IIR if whenever an agent’s ranking at an object is irrelevant to her assignment, then it is irrelevant to the assignment of all agents. We demonstrate that a mechanism is Pareto efficient, strategy-proof, IIR, and satisfies mutual best if and only if it is top trading cycles. This provides a new insight into what distinguishes top trading cycles from all other efficient and strategy-proof assignment mechanisms. We provide a second characterization in terms of weak Maskin monotonicity. A mechanism satisfies Pareto efficiency, weak Maskin monotonicity, IIR, and mutual best if and only if it is top trading cycles. This allows us to directly compare top trading cycles to known characterizations of the deferred acceptance algorithm in terms of weak Maskin monotonicity.     

The role of optimal threats in auction design

This paper studies revenue-maximizing auctions when buyers' outside options depend on their private information and are endogenously chosen by the seller. We show that the revenue-maximizing assignment of the object can depend crucially on the outside options that the seller can choose as threats. Depending on the shape of outside options, sometimes an optimal mechanism allocates the object in an ex-post efficient way, and, other times, buyers obtain the object more often than is efficient.     

An experimental examination into the design of decentralized methods to solve the assignment problem with and without money

Summary An experimental examination of the assignment problem, matching individuals to positions or slots, is conducted in which various assignment mechanisms are analyzed. Generalized versions of both the Vickrey and English auctions are designed to solve the assignment problem along with oridinal ranking mechanisms (serial dictator and funny money system). The generalized auctions result in efficient allocations. In contrast, the ordinal ranking mechanisms, which require no monetary transfers, are significantly less efficient in their assignments. However, the efficient allocations obtained from the competitive bidding processes are at the expense of consumers' surplus since demanders retain significantly larger profits with the ordinal ranking mechanisms.     

A simple and general solution to King Solomon''s problem

An indivisible object is to be allocated at no cost to the agent who values it most. We provide a simple two-stage mechanism, which implements the desired outcome when it is common knowledge that the agent who values the object most knows that. At each stage of the game, all players have weakly dominant strategies. Moreover, if the two highest valuations are common knowledge, the second stage of the game is redundant, and the outcome is implemented in weakly dominant strategies.     

Cardinal Bayesian allocation mechanisms without transfers

In allocating goods with no use of monetary transfers, random allocation mechanisms can be designed in order to elicit information on preference intensities. I study the nontransfer allocation of two ex-ante identical objects under Bayesian incentive compatibility, with symmetric agents and independent private valuations. I find the ex-ante utilitarian-optimal mechanism, in which the probability of receiving a specified object is used as “numeraire” to purchase probability units of the other object. I characterize this mechanism as an appropriate combination of lotteries, auctions and insurance. The latter element ensures that efficient auctions are feasible. If the problem is constrained to guarantee exactly one object per agent, then the optimal mechanism uses no information other than the agents? ordinal preferences.     

Efficient assignment respecting priorities

A widespread practice in assignment of heterogeneous indivisible objects is to prioritize some recipients over others depending on the type of the object. Leading examples include assignment of public school seats, and allocation of houses, courses, or offices. Each object comes with a coarse priority ranking over recipients. Respecting such priorities constrains the set of feasible assignments, and therefore might lead to inefficiency, highlighting a tension between respecting priorities and Pareto efficiency. Via an easily verifiable criterion, we fully characterize priority structures under which the constrained efficient assignments do not suffer from such welfare loss, and the constrained efficient rule (CER) is indeed efficient. We also identify the priority structures for which the CER is singleton-valued and group strategy-proof.     

STRATEGY PROOF AND PRIVACY PRESERVING FAIR ALLOCATION MECHANISM*

We study a fair division problem with indivisible objects such as jobs, houses and one divisible good like money. It is required that each agent be assigned with exactly one object and a certain amount of money. Agents are assumed to have quasi‐linear utilities in money but their reservation values over the objects are private information. A dynamic mechanism is proposed that induces all agents to act honestly rather than strategically and assigns the objects with money to agents efficiently and fairly; at the same time it achieves privacy protection for the agents.     

A New Solution to the Random Assignment Problem

A random assignment is ordinally efficient if it is not stochastically dominated with respect to individual preferences over sure objects. Ordinal efficiency implies (is implied by) ex post (ex ante) efficiency. A simple algorithm characterizes ordinally efficient assignments: our solution, probabilistic serial (PS), is a central element within their set. Random priority (RP) orders agents from the uniform distribution, then lets them choose successively their best remaining object. RP is ex post, but not always ordinally, efficient. PS is envy-free, RP is not; RP is strategy-proof, PS is not. Ordinal efficiency, Strategyproofness, and equal treatment of equals are incompatible. Journal of Economic Literature Classification Numbers: C78, D61, D63.     

Incomplete information and singleton cores in matching markets

We study ordinal Bayesian Nash equilibria of stable mechanisms in centralized matching markets under incomplete information. We show that truth-telling is an ordinal Bayesian Nash equilibrium of the revelation game induced by a common belief and a stable mechanism if and only if all the profiles in the support of the common belief have singleton cores. Our result matches the observations of Roth and Peranson [The redesign of the matching market for American physicians: some engineering aspects of economic design, Amer. Econ. Rev. 89 (1999) 748-780] in the National Resident Matching Program (NRMP) in the United States: (i) the cores of the profiles submitted to the clearinghouse are small and (ii) while truth-telling is not a dominant strategy most participants in the NRMP truthfully reveal their preferences.     

Dynamics of inductive inference in a unified framework

We present a model of inductive inference that includes, as special cases, Bayesian reasoning, case-based reasoning, and rule-based reasoning. This unified framework allows us to examine how the various modes of inductive inference can be combined and how their relative weights change endogenously. For example, we establish conditions under which an agent who does not know the structure of the data generating process will decrease, over the course of her reasoning, the weight of credence put on Bayesian vs. non-Bayesian reasoning. We illustrate circumstances under which probabilistic models are used until an unexpected outcome occurs, whereupon the agent resorts to more basic reasoning techniques, such as case-based and rule-based reasoning, until enough data are gathered to formulate a new probabilistic model.     

Serial dictatorship and Pareto optimality

In a deterministic allocation problem in which each agent is entitled to receive exactly one object, an allocation is Pareto optimal if and only if it is the outcome of a serial dictatorship. We extend the definition of serial dictatorship to settings in which some agents may be entitled to receive more than one object, and study the efficiency and uniqueness properties of the equilibrium allocations. We prove that subgame perfect equilibrium allocations of serial dictatorship games are not necessarily Pareto optimal; and generally not all Pareto optima can be implemented as subgame perfect equilibrium allocations of serial dictatorship games, except in the 2-agent separable preference case. Moreover, serial dictatorship games do not necessarily have unique subgame perfect equilibrium allocations, except in the 2-agent case, hence their outcomes are indeterminate and manipulable.     

α‐SERIAL MECHANISMS FOR THE PROVISION OF AN EXCLUDABLE PUBLIC GOOD

We present a new class of “α‐serial mechanisms” for the provision of an excludable public good. Those mechanisms have a similar structure to the serial mechanism, but may let the non‐consumers pay a positive cost. They inherit desirable properties such as anonymity, envy‐freeness, Maskin monotonicity, and population monotonicity from the serial mechanism. We calculate the “maximal efficiency loss” and “maximal manipulation” of α‐serial mechanisms and point out a trade‐off between these two properties.     

Measuring school segregation

Using only ordinal axioms, we characterize several multigroup school segregation indices: the Atkinson indices for the class of school districts with a given fixed number of ethnic groups and the Mutual Information index for the class of all districts. Properties of other school segregation indices are also discussed. In an empirical application, we document a weakening of the effect of ethnicity on school assignment from 1987/1988 to 2007/2008. We also show that segregation between districts within cities currently accounts for 33% of total segregation. Segregation between states, driven mainly by the distinct residential patterns of Hispanics, contributes another 32%.     

Serial cost sharing of excludable public goods: general cost functions

Summary. A group of individuals meet to share the cost and determine output allocations of a partial-excludable public good. We demonstrate that, for general cost functions and preferences that satisfy the Spence-Mirlees sorting condition, the serial cost-sharing formula (Moulin, 1994) has remarkable incentive properties. First, a direct economic mechanism that uses the serial formula is coalition strategy-proof, envy-free and satisfies the stand-alone property. Second, the serial mechanism involves partial exclusion, which is important for the reduction of the free-rider problem. Received: June 10, 1996; revised version; February 11, 1997