A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna

References

• [1] Azrieli Y, Shmaya E (2014) Rental harmony with roommates. J. Econom. Theory 153:128–137.Crossref, Google Scholar
• [2] Bataille N, Lemaître M, Verfaillie G (1999) Efficiency and fairness when sharing the use of a satellite. Proc. Fifth Internat. Sympo. Artificial Intelligence Robotics Automation Space, 465–470.Google Scholar
• [3] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaia E (2017) Competitive division of a mixed manna. Econometrica 85(6):1847–1871.Crossref, Google Scholar
• [4] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaia E (2019) Dividing bads under additive utilities. Soc. Choice Welfare 52(3):395–417.Crossref, Google Scholar
• [5] Brainard W, Scarf H (2000) How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper 1270, New Haven, CT.Google Scholar
• [6] Brams SJ, Taylor AD (1996) Fair Division—From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [7] Branzei S, Sandomirskiy F (2019) Algorithms for competitive division of chores. Preprint, submitted July 3, https://arxiv.org/abs/1907.01766.Google Scholar
• [8] Budish B, Cantillon E (2010) The multi-unit assignment problem: Theory and evidence from course allocation at Harvard. Amer. Econom. Rev. 102(5):2237–2271.Crossref, Google Scholar
• [9] Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2020) Dividing bads is harder than dividing goods: On the complexity of fair and efficient division of chores. Preprint, submitted August 1, https://arxiv.org/abs/2008.00285.Google Scholar
• [10] Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2021) Competitive allocation of a mixed manna. Marx D, ed. Proc. 32nd Sympos. Discrete Algorithms (SIAM, Philadelphia), 1405–1424.Google Scholar
• [11] Chen X, Teng S (2009) Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria. Dong Y, Du D-Z, Ibarra OH, eds. Proc. 20th Internat. Sympos. Algorithms Comput. (Springer, New York), 647–656.Google Scholar
• [12] Chen X, Paparas D, Yannakakis M (2017) The complexity of non-monotone markets. J. ACM 64(3):20:1–20:56.Google Scholar
• [13] Chen X, Dai D, Du Y, Teng S (2009) Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Proc. 50th Sympos. Foundations Comput. Sci. (IEEE, Atlanta), 273–282.Google Scholar
• [14] Chvátal V (1983) Linear Programming (W.H. Freeman and Company, New York).Google Scholar
• [15] Cottle R, Pang JS, Stone R (1992) The Linear Complementarity Problem (Academic Press, Boston).Google Scholar
• [16] Dantzig G (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [17] Devanur N, Kannan R (2008) Market equilibria in polynomial time for fixed number of goods or agents. Proc. 49th Sympos. Foundations Comput. Sci. (IEEE, Philadelphia), 45–53.Google Scholar
• [18] Devanur N, Garg J, Végh L (2016) A rational convex program for linear Arrow-Debreu markets. ACM Trans. Econom. Comput. 5(1):1–13.Crossref, Google Scholar
• [19] Devanur N, Papadimitriou C, Saberi A, Vazirani V (2008) Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5):1–18.Crossref, Google Scholar
• [20] Duan R, Mehlhorn K (2015) A combinatorial polynomial algorithm for the linear Arrow-Debreu market. Inform. Comput. 243:112–132.Crossref, Google Scholar
• [21] Duan R, Garg J, Mehlhorn K (2016) An improved combinatorial polynomial algorithm for the linear Arrow-Debreu market. Krauthgamer R, ed. Proc. 27th Sympos. Discrete Algorithms (SIAM, Philadelphia), 90–106.Google Scholar
• [22] Eaves BC (1976) A finite algorithm for the linear exchange model. J. Math. Econom. 3(2):197–203.Crossref, Google Scholar
• [23] Eisenberg E (1961) Aggregation of utility functions. Management Sci. 7(4):337–350.Link, Google Scholar
• [24] Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The Pari-Mutuel method. Ann. Math. Statist. 30(1):165–168.Crossref, Google Scholar
• [25] Etkin R, Parekh A, Tse D (2007) Spectrum sharing for unlicensed bands. Proc. First IEEE Sympos. New Frontiers Dynamic Spectrum Access Networks. IEEE J. Selected Areas Commun. 25:517–528.Google Scholar
• [26] Garg J, Kannan R (2015) Markets with production: A polynomial time algorithm and a reduction to pure exchange. Roughgarden T, Feldman M, Schwarz M, eds. Proc. 16th Conf. Econom. Comput. (ACM, New York), 733–749.Google Scholar
• [27] Garg J, McGlaughlin P (2020) Computing competitive equilibria with mixed manna. Seghrouchni AEF, Sukthankar G, An B, Yorke–Smith N, eds. Proc. 19th Conf. Autonomous Agents Multi-Agent Systems (International Foundation for Autonomous Agents and Multiagent Systems), 420–428.Google Scholar
• [28] Garg J, Vazirani VV (2014) On computability of equilibria in markets with production. Chekuri C, ed. Proc. 25th Sympos. Discrete Algorithms (SIAM, Philadelphia), 1329–1340.Google Scholar
• [29] Garg J, Végh LA (2019) A strongly polynomial algorithm for linear exchange markets. Charikar M, Cohen E, eds. Proc. 51st Sympos. Theory Comput. (ACM, New York), 54–65.Google Scholar
• [30] Garg J, Mehta R, Vazirani VV (2018) Substitution with satiation: A new class of utility functions and a complementary pivot algorithm. Math. Oper. Res. 43(3):996–1024.Link, Google Scholar
• [31] Garg J, Mehta R, Sohoni M, Vazirani VV (2015) A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. SIAM J. Comput. 44(6):1820–1847.Crossref, Google Scholar
• [32] Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. Proc. Eighth USENIX Conf. Networked Systems Design Implementation, 323–336.Google Scholar
• [33] Goldman JR, Procaccia AD (2014) Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13(2):41–46.Crossref, Google Scholar
• [34] Hansen KA, Lund TB (2018) Computational complexity of proper equilibrium. Tardos E, Elkind E, Vohra R, eds. Proc. 19th Conf. Econom. Comput. (ACM, New York), 113–130.Google Scholar
• [35] Jain K (2007) A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. SIAM J. Comput. 37(1):306–318.Crossref, Google Scholar
• [36] Klee V, Minty G (1972) How good is the Simplex algorithm? Shisha O, ed. Inequalities III (Academic Press, Boston), 159–175.Google Scholar
• [37] Koller D, Megiddo N, von Stengel B (1994) Fast algorithms for finding randomized strategies in game trees. Leighton FT, Goodrich MT, eds. Proc. 26th Sympos. Theory Comput. (ACM, New York), 750–759.Google Scholar
• [38] Lemke C (1965) Bimatrix equilibrium points and mathematical programming. Management Sci. 11(7):681–689.Link, Google Scholar
• [39] Lemke C, Howson J (1964) Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12(2):413–423.Crossref, Google Scholar
• [40] Moulin H (2003) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Crossref, Google Scholar
• [41] Moulin H (2019) Fair division in the internet age. Annual Rev. Econom. 11:407–441.Crossref, Google Scholar
• [42] Orlin J (2010) Improved algorithms for computing Fisher’s market clearing prices. Schulman LJ, ed. Proc. 42nd Sympos. Theory Comput. (ACM, New York), 291–300.Google Scholar
• [43] Pratt JW, Zeckhauser RJ (1990) The fair and efficient division of the Winsor family silver. Management Sci. 36(11):1293–1301.Link, Google Scholar
• [44] Robertson J, Webb W (1998) Cake-Cutting Algorithms: Be Fair if You Can (AK Peters, Natick, MA).Crossref, Google Scholar
• [45] Savani R (2006) Finding Nash equilibria of bimatrix games. Unpublished PhD thesis, London School of Economics and Political Science, London.Google Scholar
• [46] Savani R, von Stengel B (2006) Hard-to-solve bimatrix games. Econometrica 74(2):397–429.Crossref, Google Scholar
• [47] Sönmez T, Unver U (2010) Course bidding at business schools. Internat. Econom. Rev. 51(1):99–123.Crossref, Google Scholar
• [48] Sørensen TB (2012) Computing a proper equilibrium of a bimatrix game. Faltings B, Leyton–Brown K, Ipeirotis P, eds. Proc. 13th Conf. Econom. Comput. (ACM, New York), 916–928.Google Scholar
• [49] Steinhaus H (1948) The problem of fair division. Econometrica 16:101–104.Google Scholar
• [50] Su FE (1999) Rental harmony: Sperner’s lemma in fair division. Amer. Math. Monthly 106(10):930–942.Crossref, Google Scholar
• [51] Todd M (1976) Orientation in complementary pivot algorithms. Math. Oper. Res. 1(1):54–66.Link, Google Scholar
• [52] Varian H (1974) Equity, envy and efficiency. J. Econom. Theory 29(2):217–244.Google Scholar
• [53] Vazirani V, Yannakakis M (2011) Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58(3):1–25.Crossref, Google Scholar
• [54] Végh LA (2014) Concave generalized flows with applications to market equilibria. Math. Oper. Res. 39(2):573–596.Link, Google Scholar
• [55] Végh LA (2017) A strongly polynomial algorithm for generalized flow maximization. Math. Oper. Res. 42(1):179–211.Link, Google Scholar
• [56] Vossen TW (2002) Fair allocation concepts in air traffic management. Unpublished PhD thesis, University of Maryland, College Park, MD.Google Scholar
• [57] Walras L (1874) Éléments d’économie politique pure, ou théorie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth) (Lausanne, Paris), (1899, 4th ed.; 1926, rev ed., 1954, Engl. transl.).Google Scholar
• [58] Ye Y (2007) Exchange market equilibria with Leontief’s utility: Freedom of pricing leads to rationality. Theoretical Comput. Sci. 378(2):134–142.Crossref, Google Scholar