Satiation in Fisher Markets and Approximation of Nash Social Welfare

References

• [1] Allouch N, Van CL (2007) Walras and dividends equilibrium with possibly satiated consumers. J. Math. Econom. 44(9):907–918.Google Scholar
• [2] Anari N, Gharan SO, Saberi A, Singh M (2017) Nash social welfare, matrix permanent, and stable polynomials. Papadimitriou CH, ed. Proc. 8th Sympos. Innovations Theoret. Comput. Sci. (ITCS), 36 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany), 1–12.Google Scholar
• [3] Anari N, Mai T, Gharan SO, Vazirani V (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Czumaj A, ed. Proc. 29th Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2274–2290.Google Scholar
• [4] Andelman N, Mansour Y (2004) Auctions with budget constraints. Hagerup T, Katajainen J, eds. Proc. 9th Scandinavian Workshop Algorithm Theory (SWAT) (Springer, New York), 26–38.Google Scholar
• [5] Aumann R, Dreze J (1986) Values of markets with satiation or fixed prices. Econometrica 54(6):1271–1318.Crossref, Google Scholar
• [6] Azar Y, Birnbaum B, Karlin A, Mathieu C, Nguyen CT (2008) Improved approximation algorithms for budgeted allocations. Aceto L, Damgård I, Ann Goldberg L, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I, eds. Proc. 35th Internat. Colloquium Automata Languages Programming (ICALP) (Springer, New York), 186–197.Google Scholar
• [7] Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Tardos E, Elkind E, Vohra R, eds. Proc. 19th Conf. Econom. Comput. (EC) (ACM, New York), 557–574.Google Scholar
• [8] Bei X, Garg J, Hoefer M, Mehlhorn K (2019) Earning and utility limits in Fisher markets. ACM Trans. Econom. Comput. 7(2):10:1–10:35.Google Scholar
• [9] Brainard W, Scarf H (2005) How to compute equilibrium prices in 1891. Amer. J. Econom. Sociol. 64(1):57–83.Google Scholar
• [10] Buchbinder N, Jain K, Naor J (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Arge L, Hoffmann M, Welzl E, eds. Proc. 15th Eur. Sympos. Algorithms (ESA) (Springer, New York), 253–264.Google Scholar
• [11] Buchfuhrer D, Dughmi S, Fu H, Kleinberg R, Mossel E, Papadimitriou C, Schapira M, Singer Y, Umans C (2010) Inapproximability for VCG-based combinatorial auctions. Charikar M, ed. Proc. 21st Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 518–536.Google Scholar
• [12] Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2019) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):12:1–12:32.Google Scholar
• [13] Chakrabarty D, Goel G (2010) On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput. 39(6):2189–2211.Crossref, Google Scholar
• [14] Chaudhury BR, Cheung YK, Garg J, Garg N, Hoefer M, Mehlhorn K (2022) Fair division of indivisible goods for a class of concave valuations. J. Artificial Intelligence Res. 74:111–142.Crossref, Google Scholar
• [15] Chlebík M, Chlebíková J (2003) Approximation hardness for small occurrence instances of NP-hard problems. Petreschi R, Persiano G, Silvestri R, eds. Proc. 5th Internat. Conf. Algorithms Complexity (CIAC) (Springer, New York), 152–164.Google Scholar
• [16] Chvátal V (1983) Linear Programming (W. H. Freeman and Company, Alexandria, VA).Google Scholar
• [17] Cole R, Gkatzelis V (2018) Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211–1236.Crossref, Google Scholar
• [18] Cole R, Devanur N, Gkatzelis V, Jain K, Mai T, Vazirani V, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 18th Conf. Econom. Comput. (EC) (ACM, New York), 459–460.Google Scholar
• [19] Cottle R, Pang JS, Stone R (1992) The Linear Complementarity Problem (Academic Press, Boston).Google Scholar
• [20] Darmann A, Schauer J (2015) Maximizing Nash product social welfare in allocating indivisible goods. Eur. J. Oper. Res. 247(2):548–559.Crossref, Google Scholar
• [21] Devanur N, Garg J, Végh L (2016) A rational convex program for linear Arrow-Debreu markets. ACM Trans. Econom. Comput. 5(1):6:1–6:13.Google Scholar
• [22] Devanur N, Jain K, Sivan B, Wilkens C (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):7:1–7:41.Crossref, Google Scholar
• [23] Devanur N, Papadimitriou C, Saberi A, Vazirani V (2008) Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5):22:1–22:18.Crossref, Google Scholar
• [24] Duan R, Mehlhorn K (2015) A combinatorial polynomial algorithm for the linear Arrow-Debreu market. Inform. Comput. 243:112–132.Crossref, Google Scholar
• [25] 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 (SODA) (SIAM, Philadelphia), 90–106.Google Scholar
• [26] Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The Pari-Mutuel method. Ann. Math. Statist. 30(1):165–168.Crossref, Google Scholar
• [27] Fearnley J, Goldberg P, Hollender A, Savani R (2021) The complexity of gradient descent: CLS = PPAD ∩ PLS. Khuller S, Williams VV, eds. Proc. 53rd Sympos. Theory Comput. (STOC) (ACM, New York), 46–59.Google Scholar
• [28] Feldman M, Gravin N, Lucier B (2016) Combinatorial Walrasian equilibrium. SIAM J. Comput. 45(1):29–48.Crossref, Google Scholar
• [29] Freeman R, Zahedi S, Conitzer V (2017) Fair and efficient social choice in dynamic settings. Sierra C, ed. Proc. 26th Internat. Joint Conf. Artificial Intelligence (IJCAI, California), 4580–4587.Google Scholar
• [30] Gale D (1960) Theory of Linear Economic Models (McGraw Hill, New York).Google Scholar
• [31] Garg J, Végh L (2019) A strongly polynomial algorithm for linear exchange markets. Charikar M, Cohen E, eds. Proc. 51st Sympos. Theory Comput. (STOC) (ACM, New York), 54–65.Google Scholar
• [32] Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Czumaj A, ed. Proc. 29th Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 2326–2340.Google Scholar
• [33] Garg J, Mehta R, Vazirani V (2014) Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions. Shmoys DB, ed. Proc. 46th Sympos. Theory Comput. (STOC) (ACM, New York), 525–534.Google Scholar
• [34] Garg J, Mehta R, Vazirani V (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
• [35] Garg J, Mehta R, Sohoni M, Vazirani V (2015) A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. SIAM J. Comput. 44(6):1820–1847.Crossref, Google Scholar
• [36] 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
• [37] Kajii A (1996) How to discard non-satiation and free-disposal with paper money. J. Math. Econom. 25:75–84.Crossref, Google Scholar
• [38] Kalaitzis C (2016) An improved approximation guarantee for the maximum budgeted allocation problem. Krauthgamer R, ed. Proc. 27th Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1048–1066.Google Scholar
• [39] Kaneko M, Nakamura K (1979) The Nash social welfare function. Econometrica 47(2):423–436.Crossref, Google Scholar
• [40] Kelly F (1997) Charging and rate control for elastic traffic. Eur. Trans. Telecomm. 8:33–37.Crossref, Google Scholar
• [41] Konovalov A (2005) The core of an economy with satiation. Econom. Theory 25:711–719.Crossref, Google Scholar
• [42] Lee E (2017) APX-hardness of maximizing Nash social welfare with indivisible items. Inform. Processing Lett. 122:17–20.Crossref, Google Scholar
• [43] Mas-Colell A (1992) Equilibrium theory with possibly satiated preferences. Majumdar M, ed. Equilibrium and Dynamics (Palgrave Macmillan, London), 201–213.Crossref, Google Scholar
• [44] Mehta A (2012) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• [45] Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• [46] Moulin H (2003) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Crossref, Google Scholar
• [47] Nash J (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• [48] Nguyen N, Nguyen TT, Roos M, Rothe J (2014) Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Autonomous Agents Multi-Agent Systems 28(2):256–289.Crossref, Google Scholar
• [49] Orlin J (2010) Improved algorithms for computing Fisher’s market clearing prices. Schulman LJ, ed. Proc. 42nd Sympos. Theory Comput. (STOC) (ACM, New York), 291–300.Google Scholar
• [50] Ramezani S, Endriss U (2010) Nash social welfare in multiagent resource allocation. David E, Gerding E, Sarne D, Shehory O, eds. Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets. AMEC TADA 2009, Lecture Notes in Business Information Processing, vol. 59 (Springer, Berlin), 117–131.Crossref, Google Scholar
• [51] Roughgarden T, Talgam-Cohen I (2015) Why prices need algorithms. Roughgarden T, Feldman M, Schwarz M, eds. Proc. 16th Conf. Econom. Comput. (EC) (ACM, New York), 19–36.Google Scholar
• [52] Shmyrev V (2009) An algorithm for finding equilibrium in the linear exchange model with fixed budgets. J. Appl. Indust. Math. 3(4):505–518.Crossref, Google Scholar
• [53] Srinivasan A (2008) Budgeted allocations in the full-information setting. Goel A, Jansen K, Rolim JDP, Rubinfeld R, eds. Proc. 11th Workshop Approximation Algorithms Combinatorial Optim. Problems (APPROX) (Springer, Boston), 247–253.Google Scholar
• [54] Todd M (1976) Orientation in complementary pivot algorithms. Math. Oper. Res. 1(1):54–66.Link, Google Scholar
• [55] Végh L (2014) Concave generalized flows with applications to market equilibria. Math. Oper. Res. 39(2):573–596.Link, Google Scholar
• [56] Walras L (1874) Éléments d’économie politique pure, ou théorie de la richesse sociale (Lausanne, Paris).Google Scholar
• [57] Ye Y (2007) Exchange market equilibria with Leontief’s utility: Freedom of pricing leads to rationality. Theoret. Comput. Sci. 378(2):134–142.Crossref, Google Scholar