Algorithms for Competitive Division of Chores

References

• [1] Abdulkadiroğlu A, Sönmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689–701.Crossref, Google Scholar
• [2] Alaei S, Jalaly Khalilabadi P, Tardos E (2017) Computing equilibrium in matching markets. Proc. ACM Conf. Econom. Computation (EC) (ACM, New York), 245–261.Google Scholar
• [3] Amanatidis G, Markakis E, Nikzad A, Saberi A (2017) Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms 13(4):1–28.Google Scholar
• [4] Arora S, Barak B (2007) Computational Complexity: A Modern Approach (Cambridge University Press, Cambridge, UK).Google Scholar
• [5] Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica. 22(3):265–290.Crossref, Google Scholar
• [6] Aziz H, Caragiannis I, Igarashi A (2019a) Fair allocation of combinations of indivisible goods and chores. Proc. 28th Internat. Joint Conf. Artificial Intelligence (IJCAI) (AAAI Press, Washington, DC), 53–59.Google Scholar
• [7] Aziz H, Li B, Wu X (2019b) Strategyproof and approximately maxmin fair share allocation of chores. Proc. 29th Internat. Joint Conf. Artificial Intelligence (IJCAI) (AAAI Press, Washington, DC), 60–66.Google Scholar
• [8] Aziz H, Rauchecker G, Schryen G, Walsh T (2017) Algorithms for max-min share fair allocation of indivisible chores. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 335–341.Google Scholar
• [9] Babaioff M, Nisan N, Talgam-Cohen I (2019) Fair allocation through competitive equilibrium from generic incomes. Proc. Conf. Fairness, Accountability, and Transparency (FAT*) (AAAI Press, Washington, DC), 180–196.Google Scholar
• [10] Barbanel JB (2005) The Geometry of Efficient Fair Division (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [11] Barman S, Krishnamurthy SK (2019) On the proximity of markets with integral equilibria. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1748–1755.Google Scholar
• [12] Basu S, Pollack R, Roy M-F (1998) A new algorithm to find a point in every cell defined by a family of polynomials. Caviness B, Johnson J, eds. Quantifier Elimination and Cylindrical Algebraic Decomposition (Springer, Vienna), 341–350.Crossref, Google Scholar
• [13] Birnbaum B, Devanur NR, Xiao L (2011) Distributed algorithms via gradient descent for Fisher markets. Proc. 12th ACM Conf. Electronic Commerce (EC), (ACM, New York), 127–136.Google Scholar
• [14] Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J. Econom. Theory 100(2):295–328.Crossref, Google Scholar
• [15] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2017) Competitive division of a mixed manna. Econometrica 85:1847–1871.Crossref, Google Scholar
• [16] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2019) Dividing bads under additive utilities. Soc. Choice Welf. 52:395–417.Crossref, Google Scholar
• [17] Boodaghians S, Chaudhury BR, Mehta R (2022) Polynomial time algorithms to find an approximate competitive equilibrium for chores. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2285–2302.Google Scholar
• [18] Bouveret S, Cechlárová K, Lesca J (2019) Chore division on a graph. Auton. Agent. Multi Agent Syst. 33(5):540–563.Crossref, Google Scholar
• [19] Brainard WC, Scarf HE (2005) How to compute equilibrium prices in 1891. Amer. J. Econom. Sociol. 64(1):57–83.Google Scholar
• [20] Brânzei S, Hosseini H, Miltersen PB (2015) Characterization and computation of equilibria for indivisible goods. Hoefer M, eds. Algorithmic Game Theory, SAGT 2015, Lecture Notes in Computer Science, vol. 9347 (Springer, Berlin), 244–255.Google Scholar
• [21] Brânzei S, Lv Y, Mehta R (2016) To give or not to give: Fair division for single minded valuations. Proc. 25th Internat. Joint Conf. Artificial Intelligence (IJCAI) (AAAI Press, Washington, DC), 123–129.Google Scholar
• [22] Branzei S, Mehta R, Nisan N (2018) Universal growth in production economies. Adv. Neural Inf. Process. Syst. 31:1973.Google Scholar
• [23] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6):1061–1103.Crossref, Google Scholar
• [24] Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2016a) The unreasonable fairness of maximum Nash welfare. Proc. ACM Conf. Electronic Commerce (EC) (ACM, New York), 305–322.Google Scholar
• [25] Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2021) Competitive allocation of a mixed manna. Proc. 2021 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1405–1424.Google Scholar
• [26] Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2022a) Competitive equilibrium with chores: Combinatorial algorithm and hardness. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 1106–1107.Google Scholar
• [27] Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2022b) On the existence of competitive equilibrium with chores. 13th Innovations Theoret. Comput. Sci. Conf. (ITCS 2022) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• [28] Chen X, Dai D, Du Y, Teng SH (2009) Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 273–282.Google Scholar
• [29] Cheung YK, Cole R, Devanur N (2013) Tatonnement beyond gross substitutes?: Gradient descent to the rescue. Proc. 45th Annual ACM Sympos. Theory of Comput. (STOC) (ACM, New York), 191–200.Google Scholar
• [30] Codenotti B, McCune B, Penumatcha S, Varadarajan K (2005) Market equilibrium for CES exchange economies: Existence, multiplicity, and computation. Proc. 25th Internat. Conf. Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS) (Springer, Berlin, Heidelberg), 505–516.Google Scholar
• [31] Codenotti B, Pemmaraju S, Varadarajan K (2004) The computation of market equilibria. ACM SIGACT News 35(4):23–37.Crossref, Google Scholar
• [32] Codenotti B, Saberi A, Varadarajan K, Ye Y (2006) Leontief economies encode two-player zero-sum games. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 659–667.Google Scholar
• [33] Conitzer V, Freeman R, Shah N (2017) Fair public decision making. Proc. ACM Conf. Econom. Comput. (EC) (ACM, New York), 629–646.Google Scholar
• [34] Dehghani S, Farhadi A, HajiAghayi M, Yami H (2018) Envy-free chore division for an arbitrary number of agents. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2564–2583.Google Scholar
• [35] Devanur NR, Garg J, Mehta R, Vazirani VV, Yazdanbod S (2018) A new class of combinatorial markets with covering constraints: Algorithms and applications. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2311–2325.Google Scholar
• [36] Devanur NR, Kannan R (2008) Market equilibria in polynomial time for fixed number of goods or agents. Proc. 49th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 45–53.Google Scholar
• [37] Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV (2002) Market equilibrium via a primal-dual-type algorithm. Proc. 43rd Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 389–395.Google Scholar
• [38] Echenique F, Wierman A (2012) Finding a Walrasian equilibrium is easy for a fixed number of agents. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 495.Google Scholar
• [39] Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The Pari-Mutuel method. Ann. Math. Statist. 30:165–168.Crossref, Google Scholar
• [40] Etessami K, Yannakakis M (2010) On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6):2531–2597.Crossref, Google Scholar
• [41] Farhadi A, Hajiaghayi MT (2018) On the complexity of chore division. Proc. 27th Internat. Joint Conf. Artificial Intelligence (IJCAI) (AAAI Press, Washington, DC), 226–232.Google Scholar
• [42] Feldman M, Gravin N, Lucier B (2013) Combinatorial Walrasian equilibrium. Proc. 45th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 61–70.Google Scholar
• [43] Freeman R, Shah N (2019) Recent advances in fair resource allocation (ACM EC 2019 tutorial).Google Scholar
• [44] Gardner M (1978) Aha! Insight (W.F. Freeman and Co., New York).Google Scholar
• [45] Garg J, Mehta R, Vazirani VV, Yazdanbod S (2017) Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (STOC) (ACM, New York), 890–901.Google Scholar
• [46] Garg J, Végh LA (2019) A strongly polynomial algorithm for linear exchange markets. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 54–65.Google Scholar
• [47] Garg R, Kapoor S, Vazirani VV (2004) An auction-based market equilibrium algorithm for the separable gross substitutability case. Jansen K, Khanna S, Rolim JDP, Ron D, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 128–138.Google Scholar
• [48] Gjerstad S (1996) Multiple equilibria in exchange economies with homothetic, nearly identical preference. Discussion Paper 288, Center for Economic Research, University of Minnesota, Minneapolis.Google Scholar
• [49] Goldman J, Procaccia AD (2015) Spliddit: Unleashing fair division algorithms. SIGecom Exch. 13(2):41–46.Crossref, Google Scholar
• [50] Heydrich S, van Stee R (2015) Dividing connected chores fairly. Theoret. Comput. Sci. 593:51–61.Crossref, Google Scholar
• [51] Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Political Econom. 87(2):293–314.Crossref, Google Scholar
• [52] Jain K (2007) A polynomial time algorithm for computing an arrow-debreu market equilibrium for linear utilities. SIAM J. Comput. 37(1):303–318.Crossref, Google Scholar
• [53] Jain K, Vazirani VV (2007) Eisenberg-Gale markets: Algorithms and structural properties. Proc. 39th Annual ACM Sympos. Theory Comput. (ACM, New York), 364–373.Google Scholar
• [54] Jain K, Vazirani VV, Ye Y (2005) Market equilibrium for homothetic, quasi-concave utilities and economies of scale in production. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA), (SIAM, Philadelphia), 63–71.Google Scholar
• [55] Kirman AP, Koch KJ (1986) Market excess demand in exchange economies with identical preferences and collinear endowments. Rev. Econom. Stud. 53(3):457–463.Crossref, Google Scholar
• [56] Kleinberg J, Tardos E (2006) Algorithm Design (Pearson Education, Inc, New York).Google Scholar
• [57] Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Proc. 5th ACM Conf. Electronic Commerce (EC), (ACM, New York), 125–131.Google Scholar
• [58] Megiddo N, Vazirani VV (2007) Continuity properties of equilibrium prices and allocations in linear Fisher markets. Proc. 3rd Internat. Conf. Internet Network Econom., 362–367.Google Scholar
• [59] Meunier F, Zerbib S (2019) Envy-free cake division without assuming the players prefer nonempty pieces. Israel J. Math. 234:907–925.Google Scholar
• [60] Nash J (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• [61] Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic Game Theory (Cambridge University Press, New York).Crossref, Google Scholar
• [62] Orlin JB (2010) Improved algorithms for computing Fisher’s market clearing prices. Proc. 42nd ACM Sympos. Theory Comput. (STOC) (ACM, New York), 291–300.Google Scholar
• [63] Othman A, Papadimitriou C, Rubinstein A (2016) The complexity of fairness through equilibrium. ACM Trans. Econ. Comput. 4(4):20:1–20:19.Crossref, Google Scholar
• [64] Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532.Crossref, Google Scholar
• [65] Peterson E, Su FE (2002) Four-person envy-free chore division. Math. Mag. 75(2):117–122.Crossref, Google Scholar
• [66] Plaut B, Roughgarden T (2018) Almost envy-freeness with general valuations. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2584–2603.Google Scholar
• [67] Procaccia AD, Wang J (2014) Fair enough: Guaranteeing approximate maximin shares. Proc. 15th ACM Conf. Econom. Comput. (EC) (ACM, New York), 675–692.Google Scholar
• [68] Sandomirskiy F, Segal-Halevi E (2022) Efficient fair division with minimal sharing. Oper. Res. 70(3):1762–1782.Google Scholar
• [69] Segal-Halevi E (2018) Fairly dividing a cake after some parts were burnt in the oven. Proc. 17th Internat. Conf. Autonomous Agents and MultiAgent Systems (AAMAS) (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1276–1284.Google Scholar
• [70] Shapley L, Scarf H (1974) On cores and indivisibility. J. Math. Econom. 1(1):1–23.Crossref, Google Scholar
• [71] Varian HR (1974) Equity, envy, and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• [72] Végh LA (2012) Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. Proc. 44th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 27–40.Google Scholar
• [73] Walras L, Walker DA, van Daal J (2014) Léon Walras: Elements of Theoretical Economics: Or, The Theory of Social Wealth (Cambridge University Press, Cambridge, UK).Google Scholar
• [74] Wu F, Zhang L (2007) Proportional response dynamics leads to market equilibrium. Proc. 39th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 354–363.Google Scholar
• [75] Zhang L (2011) Proportional response dynamics in the Fisher market. Theoret. Comput. Sci. 412(24):2691–2698.Google Scholar
• [76] Ziegler GM (2012) Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (Springer, New York).Google Scholar