Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
Authors: 
Eric Budish, Ruiquan Gao, Abraham Othman, 
Aviad Rubinstein, Qianfan ZhangAuthors Info & Claims
Pages 337 - 368
Abstract
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. In theory, it is known that in asymptotically large markets:
• For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L).
• From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD ≠ FP).
We develop a new heuristic algorithm that outperforms the previous state-of-the-art by multiple orders of magnitude. This new, faster algorithm lets us perform experiments on real-world inputs for the first time. We discover that with real-world preferences, even in a realistic implementation that satisfies the EF-TB and SP-L properties, agents may have surprisingly simple and plausible deviations from truthful reporting of preferences. To this end, we propose a novel strengthening of EF-TB, which dramatically reduces the potential for strategic deviations from truthful reporting in our experiments.
A (variant of) our algorithm is now in production: on real course allocation problems it is much faster, has zero clearing error, and has stronger incentive properties than the prior state-of-the-art implementation.
References
[1]
Mohammad Akbarpour, Scott Duke Kominers, Kevin Michael Li, Shengwu Li, and Paul Milgrom. 2020. Investment Incentives in Truthful Approximation Mechanisms. SSRN (2020). https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3544100
[2]
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. 2022. Fair Division of Indivisible Goods: A Survey. CoRR abs/2208.08782 (2022). arXiv:2208.08782
[3]
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. 2021. Maximum Nash welfare and other stories about EFX. Theor. Comput. Sci. 863 (2021), 69--85.
[4]
Eshwar Ram Arunachaleswaran, Siddharth Barman, and Nidhi Rathi. 2022. Fully Polynomial-Time Approximation Schemes for Fair Rent Division. Mathematics of Operations Research 47, 3 (2022), 1970--1998.
[5]
Eduardo M Azevedo and Eric Budish. 2019. Strategy-proofness in the Large. The Review of Economic Studies 86, 1 (08 2019), 81--116. arXiv:https://academic.oup.com/restud/article-pdf/86/1/81/27285295/rdy042.pdf
[6]
Haris Aziz. 2015. Competitive equilibrium with equal incomes for allocation of indivisible objects. Oper. Res. Lett. 43, 6 (2015), 622--624.
[7]
Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. 2021. Competitive Equilibrium with Indivisible Goods and Generic Budgets. Math. Oper. Res. 46, 1 (2021), 382--403.
[8]
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. 2018. Finding Fair and Efficient Allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18--22, 2018, Éva Tardos, Edith Elkind, and Rakesh Vohra (Eds.). ACM, 557--574.
[9]
Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta. 2022. Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 -- 12, 2022, Joseph (Seffi) Naor and Niv Buchbinder (Eds.). SIAM, 2285--2302.
[10]
Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters. 2017. Fair Division of a Graph. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19--25, 2017, Carles Sierra (Ed.). ijcai.org, 135--141.
[11]
Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet. 2016. Fair Allocation of Indivisible Goods. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, 284--310.
[12]
Simina Brânzei, Hadi Hosseini, and Peter Bro Miltersen. 2015. Characterization and Computation of Equilibria for Indivisible Goods. In Algorithmic Game Theory - 8th International Symposium, SAGT 2015, Saarbrücken, Germany, September 28--30, 2015, Proceedings (Lecture Notes in Computer Science, Vol. 9347), Martin Hoefer (Ed.). Springer, 244--255.
[13]
Simina Brânzei, Yuezhou Lv, and Ruta Mehta. 2016. To Give or Not to Give: Fair Division for Single Minded Valuations. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9--15 July 2016, Subbarao Kambhampati (Ed.). IJCAI/AAAI Press, 123--129. http://www.ijcai.org/Abstract/16/025
[14]
Eric Budish. 2010. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. (2010). https://faculty.chicagobooth.edu/eric.budish/research/budish-approxceei-Aug2010.pdf Working paper version of paper with the same title.
[15]
Eric Budish. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy 119, 6 (2011), 1061 -- 1103.
[16]
Eric Budish, Gérard P. Cachon, Judd B. Kessler, and Abraham Othman. 2017. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Oper. Res. 65, 2 (2017), 314--336.
[17]
Eric Budish and Estelle Cantillon. 2012. The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard. The American Economic Review 102, 5 (2012), 2237--2271. http://www.jstor.org/stable/41724620
[18]
Eric Budish and Judd B. Kessler. 2022. Can Market Participants Report Their Preferences Accurately (Enough)? Manag. Sci. 68, 2 (2022), 1107--1130.
[19]
Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019. Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24--28, 2019, Anna Karlin, Nicole Immorlica, and Ramesh Johari (Eds.). ACM, 527--545.
[20]
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. 2022a. Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness. In EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 -- 15, 2022, David M. Pennock, Ilya Segal, and Sven Seuken (Eds.). ACM, 1106--1107.
[21]
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. 2022b. On the Existence of Competitive Equilibrium with Chores. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA (LIPIcs, Vol. 215), Mark Braverman (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 41:1--41:13.
[22]
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2021. Improving EFX Guarantees through Rainbow Cycle Number. In EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18--23, 2021, Péter Biró, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 310--311.
[23]
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. 2009. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM) 56, 3 (2009), 1--57.
[24]
Yun Kuen Cheung, Richard Cole, and Nikhil R. Devanur. 2020. Tatonnement beyond gross substitutes? Gradient descent to the rescue. Games Econ. Behav. 123 (2020), 295--326.
[25]
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. 2009. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1 (2009), 195--259.
[26]
Franz Diebold, Haris Aziz, Martin Bichler, Florian Matthes, and Alexander W. Schneider. 2014. Course Allocation via Stable Matching. Bus. Inf. Syst. Eng. 6, 2 (2014), 97--110.
[27]
Duncan K. Foley. 1967. Resource allocation and the public sector. Yale economic essays 7, 1 (1967), 45--98. mit Bibliogr.
[28]
Jugal Garg, Martin Hoefer, Peter McGlaughlin, and Marco Schmalhofer. 2021. When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. In Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21--24, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 12885), Ioannis Caragiannis and Kristoffer Arnsfelt Hansen (Eds.). Springer, 329--344.
[29]
Jonathan R. Goldman and Ariel D. Procaccia. 2014. Spliddit: unleashing fair division algorithms. SIGecom Exch. 13, 2 (2014), 41--46.
[30]
Alexander S. Kelso and Vincent P. Crawford. 1982. Job Matching, Coalition Formation, and Gross Substitutes. Econometrica 50, 6 (1982), 1483--1504.
[31]
Renato Paes Leme and Sam Chiu-wai Wong. 2020. Computing Walrasian equilibria: fast algorithms and structural properties. Math. Program. 179, 1 (2020), 343--384.
[32]
Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17--20, 2004, Jack S. Breese, Joan Feigenbaum, and Margo I. Seltzer (Eds.). ACM, 125--131.
[33]
Sören Merting, Martin Bichler, and Aykut Uzunoglu. 2019. Assigning Course Schedules: About Preference Elicitation, Fairness, and Truthfulness. In Proceedings of the 40th International Conference on Information Systems, ICIS 2019, Munich, Germany, December 15--18, 2019, Helmut Krcmar, Jane Fedorowicz, Wai Fong Boh, Jan Marco Leimeister, and Sunil Wattal (Eds.). Association for Information Systems. https://aisel.aisnet.org/icis2019/data_science/data_science/15
[34]
Abraham Othman, Christos H. Papadimitriou, and Aviad Rubinstein. 2016. The Complexity of Fairness Through Equilibrium. ACM Trans. Economics and Comput. 4, 4 (2016), 20:1--20:19.
[35]
Abraham Othman, Tuomas Sandholm, and Eric Budish. 2010. Finding approximate competitive equilibria: efficient and fair course allocation. In 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10--14, 2010, Volume 1--3, Wiebe van der Hoek, Gal A. Kaminka, Yves Lespérance, Michael Luck, and Sandip Sen (Eds.). IFAAMAS, 873--880. https://dl.acm.org/citation.cfm?id=1838323
[36]
C.H. Papadimitriou. 2007. The complexity of finding nash equilibria. In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani (Eds.). Cambridge University Press, 29--51.
[37]
Dominik Peters, Ariel D. Procaccia, and David Zhu. 2022. Robust Rent Division. In NeurIPS-22: Proc. 36th Annual Conference on Neural Information Processing Systems, 2022.
[38]
Alexander Peysakhovich and Christian Kroer. 2019. Fair Division Without Disparate Impact. CoRR abs/1906.02775 (2019). arXiv:1906.02775 http://arxiv.org/abs/1906.02775
[39]
Benjamin Plaut and Tim Roughgarden. 2020. Almost Envy-Freeness with General Valuations. SIAM J. Discret. Math. 34, 2 (2020), 1039--1068.
[40]
Alvin E. Roth. 2002. The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics. Econometrica 70, 4 (2002), 1341--1378. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/1468-0262.00335
[41]
Alvin E. Roth. 2007. Repugnance as a Constraint on Markets. Journal of Economic Perspectives 21, 3 (September 2007), 37--58.
[42]
Aviad Rubinstein. 2018. Inapproximability of Nash Equilibrium. SIAM J. Comput. 47, 3 (2018), 917--959.
[43]
Ermis Soumalias, Behnoosh Zamanlooy, Jakob Weissteiner, and Sven Seuken. 2022. Machine Learning-powered Course Allocation. CoRR abs/2210.00954 (2022). arXiv:2210.00954
[44]
Warut Suksompong. 2023. A characterization of maximum Nash welfare for indivisible goods. Economics Letters 222 (2023), 110956.
[45]
William Thomson and Hal R. Varian. 1985. Theories of justice based on symmetry. Social goals and social organization : essays in memory of Elisha Pazner (1985), 107--129.
[46]
Hal R Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory 9, 1 (1974), 63--91.
[47]
Ellen Vitercik. 2021. Automated algorithm and mechanism configuration. Ph. D. Dissertation. Carnegie Mellon University. http://reports-archive.adm.cs.cmu.edu/anon/2021/abstracts/21-125.html
[48]
Zihe Wang, Zhide Wei, and Jie Zhang. 2020. Bounded Incentives in Manipulating the Probabilistic Serial Rule. (2020), 2276--2283. https://ojs.aaai.org/index.php/AAAI/article/view/5605
[49]
Mason Wright and Yevgeniy Vorobeychik. 2015. Mechanism Design for Team Formation. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25--30, 2015, Austin, Texas, USA, Blai Bonet and Sven Koenig (Eds.). AAAI Press, 1050--1056. http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9902
Index Terms
- Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
Recommendations
The Complexity of Fairness Through Equilibrium
Special Issue on EC'14Competitive equilibrium from equal incomes (CEEI) is a well-known fair allocation mechanism with desirable fairness and efficiency properties; however, with indivisible resources, a CEEI may not exist [Foley 1967; Varian 1974; Thomson and Varian 1985]. ...
A robust combinatorial auction mechanism against shill bidders
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systemsThis paper presents a method for discovering and detecting shill bids in combinatorial auctions. The Vickrey-Clarke-Groves Mechanism is one of the most important combinatorial auctions because it can satisfy the strategy-proof property, individual ...
Truthful fair division
SAGT'10: Proceedings of the Third international conference on Algorithmic game theoryWe address the problem of fair division, or cake cutting, with the goal of finding truthful mechanisms. In the case of a general measure space ("cake") and non-atomic, additive individual preference measures - or utilities - we show that there exists a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
1253 pages
ISBN:9798400701047
DOI:10.1145/3580507
- Chair:
- Kevin Leyton-Brown,
- Program Chair:
- Jason D Hartline,
- Program Co-chair:
- Larry Samuelson
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
EC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 664 of 2,389 submissions, 28%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 106Total Downloads
- Downloads (Last 12 months)63
- Downloads (Last 6 weeks)9
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in