Abstract
We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of \(\varOmega (\sqrt{n})\) on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.
George Christodoulou, Paul W. Goldberg and Jinshan Zhang were supported by the EPSRC grant EP/K01000X/1. Paul W. Goldberg was supported by COST Action IC1205. Aris Filos-Ratsikas and Jie Zhang were supported by the ERC Advanced Grant 321171 (ALGAME). Aris Filos-Ratsikas and Søren K.S. Frederiksen acknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, within which part of this work was performed and support from the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdulkadiroğlu, A., Sönmez, T., Markets, M.: Theory and practice. In: Advances in Economics and Econometrics (Tenth World Congress), pp. 3–47 (2013)
Adamczyk, M., Sankowski, P., Zhang, Q.: Efficiency of truthful and symmetric mechanisms in one-sided matching. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 13–24. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44803-8_2
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)
Aziz, H., Brandt, F., Brill, M.: The computational complexity of random serial dictatorship. Econ. Lett. 121(3), 341–345 (2013)
Aziz, H., Gaspers, S., Mackenzie, S., Mattei, N., Narodytska, N., Walsh, T.: Equilibria under the probabilistic serial rule. arXiv preprint arXiv:1502.04888 (2015)
Aziz, H., Gaspers, S., Mackenzie, S., Mattei, N., Narodytska, N., Walsh, T.: Manipulating the probabilistic serial rule. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 1451–1459. International Foundation for Autonomous Agents and Multiagent Systems (2015)
Aziz, H., Gaspers, S., Mattei, N., Narodytska, N., Walsh, T.: Strategic aspects of the probabilistic serial rule for the allocation of goods. arXiv preprint arXiv: 1401.6523 (2014)
Bhalgat, A., Chakrabarty, D., Khanna, S.: Social welfare in one-sided matching markets without money. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX/RANDOM 2011. LNCS, vol. 6845, pp. 87–98. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22935-0_8
Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. J. Econ. Theory 100, 295–328 (2001)
Brams, S.J., Feldman, M., Lai, J.K., Morgenstern, J., Procaccia, A.D.: On maxsum fair cake divisions. In: AAAI (2012)
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589–610 (2012)
Chakrabarty, D., Swamy, C.: Welfare maximization and truthfulness in mechanism design with ordinal preferences. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 105–120 (2014)
Christodoulou, G., Kovács, A., Schapira, M.: Bayesian combinatorial auctions. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 820–832. Springer, Heidelberg (2008). doi:10.1007/978-3-540-70575-8_67
Ekici, O., Kesten, O.: On the ordinal nash equilibria of the probabilistic serial mechanism. Technical report, working paper, Tepper School of Business, Carnegie Mellon University (2010)
Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: Social welfare in one-sided matchings: random priority and beyond. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 1–12. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44803-8_1
Guo, M., Conitzer, V.: Strategy-proof allocation of multiple items between two agents without payments or priors. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, vol. 1, pp. 881–888 (2010)
Hashimoto, T., Hirata, D., Kesten, O., Kurino, M., Utku Ünver, M.: Two axiomatic approaches to the probabilistic serial mechanism. Theor. Econ. 9(1), 253–277 (2014)
Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)
Katta, A.-K., Sethuraman, J.: A solution to the random assignment problem on the full preference domain. J. Econ. Theory 131(1), 231–250 (2006)
Kesten, O: Probabilistic serial and top trading cycles from equal division for the random assignment problem. Technical report, mimeo (2006)
Kojima, F., Manea, M.: Incentives in the probabilistic serial mechanism. J. Econ. Theory 145(1), 106–123 (2010)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). doi:10.1007/3-540-49116-3_38
Krysta, P., Manlove, D., Rastegari, B., Zhang, J.: Size versus truthfulness in the house allocation problem. In: Proceedings of the 15th ACM Conference on Economics and Computation, pp. 453–470. ACM (2014)
Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 177–186. ACM (2009)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 513–522. ACM (2009)
Syrgkanis, V., Tardos, E.: Composable and efficient mechanisms. In: STOC 2013: Proceedings of the 45th Symposium on Theory of Computing, November 2013
Von Neumann, J., Morgenstern, O.: Theory of games and economic behavior (60th Anniversary Commemorative Edition). Princeton University Press, Princeton (2007)
Zhou, L.: On a conjecture by gale about one-sided matching problems. J. Econ. Theory 52, 123–135 (1990)
Acknowledgements
The authors would like to thank Piotr Krysta for useful discussion.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Christodoulou, G., Filos-Ratsikas, A., Frederiksen, S.K.S., Goldberg, P.W., Zhang, J., Zhang, J. (2016). Social Welfare in One-Sided Matching Mechanisms. In: Osman, N., Sierra, C. (eds) Autonomous Agents and Multiagent Systems. AAMAS 2016. Lecture Notes in Computer Science(), vol 10002. Springer, Cham. https://doi.org/10.1007/978-3-319-46882-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-46882-2_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-46881-5
Online ISBN: 978-3-319-46882-2
eBook Packages: Computer ScienceComputer Science (R0)