Competitive Equilibrium in the Random Assignment Problem

Le, Phuong (2013): Competitive Equilibrium in the Random Assignment Problem.

Abstract

This paper studies the problem of random assignment with fractional endowments. In the random assignment problem, a number of objects has to be assigned to a number of agents. Though the objects are indivisible, an assignment can be probabilistic: it can give an agent some probability of getting an object. Fractional endowments complicate the matter 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 competitive equilibrium 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.

• Item Type: MPRA Paper
• Language: English
• Keywords: Random Assignment, Competitive Equilibrium, Mechanism Design
• Subjects: D - Microeconomics > D4 - Market Structure, Pricing, and Design > D47 - Market Design; D - Microeconomics > D5 - General Equilibrium and Disequilibrium > D50 - General

References

Athanassoglou, S. and Sethuraman, J. (2010). House allocation with fractional endowments. International Journal of Game Theory, pages 1--33.

Birkhoff, G. (1946). Tres observaciones sobre el algebra lineal. Univ. Nac Tucuman Rev. Ser., 5:147--151.

Bogomolnaia, A. and Moulin, H. (2001). A new solution to the random assignment problem. Journal of Economic Theory, 100:295--328.

Budish, E., Che, Y.-K., Kojima, F., and Milgrom, P. (2013). Designing random allocation mechanisms: Theory and applications. American Economic Review, 103(2):585--623.

Hylland, A. and Zeckhauser, R. (1979). The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293--314.

Mas-Colell, A. (1992). Equilibrium theory with possibly satiated preferences. In Majumdar, M., editor, Equilibrium and Dynamics, Essays in Honor of David Gale. London: McMillan.

Roberts, D.~J. and Postlewaite, A. (1976). The incentives for price-taking behavior in large exchange economies. Econometrica, 4(1):115--127.

Roth, A.~E. (1982). Incentive compatibility in a market with indivisible goods. Economic Letters, 9:127--132.

Roth, A.~E. and Postlewaite, A. (1977). Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2):131 -- 137.

Shapley, L. and Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, pages 23--37.

von Neumann, J. (1953). A certain zero-sum two-persons game equivalent to the optimal assignment problem. In Kuhn, H.~W. and Tucker, A.~W., editors, Contribution to the Theory of Games, pages 5--12. Princeton University Press.

Yilmaz, O. (2010). The probabilistic serial mechanism with private endowments. Games and Economic Behavior, 69(2):475--491.

Zhou, L. (1990). On a conjecture by gale about one-sided matching problems. Journal of Economic Theory, 52(1):123 -- 135.