Extension of Additive Valuations to General Valuations on the Existence of EFX

References

• [1] Amanatidis G, Markakis E, Ntokos A (2020) Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoret. Comput. Sci. 841:94–109.Crossref, Google Scholar
• [2] Amanatidis G, Birmpas G, Filos-Ratsikas A, Voudouris AA (2022) Fair division of indivisible goods: A survey. Preprint, submitted February 15, https://arxiv.org/abs/2202.07551.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.Crossref, Google Scholar
• [4] Anari N, Mai T, Gharan SO, Vazirani VV (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 2274–2290.Google Scholar
• [5] Anari N, Oveis Gharan S, Saberi A, Singh M (2017) Nash social welfare, matrix permanent, and stable polynomials. Papadimitriou CH, ed. 8th Innovations Theoret. Comput. Sci. Conf. (ITCS) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany), 1–12.Google Scholar
• [6] Aziz H, Li B, Moulin H, Wu X (2022) Algorithmic fair allocation of indivisible items: A survey and new questions. Preprint, submitted February 17, https://arxiv.org/abs/2202.08713.Google Scholar
• [7] Barman S, Krishnamurthy SK (2017) Approximation algorithms for maximin fair division. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 18th ACM Conf. Econom. Comput. (EC) (Association for Computing Machinery, New York), 647–664.Google Scholar
• [8] Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Tardos E, Elkind E, Vohra RV, eds. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 557–574.Google Scholar
• [9] Berger B, Cohen A, Feldman M, Fiat A (2022) Almost full EFX exists for four agents. Proc. Conf. AAAI Artificial Intelligence 36:4826–4833.Crossref, Google Scholar
• [10] Bouveret S, Lemaître M (2016) Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents Multi-Agent Systems 30(2):259–290.Crossref, Google Scholar
• [11] Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [12] Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [13] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
• [14] Budish E, Cachon GP, Kessler JB, Othman A (2017) Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Oper. Res. 65(2):314–336.Link, Google Scholar
• [15] Caragiannis I, Gravin N, Huang X (2019) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Karlin AR, Immorlica N, Johari R, eds. Proc. 20th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 527–545.Google Scholar
• [16] Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2016) The unreasonable fairness of maximum Nash welfare. Conitzer V, Bergemann D, Chen Y, eds. Proc. 2016 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 305–322.Google Scholar
• [17] 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):1–32.Crossref, Google Scholar
• [18] Chaudhury BR, Garg J, Mehlhorn K (2020) EFX exists for three agents. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. 21st ACM Conf. Econom. Comput. (EC) (Association for Computing Machinery, New York), 1–19.Google Scholar
• [19] Chaudhury BR, Kavitha T, Mehlhorn K, Sgouritsa A (2020) A little charity guarantees almost envy-freeness. Chawla S, ed. Proc. 31st Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics), 2658–2672.Google Scholar
• [20] Chaudhury BR, Garg J, Mehlhorn K, Mehta R, Misra P (2021) Improving EFX guarantees through rainbow cycle number. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 310–311.Google Scholar
• [21] Chaudhury BR, Cheung YK, Garg J, Garg N, Hoefer M, Mehlhorn K (2018) On fair division for indivisible items. Ganguly S, Pandya P, eds. Proc. 38th IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany), 1–17.Google Scholar
• [22] Cole R, Gkatzelis V (2018) Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211–1236.Crossref, Google Scholar
• [23] Cole R, Devanur N, 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. 18th ACM Conf. Econom. Comput. (EC) (Association for Computing Machinery, New York), 459–460.Google Scholar
• [24] Farhadi A, Hajiaghayi M, Latifian M, Seddighin M, Yami H (2021) Almost envy-freeness, envy-rank, and Nash social welfare matchings. Proc. Conf. AAAI Artificial Intelligence 35:5355–5362.Crossref, Google Scholar
• [25] Garg J, Taki S (2020) An improved approximation algorithm for maximin shares. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 379–380.Google Scholar
• [26] Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2326–2340.Google Scholar
• [27] Garg J, Kulkarni P, Kulkarni R (2020) Approximating Nash social welfare under submodular valuations through (un)matchings. Chawla S, ed. Proc. Fourteenth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 2673–2687.Google Scholar
• [28] Ghodsi M, Hajiaghayi M, Seddighin M, Seddighin S, Yami H (2018) Fair allocation of indivisible goods: Improvements and generalizations. Tardos E, Elkind E, Vohra RV, eds. Proc. 19th ACM Conf. Econom. Comput. (EC) (Association for Computing Machinery, New York), 539–556.Google Scholar
• [29] Goldman JR, Procaccia AD (2014) Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges 13(2):41–46.Crossref, Google Scholar
• [30] Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):1–27.Crossref, Google Scholar
• [31] Lee E (2017) APX-hardness of maximizing Nash social welfare with indivisible items. Inform. Processing Lett. 122:17–20.Crossref, Google Scholar
• [32] Li W, Vondrák J (2022) A constant-factor approximation algorithm for Nash social welfare with submodular valuations. 2021 IEEE 62nd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 25–36.Google Scholar
• [33] Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Proc. 5th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 125–131.Google Scholar
• [34] Mahara R (2020) Existence of EFX for two additive valuations. Preprint, submitted August 20, https://arxiv.org/abs/2008.08798.Google Scholar
• [35] Mahara R (2021) Extension of additive valuations to general valuations on the existence of EFX. Mutzel P, Pagh R, Herman G, eds. 29th Annual Eur. Sympos. Algorithms (ESA 2021) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik).Google Scholar
• [36] Moulin H (2004) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Google Scholar
• [37] Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discrete Math. 34(2):1039–1068.Crossref, Google Scholar
• [38] Robertson J, Webb W (1998) Cake-cutting algorithms: Be fair if you can. Working paper.Google Scholar
• [39] Steinhaus H (1948) The problem of fair division. Econometrica 16(1):101–104.Google Scholar