The generalized random priority mechanism with budgets. (English) Zbl 1417.91293
Summary: This paper studies allocation problems with and without monetary transfers, such as combinatorial auctions, school choice, and course allocation. Interdependent values and multidimensional signals are allowed. Despite known negative results, a mechanism exists that is feasible, ex post individually rational, ex post incentive compatible, and asymptotically both efficient and envy-free. This mechanism is a special case of the generalized random priority mechanism (GRP), which always satisfies the first three properties. The asymptotic properties follow as a corollary of the main theorem: GRP approximates virtually any infinite-market mechanism in large finite markets.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 91B68 | Matching models |
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
Keywords:
ex post incentive compatibility; random allocation; random priority; large market; rational expectations equilibrium; information aggregationReferences:
| [1] | Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701, (1998) · Zbl 1019.91016 |
| [2] | Akbarpour, M., Nikzad, A., 2017. Approximate Random Allocation Mechanisms. Mimeo.; Akbarpour, M., Nikzad, A., 2017. Approximate Random Allocation Mechanisms. Mimeo. |
| [3] | Aliprantis, C.; Border, K., Infinite dimensional analysis: A Hitchhiker’s guide, (2007), Springer · Zbl 1156.46001 |
| [4] | Aumann, R., Markets with a continuum of traders, Econometrica, 32, 39-50, (1964) · Zbl 0137.39003 |
| [5] | Ausubel, L., An efficient dynamic auction for heterogeneous commodities, Am. Econ. Rev., 96, 602-629, (2006) |
| [6] | Ausubel, L.; Milgrom, P., Ascending auctions with package bidding, Front. Theor. Econ., 1, 1-42, (2002) |
| [7] | Azevedo, E., Budish, E., 2017. Strategyproofness in the Large. Mimeo.; Azevedo, E., Budish, E., 2017. Strategyproofness in the Large. Mimeo. |
| [8] | Azevedo, E. M.; Leshno, J. D., A supply and demand framework for two-sided matching markets, J. Polit. Econ., 124, 1235-1268, (2016) |
| [9] | Azevedo, E. M.; Weyl, E. G.; White, A., Walrasian equilibrium in large, quasi-linear markets, Theor. Econ., 8, 281-290, (2013) · Zbl 1395.91294 |
| [10] | Baliga, S.; Vohra, R., Market research and market design, Adv. Theor. Econ., 3, (2003) |
| [11] | Bergemann, D.; Morris, S., Robust mechanism design, Econometrica, 73, 1771-1813, (2005) · Zbl 1151.91327 |
| [12] | Bikhchandani, S., Ex post implementation in environments with private goods, Theor. Econ., 1, 369-393, (2006) |
| [13] | Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328, (2001) · Zbl 1134.91357 |
| [14] | Boyarchenko, N., Lucca, D.O., Veldkamp, L., 2018. Taking Orders and Taking Notes: Dealer Information Sharing in Treasury Markets. Mimeo.; Boyarchenko, N., Lucca, D.O., Veldkamp, L., 2018. Taking Orders and Taking Notes: Dealer Information Sharing in Treasury Markets. Mimeo. |
| [15] | Budish, E., The combinatorial assignment problem: approximate competitive equilibrium from equal incomes, J. Polit. Econ., 119, 1061-1103, (2011) |
| [16] | Budish, E.; Che, Y.-K.; Kojima, F.; Milgrom, P., Designing random allocation mechanisms: theory and applications, Am. Econ. Rev., 103, 585-623, (2013) |
| [17] | Che, Y.; Kojima, F., Asymptotic equivalence of probabilistic serial and random priority mechanisms, Econometrica, 78, 1625-1672, (2010) · Zbl 1203.91201 |
| [18] | Che, Y.-K.; Kim, J.; Kojima, F., Efficient assignment with interdependent values, J. Econ. Theory, 158, 54-86, (2015) · Zbl 1330.91149 |
| [19] | Chung, K.-S., Ely, J.C., 2006. Ex-Post Incentive Compatible Mechanism Design. Mimeo.; Chung, K.-S., Ely, J.C., 2006. Ex-Post Incentive Compatible Mechanism Design. Mimeo. |
| [20] | Córdoba, J.; Hammond, P., Asymptotically strategy-proof Walrasian exchange, Math. Soc. Sci., 36, 185-212, (1998) · Zbl 0930.91010 |
| [21] | Day, R.; Milgrom, P., Core-selecting package auctions, Int. J. Game Theory, 36, 393-407, (2008) · Zbl 1151.91073 |
| [22] | Feldman, M.; Gilles, C., An expository note on individual risk without aggregate uncertainty, J. Econ. Theory, 35, 26-32, (1985) · Zbl 0553.90022 |
| [23] | Goldberg, A. V.; Hartline, J. D.; Karlin, A. R.; Saks, M.; Wright, A., Competitive auctions, Games Econ. Behav.Mini Special Issue: Electronic Market Design, 55, 242-269, (2006) · Zbl 1125.91041 |
| [24] | Gul, F.; Postlewaite, A., Asymptotic efficiency in large exchange economies with asymmetric information, Econometrica, 60, 1273-1292, (1992) · Zbl 0785.90027 |
| [25] | Gul, F.; Stacchetti, E., Walrasian equilibrium with Gross substitutes, J. Econ. Theory, 87, 95-124, (1999) · Zbl 0998.91010 |
| [26] | Hashimoto, T.; Hirata, D.; Kesten, O.; Kurino, M.; Ünver, M. U., Two axiomatic approaches to the probabilistic serial mechanism, Theor. Econ., 9, 253-277, (2014) · Zbl 1395.91264 |
| [27] | He, Y.; Miralles, A.; Pycia, M.; Yan, J., A pseudo-market approach to allocation with priorities, Am. Econ. J. Microecon, (2017), In press |
| [28] | Hylland, A.; Zeckhauser, R., The efficient allocation of individuals to positions, J. Polit. Econ., 87, 293-314, (1979) |
| [29] | Jackson, M.; Kremer, I., Envy-freeness and implementation in large economies, Rev. Econ. Des., 11, 185-198, (2007) · Zbl 1136.91515 |
| [30] | Jackson, M.; Manelli, A., Approximately competitive equilibria in large finite economies, J. Econ. Theory, 77, 354-376, (1997) · Zbl 0896.90030 |
| [31] | Jehiel, P.; Meyer-ter Vehn, M.; Moldovanu, B.; Zame, W., The limits of ex post implementation, Econometrica, 74, 585-610, (2006) · Zbl 1127.91046 |
| [32] | Jehiel, P.; Moldovanu, B., Efficient design with interdependent valuations, Econometrica, 69, 1237-1259, (2001) · Zbl 1055.91517 |
| [33] | Judd, K., The law of large numbers with a continuum of IID random variables, J. Econ. Theory, 35, 19-25, (1985) · Zbl 0569.60037 |
| [34] | Katta, A.-K.; Sethuraman, J., A solution to the random assignment problem on the full preference domain, J. Econ. Theory, 131, 231-250, (2006) · Zbl 1142.90481 |
| [35] | Kojima, F., Random assignment of multiple indivisible objects, Math. Soc. Sci., 57, 134-142, (2009) · Zbl 1155.91408 |
| [36] | Kojima, F.; Yamashita, T., Double auction with interdependent values: incentives and efficiency, Theor. Econ., 12, 1393-1438, (2017) · Zbl 1396.91258 |
| [37] | Kovalenkov, A., Simple strategy-proof approximately Walrasian mechanisms, J. Econ. Theory, 103, 475-487, (2002) · Zbl 1010.91063 |
| [38] | Kremer, I., Information aggregation in common value auctions, Econometrica, 70, 1675-1682, (2002) · Zbl 1141.91398 |
| [39] | Liu, Q., Pycia, M., 2012. Ordinal Efficiency, Fairness, and Incentives in Large Markets. Mimeo.; Liu, Q., Pycia, M., 2012. Ordinal Efficiency, Fairness, and Incentives in Large Markets. Mimeo. |
| [40] | Mas-Colell, A.; Vives, X., Implementation in economies with a continuum of agents, Rev. Econ. Stud., 60, 613, (1993) · Zbl 0805.90012 |
| [41] | Maskin, E., Auctions and privatization, 115-136, (1992), J.C.B. Mohr Publisher |
| [42] | Matsushima, H., Detail-free mechanism design in twice iterative dominance: large economies, J. Econ. Theory, 141, 134-151, (2008) · Zbl 1140.91448 |
| [43] | McLean, R.; Postlewaite, A., Informational size and incentive compatibility, Econometrica, 70, 2421-2453, (2002) · Zbl 1103.91386 |
| [44] | McLean, R.; Postlewaite, A., Informational size and incentive compatibility with aggregate uncertainty, Games Econ. Behav., 45, 410-433, (2003) · Zbl 1064.91055 |
| [45] | McLean, R.; Postlewaite, A., Informational size and efficient auctions, Rev. Econ. Stud., 71, 809-827, (2004) · Zbl 1095.91012 |
| [46] | McLean, R.; Postlewaite, A., Implementation with interdependent valuations, Theor. Econ., 10, 923-952, (2015) · Zbl 1395.91233 |
| [47] | Milgrom, P. R.; Weber, R. J., A theory of auctions and competitive bidding, Econometrica, 1089-1122, (1982) · Zbl 0487.90017 |
| [48] | Nguyen, T.; Peivandi, A.; Vohra, R., Assignment problems with complementarities, J. Econ. Theory, 165, 209-241, (2016) · Zbl 1371.91117 |
| [49] | Peivandi, A., 2013. Random Allocation of Bundles. Mimeo.; Peivandi, A., 2013. Random Allocation of Bundles. Mimeo. |
| [50] | Pesendorfer, W.; Swinkels, J. M., The Loser’s curse and information aggregation in common value auctions, Econometrica, 65, 1247-1281, (1997) · Zbl 0887.90052 |
| [51] | Pesendorfer, W.; Swinkels, J. M., Efficiency and information aggregation in auctions, Am. Econ. Rev., 90, 499-525, (2000) |
| [52] | Reny, P. J.; Perry, M., Toward a strategic foundation for rational expectations equilibrium, Econometrica, 74, 1231-1269, (2006) · Zbl 1138.91410 |
| [53] | Roberts, D.; Postlewaite, A., The incentives for price-taking behavior in large exchange economies, Econometrica, 44, 115-127, (1976) · Zbl 0314.90013 |
| [54] | Segal, I., Optimal pricing mechanisms with unknown demand, Am. Econ. Rev., 93, 509-529, (2003) |
| [55] | Sönmez, T.; Ünver, M., Course bidding at business schools, Int. Econ. Rev., 51, 99-123, (2010) |
| [56] | Sun, Y., The exact law of large numbers via Fubini extension and characterization of insurable risks, J. Econ. Theory, 126, 31-69, (2006) · Zbl 1108.60025 |
| [57] | Sun, Y.; Yannelis, N. C., Core, equilibria and incentives in large asymmetric information economies, Games Econ. Behav., 61, 131-155, (2007) · Zbl 1271.91081 |
| [58] | Sun, Y.; Yannelis, N. C., Perfect competition in asymmetric information economies: compatibility of efficiency and incentives, J. Econ. Theory, 134, 175-194, (2007) · Zbl 1158.91421 |
| [59] | Sun, Y.; Zhang, Y., Individual risk and Lebesgue extension without aggregate uncertainty, J. Econ. Theory, 144, 432-443, (2009) · Zbl 1157.91385 |
| [60] | Vives, X., Private information, strategic behavior, and efficiency in Cournot markets, Rand J. Econ., 361-376, (2002) |
| [61] | Vives, X., Information and learning in markets: the impact of market microstructure, (2010), Princeton University Press |
| [62] | Zhou, L., On a conjecture by gale about one-sided matching problems, J. Econ. Theory, 52, 123-135, (1990) · Zbl 0725.90003 |
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.
