×

Efficient assignment with interdependent values. (English) Zbl 1330.91149

Summary: We study the “house allocation” problem in which \(n\) agents are assigned \(n\) objects, one for each agent, when the agents have interdependent values. We show that there exists no mechanism that is Pareto efficient and ex-post incentive compatible, and the only mechanism that is ex-post group incentive compatible is constant across states. By contrast, we demonstrate that a Pareto efficient and Bayesian incentive compatible mechanism exists in the two agent house-allocation problem, given sufficient congruence of preferences and the standard single crossing property. We also show that (approximate) Pareto efficiency can be achieved once we relax the incentive compatibility requirements to approximate ex-post incentive compatibility or Bayesian incentive compatibility.

MSC:

91B68 Matching models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdulkadı̇roğlu, Atı̇la; Sönmez, Tayfun, Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701 (1998) · Zbl 1019.91016
[2] Abdulkadı̇roğlu, Atı̇la; Sönmez, Tayfun, School choice: a mechanism design approach, Amer. Econ. Rev., 93, 729-747 (2003)
[3] Abdulkadı̇roğlu, Atı̇la; Pathak, Parag; Roth, Alvin; Sönmez, Tayfun, The Boston public school match, Amer. Econ. Rev., 95, 368-372 (2005)
[4] Abdulkadı̇roğlu, Atı̇la; Pathak, Parag; Roth, Alvin, The New York city high school match, Amer. Econ. Rev., 95, 364-367 (2005)
[5] Abdulkadı̇roğlu, Atı̇la; Pathak, Parag; Roth, Alvin, Strategy-proofness versus efficiency in matching with indifferences: redesigning the NYC high school match, Amer. Econ. Rev., 99, 5, 1954-1978 (2009)
[6] Arrow, Kenneth, Social Choice and Individual Values (1951), John Wiley and Sons: John Wiley and Sons New York · Zbl 0984.91513
[7] Balinski, Michel; Sönmez, Tayfun, A tale of two mechanisms: student placement, J. Econ. Theory, 84, 73-94 (1999) · Zbl 0916.90008
[8] Bergemann, Dirk; Morris, Stephen, Robust mechanism design, Econometrica, 73, 1771-1813 (2005) · Zbl 1151.91327
[9] Bergemann, Dirk; Morris, Stephen, The role of the common prior in the robust implementation, J. Eur. Econ. Assoc., 6, 551-559 (2008)
[10] Bergemann, Dirk; Välimäki, Juuso, Information acquisition and efficient mechanism design, Econometrica, 70, 1007-1033 (2002) · Zbl 1121.91342
[11] Bikhchandani, Sushil, Ex post implementation in environments with private goods, Theoretical Econ., 1, 369-393 (2006)
[12] Bogomolnaia, Anna; Moulin, Hervé, A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328 (2001) · Zbl 1134.91357
[13] Carroll, Gabriel, When are local incentive constraints sufficient?, Econometrica, 80, 2, 661-686 (2012) · Zbl 1274.91157
[14] Chakraborty, Archishman; Citanna, Alessandro; Ostrovsky, Michael, Two-sided matching with interdependent values, J. Econ. Theory, 145, 85-105 (2010) · Zbl 1202.91234
[15] Chakraborty, Archishman; Citanna, Alessandro; Ostrovsky, Michael, Group stability in matching with interdependent values, Rev. Econ. Design (2014) · Zbl 1329.91101
[16] Crémer, Jacques; McLean, Richard, Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent, Econometrica, 53, 345-361 (1985) · Zbl 0567.90011
[18] Gale, David; Shapley, Lloyd, College admissions and the stability of marriage, Amer. Math. Mon., 69, 9-15 (1962) · Zbl 0109.24403
[19] Gibbard, Allan, Manipulation of voting schemes: a general result, Econometrica, 587-601 (1973) · Zbl 0325.90081
[20] Jehiel, Philippe; Moldovanu, Benny, Efficient design with interdependent valuations, Econometrica, 1237-1259 (2001) · Zbl 1055.91517
[21] Jehiel, Philippe; Moldovanu, Benny, Allocative and informational externalities in auctions and related mechanisms, (Blundell, Richard; Newey, Whitney; Persson, Torsten, The Proceedings of the 9th World Congress of the Econometric Society (2006), Cambridge University Press) · Zbl 1303.91084
[22] Jehiel, Philippe; Meyer ter Vehn, Moritz; Moldovanu, Benny; Zame, William, The limits of ex post implementation, Econometrica, 585-610 (2006) · Zbl 1127.91046
[23] Krishna, Vijay, Asymmetric English auctions, J. Econ. Theory, 112, 261-288 (2003) · Zbl 1085.91023
[24] Li, Hao; Rosen, Sherwin; Suen, Wing, Conflicts and common interests in committees, Amer. Econ. Rev., 91, 1478-1497 (2001)
[25] Maskin, Eric, Auctions and privatization, (Siebert, Horst, Privatization: Symposium in Honor of Herbert Giersch (1992), Mohr (Siebeck): Mohr (Siebeck) Tübingen)
[26] Pápai, Szilvia, Strategyproof assignment by hierarchical exchange, Econometrica, 68, 1403-1433 (2000) · Zbl 1023.91019
[27] Pathak, Parag, The mechanism design approach to student assignment, Annu. Rev. Econ., 3, 1 (2011) · Zbl 1231.91360
[28] Perry, Motty; Reny, Philip, An efficient auction, Econometrica, 70, 1199-1212 (2002) · Zbl 1121.91352
[29] Pycia, Marek; Ünver, Utku, Incentive compatible allocation and exchange of discrete resources (2009), Boston College Working Papers in Economics · Zbl 1396.91327
[30] Roth, Alvin, The economics of matching: stability and incentives, Math. Oper. Res., 7, 617-628 (1982) · Zbl 0496.90008
[31] Roth, Alvin, The evolution of the labor market for medical interns and residents: a case study in game theory, J. Polit. Economy, 92, 991-1016 (1984)
[32] Roth, Alvin, The economist as engineer: game theory, experimentation, and computation as tools for design economics, Econometrica, 70, 1341-1378 (2002) · Zbl 1137.91339
[33] Roth, Alvin; Sotomayor, Marilda, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0726.90003
[34] Sato, Shin, A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one, J. Econ. Theory, 148, 259-278 (2013) · Zbl 1282.91097
[35] Satterthwaite, Mark, Strategy-proofness and arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions, J. Econ. Theory, 10, 187-217 (1975) · Zbl 0315.90088
[36] Sönmez, Tayfun; Ünver, Uktu, Matching, allocation, and exchange of discrete resources, (Benhabib, Jess; Bisin, Alberto; Jackson, Matthew O., Handbook of Social Economics (2011), North-Holland: North-Holland The Netherlands), 781-852
[37] Stewart, Ian; Tall, David, Complex Analysis (1983), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0501.30001
[38] Svensson, Lars-Gunnar, Strategy-proof allocation of indivisible goods, Soc. Choice Welfare, 16 (1999) · Zbl 1066.91571
[39] Wilson, Robert, Game-theoretic analyses of trading processes, (Bewley, Truman, Advances in Economic Theory: Fifth World Congress (1987), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0729.90694
[40] Zhou, Lin, Inefficiency of strategy-proof allocation mechanisms in pure exchange economies, Soc. Choice Welfare, 8, 247-257 (1991) · Zbl 0745.90016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.