Competitive equilibrium in the random assignment problem

• Published date: 01 December 2017
• DOI: http://doi.org/10.1111/ijet.12135
• Date: 01 December 2017
• Author: Phuong Le

doi: 10.1111/ijet.12135

Competitive equilibrium in the random assignment problem

Phuong Le∗

This paper studies the problem of random assignment with fractional endowments. Fractional

endowments complicate matters because the assignment has to make an agent weakly better

off than his endowment. I first formulate an exchange economy that resembles the random

assignment problem and prove the existence of competitiveequilibrium in this economy. I then

propose a pseudo-market mechanism for the random assignment problem that is based on the

competitive equilibrium. This mechanism is individually rational, Pareto optimal and justified

envy-free but not incentive compatible.

Key wor ds random assignment, competitive equilibrium, mechanism design

JEL classification D50, D47

Accepted 15 June2016

1 Introduction

I consider the random assignment problem with fractional endowment, that is, how to probabilisti-

cally assign a number of objects to a number of agents in an efficient and fair manner while respecting

individual rationality constraints arising from fractional private endowments. My solution uses the

concept of competitive equilibrium, and is related to two prominent existing results on competitive

equilibrium in the assignment problem, as well as certain special settings in school choice.

When each agent only has strict preferences over deterministic assignments and owns a distinct

entire house, the assignment problem parallels the housing market model first analyzed by Shapley

and Scarf (1974). In this model the houses areconsidered indivisible, and, given prices, each agent uses

the market value of his house to buy his most preferred affordable house. A competitive equilibrium

consists of prices that clear the market and the associated allocation. Roth and Postlewaite (1977)

show that for the housing market a competitive equilibrium exists and is unique. The competitive

equilibrium allocation is ex post efficient, individually r ational and can be implemented truthfully

through the prominent TopTrading Cycles algorithm (Roth 1982).

In the environment where each agent has cardinal utility for each house and compares proba-

bilistic assignments through von Neumann–Morgenstern(vNM) expected utility and no agent owns

any house, Hylland and Zeckhauser (1979) propose the competitive equilibrium from equal incomes

(CEEI) solution. The houses are infinitely divisible and each allocation corresponds to a random

*Department of Economics, Stanford University,Beverly Hills, CA, USA. Email: lp3ides@gmail.com

I gratefully acknowledge the E. S. Shaw and B. F. Haley Fellowship from the Stanford Institute for Economic Policy

Research. I am grateful to Fuhito Kojima,Ilya Segal and par ticipants in the EconomicTheor y seminar for their helpful

comments on a version of this paper that was in my PhD dissertation at Stanford University. I thank two anonymous

referees for their suggestions on the paper’smot ivationand contributions to the literature.

International Journal of Economic Theory 13 (2017) 369–385 © IAET 369

Random assignment problem Phuong Le

assignment. The authors construct an economy in which, given prices, agents use an exogenous

strictly positive income to purchase a utility-maximizing probability distribution over the houses.

A competitive equilibrium consists of prices of the houses that clear the market, and the corre-

sponding allocation. The authors show that a competitive equilibrium always exists and proposethe

pseudo-market mechanism for the assignment problem as follows. First, elicit cardinal utilities of

the agents. Second, give agents the same incomes, simulate the market and computethe competitive

equilibrium. Their pseudo-market mechanism is ex ante efficient, envy-free, but not strategy-proof.

In my setting, the houses are also infinitely divisible, and each agent still evaluates random

assignments using his vNM expected utility, but the endowment structure is more general: each

agent can own probability shares of houses and there might be house shares not owned by any agent.

In my solution, I first distribute the unowned houses among the agents and set up an exchange

economy in which, given prices, agents use the market value of their endowments to purchase a

utility-maximizing probability distribution over the houses. A competitive equilibrium consists of

prices of the houses that clear the market, and the corresponding allocation. My main result is that,

given strictly positive endowments, a competitive equilibrium exists. If endowments are not strictly

positive, however,I can still guarantee the existence of an approximate competitive equilibrium.

My results generalize the existing ones on competitive equilibrium in the assignment problem,

with and without divisibility. In my environment, when the endowment structure is such that each

agent owns a distinct entire house, there exists a unique competitive allocation (with divisibility)

whose allocation is unique and coincides with that of the unique competitive allocation with indivis-

ibility. Whenno agent owns any house, the distribution of unowned houses e venlyamong the agents

is equivalent to giving agents equal incomes, so my existence result implies the existence of CEEI.

My results also allow for the design of a pseudo-market mechanism for the assignment problem

that accommodates endowment structures more general than those amenable to Top Trading Cycles

and CEEI. In the pseudo-market mechanism, I first elicit from the agents their cardinal utilities

over the houses. I then distribute the unowned houses evenly among the agents and compute the

competitive equilibrium. The resulting allocation will be ex ante efficient, individually rational and

justified envy-free. My pseudo-market mechanism improves upon that of Hylland and Zeckhauser

(1979) since it satisfies individual rationality constraints arising from private endowments, and

collapses to the CEEI outcome when there are no private endowments. It also improves upon Top

Trading Cycles by allowing for fractional private endowments, and collapses to the Top Trading

Cycles outcome when each agent owns a distinct entire house. However, the mechanism is not

strategy-proof.

The current paper is related to the literature on house allocation with existing tenants/private

endowments. Abdulkadiro˘

glu and S¨

onmez (1999) first study the house allocation problem with

existing tenants, a setting that captures the endowment structures in both Shapley and Scarf (1974)

(only existing tenants) and Hylland and Zeckhauser (1979) (only new applicants) as two polar cases.

The authors propose the top trading cycles mechanism from random orderings as a solution, and

show that this mechanism is efficient, individually rational and incentive compatible. Moreover,

this mechanism reduces to the competitive mechanism (based on top trading cycles) in the first

model, and to random serial dictatorship in the second model. While Abdulkadiro˘

glu and S¨

onmez

(1999) use the ex post notion of efficiency and individual rationality, the current paper uses the

ex ante notion. In addition, their top trading cycles mechanism is incentive compatible but my

pseudo-market mechanism is not.

The current paper’s setting of fractional endowments has been analyzed by (Athanassoglou and

Sethuraman 2011). There are important differences between their analysis and the current paper.

First, they use ordinal efficiency, a notion based on stochastic dominance that only relies on ordinal

370 International Journal of Economic Theory 13 (2017) 369–385 © IAET