EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number

References

• Akrami H, Garg J (2024) Breaking the 3/4 barrier for approximate maximin share. Proc. 2024 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 74–91.Google Scholar
• Akrami H, Rezvan R, Seddighin M (2022) An EF2X allocation protocol for restricted additive valuations. Proc. Thirty-First Internat. Joint Conf. Artificial Intelligence, IJCAI 2022 (ijcai.org), 17–23.Google Scholar
• Akrami H, Garg J, Sharma E, Taki S (2023) Simplification and improvement of MMS approximation. Proc. Thirty-Second Internat. Joint Conf. Artificial Intelligence, IJCAI 2023 (AAAI Press, Palo Alto, CA).Google Scholar
• Alon N, Krivelevich M (2021) Divisible subdivisions. J. Graph Theory 98(4):623–629.Crossref, Google Scholar
• Alon N, Spencer J (2016) The Probabilistic Method, 4th ed. (John Wiley & Sons, Hoboken, NJ).Google Scholar
• 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
• Amanatidis G, Markakis E, Nikzad A, Saberi A (2017) Approximation algorithms for computing maximim share allocations. ACM Trans. Algorithms 13(4):1–28.Google Scholar
• Aziz H, Gaspers S, Mackenzie S, Walsh T (2015) Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence 227:71–92.Crossref, Google Scholar
• Baklanov A, Garimidi P, Gkatzelis V, Schoepflin D (2021) Achieving proportionality up to the maximin item with indivisible goods. Thirty-Fifth AAAI Conf. Artificial Intelligence, AAAI 2021 (AAAI Press, Palo Alto, CA), 5143–5150.Google Scholar
• Barman S, Krishnamurthy SK (2017) Approximation algorithms for maximin fair division. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput., EC ’17 (ACM, New York), 647–664.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
• Berendsohn BA, Boyadzhiyska S, Kozma L (2022) Fixed-point cycles and EFX allocations. Szeider S, Ganian R, Silva A, eds. 47th Internat. Sympos. Mathematical Foundations Comput. Science, MFCS, LIPIcs, vol. 241, 17:1–17:13.Google Scholar
• Berger B, Cohen A, Feldman M, Fiat A (2022) (Almost full) EFX exists for four agents (and beyond). Proc. 36th Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 4826–4833.Google Scholar
• 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
• Brams SJ, Taylor AD (1996) Fair Division—From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brams SJ, Kilgour DM, Klamler C (2017) Maximin envy-free division of indivisible items. Group Decision Negotiation 26(1):115–131.Crossref, Google Scholar
• Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
• Budish E, 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
• Caragiannis I, Gravin N, Huang X (2019) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Proc. 20th ACM Conf. Econom. Comput. (ACM, New York), 527–545.Google Scholar
• 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. EC ’16 (ACM, New York), 305–322.Google Scholar
• Chaudhury BR, Garg J, Mehlhorn K (2020) EFX exists for three agents. Biro P, Hartline JD, Ostrovsky M, Procaccia AD, eds. EC ’20: 21st ACM Conf. Econom. Comput. (ACM, New York), 1–19.Google Scholar
• Chaudhury BR, Kavitha T, Mehlhorn K, Sgouritsa A (2021a) A little charity guarantees almost envy-freeness. SIAM J. Comput. 50(4):1336–1358.Crossref, Google Scholar
• Chaudhury BR, Garg J, Mehlhorn K, Mehta R, Misra P (2021b) Improving EFX guarantees through rainbow cycle number. Bior P, Chawla S, Echenique F, eds. EC ’21: 22nd ACM Conf. Econom. Comput. (ACM, New York), 310–311.Google Scholar
• Etkin R, Parekh A, Tse D (2005) Spectrum sharing for unlicensed bands. First IEEE Internat. Sympos. New Frontiers Dynam. Spectrum Access Networks (IEEE, Piscataway, NJ), 251–258.Google Scholar
• Garg J, Taki S (2021) An improved approximation algorithm for maximin shares. Artificial Intelligence 300:103547.Crossref, Google Scholar
• Garg J, McGlaughlin P, Taki S (2019) Approximating maximin share allocations. Fineman JT, Mitzenmacher M, eds. 2nd Sympos. Simplicity Algorithms, SOSA 2019, vol. 69 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 20:1–20:11.Google Scholar
• Ghodsi M, Hajiaghayi MT, Seddighin M, Seddighin S, Yami H (2018) Fair allocation of indivisible goods: Improvements and generalizations. Tardos E, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 539–556.Google Scholar
• Halpern D, Procaccia AD, Psomas A, Shah N (2020) Fair division with binary valuations: One rule to rule them all. Chen X, Gravin N, Hoefer M, Mehta R, eds. Web Internet Econom. 16th Internat. Conf. WINE 2020, vol. 12495 (Springer, New York), 370–383.Google Scholar
• Jahan SC, Seddighin M, Seyed-Javadi SM, Sharifi M (2023) Rainbow cycle number and EFX allocations: (Almost) closing the gap. Proc. Thirty-Second Internat. Joint Conf. Artificial Intelligence, IJCAI 2023 (ijcai.org), 2572–2580.Google Scholar
• Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):1–27.Google Scholar
• Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Breese JS, Feigenbaum J, Seltzer MI, eds. Proc. 5th ACM Conf. Electronic Commerce (EC-2004) (ACM, New York), 125–131.Google Scholar
• Mahara R (2021) Extension of additive valuations to general valuations on the existence of EFX. Mutzel P, Pagh R, Herman G, eds. 29th Annu. Eur. Sympos. Algorithms, ESA 2021 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 66:1–66:15.Google Scholar
• Mészáros T, Steiner R (2021) Zero sum cycles in complete digraphs. Eur. J. Combin. 98:103399.Crossref, Google Scholar
• Moulin H (2019) Fair division in the internet age. Annual Rev. Econom. 11(1):407–441.Crossref, Google Scholar
• Murhekar A, Garg J (2021) On fair and efficient allocations of indivisible goods. Thirty-Fifth AAAI Conf. Artificial Intelligence, AAAI 2021 (AAAI Press, Palo Alto, CA), 5595–5602.Google Scholar
• Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discrete Math. 34(2):1039–1068.Crossref, Google Scholar
• Pratt JW, Zeckhauser RJ (1990) The fair and efficient division of the Winsor family silver. Management Sci. 36(11):1293–1301.Link, Google Scholar
• Procaccia AD (2020) Technical perspective: An answer to fair division’s most enigmatic question. Comm. ACM 63(4):118.Google Scholar
• Steinhaus H (1948) The problem of fair division. Econometrica 16(1):101–104.Google Scholar
• Vossen TW (2002) Fair allocation concepts in air traffic management. Unpublished PhD thesis, University of Maryland, College Park.Google Scholar