{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T14:39:48Z","timestamp":1767969588455,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T00:00:00Z","timestamp":1471305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation under NSF","award":["CCF-0964033"],"award-info":[{"award-number":["CCF-0964033"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,8,26]]},"abstract":"<jats:p>\n            Competitive 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]. It was shown in Budish [2011] that in the case of indivisible resources, there is always an allocation, called\n            <jats:italic>A-CEEI<\/jats:italic>\n            , that is approximately fair, approximately truthful, and approximately efficient for some favorable approximation parameters. A heuristic search that attempts to find this approximation is used in practice to assign business school students to courses. In this article, we show that finding the A-CEEI allocation guaranteed to exist by Budish\u2019s theorem is PPAD-complete. We further show that finding an approximate equilibrium with better approximation guarantees is even harder: NP-complete.\n          <\/jats:p>","DOI":"10.1145\/2956583","type":"journal-article","created":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T12:14:20Z","timestamp":1471349660000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["The Complexity of Fairness Through Equilibrium"],"prefix":"10.1145","volume":"4","author":[{"given":"Abraham","family":"Othman","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}]},{"given":"Christos","family":"Papadimitriou","sequence":"additional","affiliation":[{"name":"University of California at Berkeley"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[{"name":"University of California at Berkeley"}]}],"member":"320","published-online":{"date-parts":[[2016,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.59"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Eric Budish Gerard P. Cachon Judd Kessler and Abraham Othman. 2016. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research. To appear.  Eric Budish Gerard P. Cachon Judd Kessler and Abraham Othman. 2016. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research. To appear.","DOI":"10.2139\/ssrn.2635243"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488632"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_66"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2011 International Conference on Supercomputing (ICS\u201911)","author":"Chen Xi","year":"2011","unstructured":"Xi Chen and Shang-Hua Teng . 2011 . A complexity view of markets with social influence . In Proceedings of the 2011 International Conference on Supercomputing (ICS\u201911) . 141--154. Xi Chen and Shang-Hua Teng. 2011. A complexity view of markets with social influence. In Proceedings of the 2011 International Conference on Supercomputing (ICS\u201911). 141--154."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109629"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1461928.1461951"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_14_1","first-page":"45","article-title":"Resource allocation and the public sector","volume":"7","author":"Foley D. K.","year":"1967","unstructured":"D. K. Foley . 1967 . Resource allocation and the public sector . Yale Economic Essays 7 , 1, 45 -- 98 . D. K. Foley. 1967. Resource allocation and the public sector. Yale Economic Essays 7, 1, 45--98.","journal-title":"Yale Economic Essays"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201911)","author":"Ghodsi Ali","year":"2011","unstructured":"Ali Ghodsi , Matei Zaharia , Benjamin Hindman , Andy Konwinski , Scott Shenker , and Ion Stoica . 2011 . Dominant resource fairness: Fair allocation of multiple resource types . In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201911) . 323--336. http:\/\/dl.acm.org\/ citation.cfm?id&equals;1972457.1972490 Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. 2011. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201911). 323--336. http:\/\/dl.acm.org\/ citation.cfm?id&equals;1972457.1972490"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1776166.1776175"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.57"},{"key":"e_1_2_1_18_1","volume-title":"Bidding languages for combinatorial auctions","author":"Nisan Noam","unstructured":"Noam Nisan . 2006. Bidding languages for combinatorial auctions . In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg (Eds.). MIT Press , Cambridge, MA . Noam Nisan. 2006. Bidding languages for combinatorial auctions. In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg (Eds.). MIT Press, Cambridge, MA."},{"key":"e_1_2_1_19_1","volume-title":"Vazirani","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan , Tim Roughgarden , Eva Tardos , and Vijay V . Vazirani . 2007 . Algorithmic Game Theory. Cambridge University Press , New York, NY. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201910)","author":"Othman Abraham","year":"2010","unstructured":"Abraham Othman , Eric Budish , and Tuomas Sandholm . 2010 . Finding approximate competitive equilibria: Efficient and fair course allocation . In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201910) . Abraham Othman, Eric Budish, and Tuomas Sandholm. 2010. Finding approximate competitive equilibria: Efficient and fair course allocation. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS\u201910)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_57"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746578"},{"key":"e_1_2_1_25_1","volume-title":"Preference elicitation in combinatorial auctions","author":"Sandholm Tuomas","unstructured":"Tuomas Sandholm and Craig Boutilier . 2006. Preference elicitation in combinatorial auctions . In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg (Eds.). MIT Press , Cambridge, MA . Tuomas Sandholm and Craig Boutilier. 2006. Preference elicitation in combinatorial auctions. In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg (Eds.). MIT Press, Cambridge, MA."},{"key":"e_1_2_1_26_1","volume-title":"Varian","author":"Thomson William","year":"1985","unstructured":"William Thomson and Hal R . Varian . 1985 . Theories of justice based on symmetry. In Social Goals and Social Organizations : Essays in Memory of Elisha Pazner, L. Hurwicz, D. Schmeidler, and H. Sonnenschein (Eds.). Cambridge University Press, New York, NY. William Thomson and Hal R. Varian. 1985. Theories of justice based on symmetry. In Social Goals and Social Organizations: Essays in Memory of Elisha Pazner, L. Hurwicz, D. Schmeidler, and H. Sonnenschein (Eds.). Cambridge University Press, New York, NY."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956583","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2956583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:43Z","timestamp":1750217983000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956583"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,16]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8,26]]}},"alternative-id":["10.1145\/2956583"],"URL":"https:\/\/doi.org\/10.1145\/2956583","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,16]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}