Nash Social Welfare Approximation for Strategic Agents

References

• Abebe R, Cole R, Gkatzelis V, Hartline JD (2020) A truthful cardinal mechanism for one-sided matching. Chawla S, ed. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms, SODA 2020 (SIAM, Philadelphia), 2096–2113.Google Scholar
• Adsul B, Babu CS, Garg J, Mehta R, Sohoni MA (2010) Nash equilibria in Fisher market. Algorithmic Game Theory—Proc. Third Internat. Sympos. SAGT 2010, vol. 6386, Lecture Notes in Computer Science (Springer, Berlin), 30–41.Google Scholar
• Anari N, Gharan SO, Saberi A, Singh M (2017) Nash social welfare, matrix permanent, and stable polynomials. Papadimitriou, CH, ed. 8th Innovations Theoret. Comput. Sci. Conf., ITCS 2017, vol. 67, LIPIcs (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany), 36:1–36:12.Google Scholar
• Anari N, Mai T, Gharan SO, Vazirani VV (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Czumaj A, ed. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA 2018 (SIAM, Philadelphia), 2274–2290.Google Scholar
• Babaioff M, Lucier B, Nisan N, Leme RP (2014) On the efficiency of the Walrasian mechanism. ACM Conf. Econom. Comput., EC ’14 (ACM, New York), 783–800.Google Scholar
• Barbanel JB (2005) The Geometry of Efficient Fair Division (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Tardos E, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 557–574.Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. Oper. Res. 59(1):17–31.Link, Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2012) On the efficiency-fairness trade-off. Management Sci. 58(12):2234–2250.Link, Google Scholar
• Brams S, Taylor A (1996) Fair Division: From Cake Cutting to Dispute Resolution (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Brânzei S, Devanur NR, Rabani Y (2019) Proportional dynamics in exchange economies. Preprint, submitted July 11, https://arxiv.org/abs/1907.05037.Google Scholar
• Brânzei S, Gkatzelis V, Mehta R (2017) Nash social welfare approximation for strategic agents. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Economics Comput., EC ’17 (ACM, New York), 611–628.Google Scholar
• Brânzei S, Mehta R, Nisan N (2018) Universal growth in production economies. Bengio S, Wallach HM, Larochelle H, GraumanK, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems 31: Annual Conf. Neural Inform. Processing Systems 2018, NeurIPS 2018.Google Scholar
• Brânzei S, Chen Y, Deng X, Filos-Ratsikas A, Frederiksen SKS, Zhang J (2014) The Fisher market game: Equilibrium and welfare. Proc. Twenty-Eighth AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 587–593.Google Scholar
• Buchanan J, Tullock G, Tollison R (1980) Toward a Theory of the Rent-Seeking Society, Texas A & M University Economics Series (Texas A&M University Press, College Station, TX).Google Scholar
• Cambini A, Martein L (2009) Generalized Convexity and Optimization: Theory and Applications (Springer, Berlin).Google Scholar
• Caragiannis I, Gravin N, Huang X (2019a) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Karlin A, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput., EC 2019 (ACM, New York), 527–545.Google Scholar
• Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2019b) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):12.1–12.32.Google Scholar
• Chaudhury BR, Kavitha T, Mehlhorn K, Sgouritsa A (2020) A little charity guarantees almost envy-freeness. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms, SODA 2020 (SIAM, Philadelphia), 2658–2672.Google Scholar
• Chen N, Deng X, Zhang J (2011) How profitable are strategic behaviors in a market? Proc. 19th Annual Eur. Sympos. Algorithms—ESA 2011, vol. 6942, Lecture Notes in Computer Science (Springer, Berlin), 106–118.Google Scholar
• Chen N, Deng X, Zhang H, Zhang J (2012) Incentive ratios of Fisher markets. Proc. 39th Internat. Colloquium Automata, Languages Programming, ICALP 2004: Part II, vol. 7392:464–475, Lecture Notes in Computer Science (Springer, Berlin).Google Scholar
• Codenotti B, Varadarajan KR (2004) Efficient computation of equilibrium prices for markets with Leontief utilities. Proc. 31st Internat. Colloquium Automata, Languages Programming, ICALP 2004, vol. 3142, Lecture Notes in Computer Science (Springer, Berlin), 371–382.Google Scholar
• Cole R, Gkatzelis V (2018) Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211–1236.Crossref, Google Scholar
• Cole R, Tao Y (2016) Large market games with near optimal efficiency. Conitzer V, Bergemann D, Chen Y, eds. Proc. 2016 ACM Conf. Econom. Comput., EC ’16 (ACM, New York), 791–808.Google Scholar
• Cole R, Gkatzelis V, Goel G (2013) Mechanism design for fair division: Allocating divisible items without payments. Proc. Fourteenth ACM Conf. Electronic Commerce, EC 2013 (ACM, New York), 251–268.Google Scholar
• Cole R, Devanur NR, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput., EC ’17 (ACM, New York), 459–460.Google Scholar
• Debreu G (1952) A social equilibrium existence theorem. Proc. Natl. Acad. Sci. USA 38(10):886–893.Crossref, Google Scholar
• Devanur NR (2010) Fisher markets and convex programs. Preprint, submitted December, https://www.researchgate.net/publication/265153236_Fisher_Markets_and_Convex_Programs.Google Scholar
• Dolev D, Feitelson DG, Halpern JY, Kupferman R, Linial N (2012) No justified complaints: On fair sharing of multiple resources. Innovations Theoret. Comput. Sci. 2012 (ACM, New York), 68–75.Google Scholar
• Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The Pari-Mutuel method. Ann. Math. Statist. 30:165–168.Crossref, Google Scholar
• Fan K (1952) Fixed-point and minimax theorems in locally convex topological linear spaces. Proc. Natl. Acad. Sci. USA 38(2):121–126.Crossref, Google Scholar
• Fang H (2002) Lottery vs. all-pay auction models of lobbying. Public Choice 112(3-4):351–371.Crossref, Google Scholar
• Feldman M, Lai K, Zhang L (2009) The proportional-share allocation market for computational resources. IEEE Trans. Parallel Distributed Systems 20(8):1075–1088.Crossref, Google Scholar
• Gale D (1960) Theory of Linear Economic Models (McGraw Hill, New York).Google Scholar
• Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Czumaj A, ed. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA 2018 (SIAM, Philadelphia), 2326–2340.Google Scholar
• Garg J, Kulkarni P, Kulkarni R (2020) Approximating Nash social welfare under submodular valuations through (un)matchings. Chawla S, ed. Proc. 2020 ACM-SIAM Sympos. Discrete Algorithms, SODA 2020 (SIAM, Philadelphia), 2673–2687.Google Scholar
• Georgiou C, Pavlides T, Philippou A (2006) Network uncertainty in selfish routing. Proc. 20th Internat. Parallel Distributed Processing Sympos. (IPDPS 2006) (IEEE, New York).Google Scholar
• Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. Proc. 8th USENIX Sympos. Networked Systems Design Implementation, NSDI 2011 (USENIX Association, Berkeley, CA), 323–336.Google Scholar
• Glicksberg IL (1952) A further generalization of the Kakutani fixed-point theorem. Proc. Amer. Math. Soc. 3:170–174.Google Scholar
• Gutman A, Nisan N (2012) Fair allocation without trade. Internat. Conf. Autonomous Agents Multiagent Systems, AAMAS 2012 (IFAAMAS, Liverpool, United Kingdom), 719–728.Google Scholar
• Johari R, Tsitsiklis JN (2004) Efficiency loss in a network resource allocation game. Math. Oper. Res. 29(3):407–435.Link, Google Scholar
• Kaneko M, Nakamura K (1979) The Nash social welfare function. Econometrica 47(2):423–435.Crossref, Google Scholar
• Kelly FP (1997) Charging and rate control for elastic traffic. Eur. Trans. Telecommunication 8:33–37.Crossref, Google Scholar
• Kelly FP, Maulloo AK, Tan DKH (1998) Rate control in communication networks. J. Oper. Res. Soc. 49:237–252.Crossref, Google Scholar
• Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• Matros A (2007) Chines auctions. Unpublished manuscript, University of Pittsburgh, Pittsburgh, Pennsylvania.Google Scholar
• Moldovanu B, Sela A (2001) The optimal allocation of prizes in contests. Amer. Econom. Rev. 91(3):542–558.Crossref, Google Scholar
• Moulin H (2003) Fair Division and Collective Welfare (The MIT Press, Cambridge, MA).Crossref, Google Scholar
• Nash J (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos E, Vazirani V (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Parkes DC, Procaccia AD, Shah N (2015) Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. ACM Trans. Econom. Comput. 3(1):3.1–3.22.Google Scholar
• Plaut B (2019) Optimal Nash equilibria for bandwidth allocation. Preprint, submitted April 6, https://arxiv.org/abs/1904.03322.Google Scholar
• Robertson J, Webb W (1998) Cake-Cutting Algorithms—Be Fair If You Can(CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Roughgarden T, Tardos É (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• Shapley L, Shubik M (1977) Trade using one commodity as a means of payment. J. Political Econom. 85(5):937–968.Crossref, Google Scholar
• Young H (1995) Equity (Princeton University Press, Princeton, NJ).Crossref, Google Scholar