Envy-Freeness up to Any Good Allocations on Graphs

References

• [1] Afshinmehr M, Danaei A, Kazemi M, Mehlhorn K, Rathi N (2025) EFX allocations and orientations on bipartite multi-graphs: A complete picture. Das S, Nowé A, Vorobeychik Y, eds. Proc. 24th Internat. Conf. Autonomous Agents Multiagent Systems AAMAS 2025 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 32–40.Google Scholar
• [2] Akrami H, Rathi N (2025) Epistemic EFX allocations exist for monotone valuations. Walsh T, Shah J, Kolter Z, eds. AAAI’25/IAAI’25/EAAI’25 Proc. 39th AAAI Conf. Artificial Intelligence 37th Conf. Innovative Appl. Artificial Intelligence 15th Sympos. Ed. Adv. Artificial Intelligence (AAAI Press, Washington, DC), 13520–13528.Google Scholar
• [3] Akrami H, Rezvan R, Seddighin M (2022) An EF2X allocation protocol for restricted additive valuations. Raedt LD, ed. Proc. Thirty-First Internat. Joint Conf. Artificial Intelligence IJCAI 2022 (IJCAI), 17–23.Google Scholar
• [4] Akrami H, Alon N, Chaudhury BR, Garg J, Mehlhorn K, Mehta R (2025) EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. Oper. Res. 73(2):738–751.Link, Google Scholar
• [5] Amanatidis G, Filos-Ratsikas A, Sgouritsa A (2024) Pushing the frontier on approximate EFX allocations. Bergemann D, Kleinberg R, Sabán D, eds. Proc. 25th ACM Conf. Econom. Comput. EC 2024 (Association for Computing Machinery, New York), 1268–1286.Google Scholar
• [6] Amanatidis G, Markakis E, Ntokos A (2020) Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. 841:94–109.Crossref, Google Scholar
• [7] Amanatidis G, Birmpas G, Filos-Ratsikas A, Hollender A, Voudouris AA (2021) Maximum Nash welfare and other stories about EFX. Theor. Comput. Sci. 863:69–85.Crossref, Google Scholar
• [8] Amanatidis G, Aziz H, Birmpas G, Filos-Ratsikas A, Li B, Moulin H, Voudouris AA, Wu X (2023) Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence 322:103965.Crossref, Google Scholar
• [9] Babaioff M, Ezra T, Feige U (2021) Fair and truthful mechanisms for dichotomous valuations. Thirty-Fifth AAAI Conf. Artificial Intelligence AAAI 2021 (AAAI Press, Washington, DC), 5119–5126.Google Scholar
• [10] Berendsohn BA, Boyadzhiyska S, Kozma L (2022) Fixed-point cycles and approximate EFX allocations. Szeider S, Ganian R, Silva A, eds. 47th Internat. Sympos. Math. Foundations Comput. Sci. MFCS 2022, LIPIcs, vol. 241 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 17:1–17:13.Google Scholar
• [11] Berger B, Cohen A, Feldman M, Fiat A (2022) Almost full EFX exists for four agents. Thirty-Sixth AAAI Conf. Artificial Intelligence AAAI 2022 Thirty-Fourth Conf. Innovative Appl. Artificial Intelligence IAAI 2022 Twelfth Sympos. Ed. Adv. Artificial Intelligence EAAI 2022 (AAAI Press, Washington, DC), 4826–4833.Google Scholar
• [12] Bhaskar U, Pandit Y (2025) Extending EFX allocations to further multi-graph classes. Aiswarya C, Mehta R, Roy S, eds. 45th IARCS Annu. Conf. Foundations Software Tech. Theor. Comput. Sci. FSTTCS 2025, LIPIcs, vol. 360 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 15:1–15:18.Google Scholar
• [13] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Polit. Econom. 119(6):1061–1103.Crossref, Google Scholar
• [14] Caragiannis I, Gravin N, Huang X (2019a) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Karlin AR, Immorlica N, Johari R, eds. Proc. 2019 ACM Conf. Econom. Comput. EC 2019 (Association for Computing Machinery, New York), 527–545.Google Scholar
• [15] Caragiannis I, Garg J, Rathi N, Sharma E, Varricchio G (2023) New fairness concepts for allocating indivisible items. Proc. Thirty-Second Internat. Joint Conf. Artificial Intelligence IJCAI 2023 (IJCAI), 2554–2562.Google Scholar
• [16] 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.Google Scholar
• [17] Chan H, Chen J, Li B, Wu X (2019) Maximin-aware allocations of indivisible goods. Kraus S, ed. Proc. Twenty-Eighth Internat. Joint Conf. Artificial Intelligence IJCAI 2019 (IJCAI), 137–143.Google Scholar
• [18] Chaudhury BR, Garg J, Mehlhorn K (2024a) EFX exists for three agents. J. ACM 71(1):4.Crossref, Google Scholar
• [19] Chaudhury BR, Kavitha T, Mehlhorn K, Sgouritsa A (2021) A little charity guarantees almost envy-freeness. SIAM J. Comput. 50(4):1336–1358.Crossref, Google Scholar
• [20] Chaudhury BR, Garg J, Mehlhorn K, Mehta R, Misra P (2024b) Improving envy freeness up to any good guarantees through rainbow cycle number. Math. Oper. Res. 49(4):2323–2340.Link, Google Scholar
• [21] Chen X, Deng X, Teng S (2009) Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3):14.Crossref, Google Scholar
• [22] Christodoulou G, Koutsoupias E, Kovács A (2021) On the Nisan-Ronen conjecture. 62nd IEEE Annu. Sympos. Foundations Comput. Sci. FOCS 2021 (IEEE, Piscataway, NJ), 839–850.Google Scholar
• [23] Christodoulou G, Koutsoupias E, Kovács A (2023) A proof of the Nisan-Ronen conjecture. Saha B, Servedio RA, eds. Proc. 55th Annu. ACM Sympos. Theory Comput. STOC 2023 (Association for Computing Machinery, New York), 672–685.Google Scholar
• [24] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• [25] Deligkas A, Eiben E, Goldsmith T, Korchemna V (2025) EF1 and EFX orientations. Proc. Thirty-Fourth Internat. Joint Conf. Artificial Intelligence IJCAI 2025 (IJCAI, Montreal and Guangzhou, China), 56–63.Google Scholar
• [26] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (WH Freeman, New York).Google Scholar
• [27] Gorantla P, Marwaha K, Velusamy S (2023) Fair allocation of a multiset of indivisible items. Bansal N, Nagarajan V, eds. Proc. 2023 ACM-SIAM Sympos. Discrete Algorithms SODA 2023 (SIAM, Philadelphia), 304–331.Google Scholar
• [28] Gourvès L, Monnot J, Tlilane L (2014) Near fairness in matroids. Schaub T, Friedrich G, O’Sullivan B, eds. ECAI 2014 21st Eur. Conf. Artificial Intelligence Prestigious Appl. Intelligent Systems PAIS 2014, Frontiers in Artificial Intelligence and Applications, vol. 263 (IOS Press, Amsterdam), 393–398.Google Scholar
• [29] Hosseini H, Sikdar S, Vaish R, Xia L (2021) Fair and efficient allocations under lexicographic preferences. Thirty-Fifth AAAI Conf. Artificial Intelligence AAAI 2021 Thirty-Third Conf. Innovative Appl. Artificial Intelligence IAAI 2021 Eleventh Sympos. Ed. Adv. Artificial Intelligence EAAI 2021 (AAAI Press, Washington, DC), 5472–5480.Google Scholar
• [30] Hsu K (2024) EFX orientations of multigraphs. Preprint, submitted October 15, https://arxiv.org/abs/2410.12039v1.Google Scholar
• [31] Jahan SC, Seddighin M, Javadi SMS, Sharifi M (2023) Rainbow cycle number and EFX allocations: (Almost) closing the gap. Proc. Thirty-Second Internat. Joint Conf. Artificial Intelligence IJCAI 2023 (IJCAI), 2572–2580.Google Scholar
• [32] Kaviani A, Seddighin M, Shahrezaei A (2024) Almost envy-free allocation of indivisible goods: A tale of two valuations. Web Internet Econom. 20th Internat. Conf. WINE 2024, Edinburgh, United Kingdom, December 2–5, 2024.Google Scholar
• [33] 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 (Association for Computing Machinery, New York), 125–131.Google Scholar
• [34] Mahara R (2024) Extension of additive valuations to general valuations on the existence of EFX. Math. Oper. Res. 49(2):1263–1277.Link, Google Scholar
• [35] Nisan N, Ronen A (2001) Algorithmic mechanism design. Games Econom. Behav. 35(1–2):166–196.Crossref, Google Scholar
• [36] Payan J, Sengupta R, Viswanathan V (2023) Relaxations of envy-freeness over graphs. Agmon N, An B, Ricci A, Yeoh W, eds. Proc. 2023 Internat. Conf. Autonomous Agents Multiagent Systems AAMAS 2023 (Association for Computing Machinery, New York), 2652–2654.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] Procaccia AD (2020) An answer to fair division’s most enigmatic question: Technical perspective. Commun. ACM 63(4):118.Crossref, Google Scholar
• [39] Sgouritsa A, Sotiriou MM (2025) On the existence of EFX allocations in multigraphs. Das S, Nowé A, Vorobeychik Y, eds. Proc. 24th Internat. Conf. Autonomous Agents Multiagent Systems AAMAS 2025 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 2735–2737.Google Scholar
• [40] Zeng JA, Mehta R (2025) On the structure of EFX orientations on graphs. Das S, Nowé A, Vorobeychik Y, eds. Proc. 24th Internat. Conf. Autonomous Agents Multiagent Systems AAMAS 2025 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 2309–2316.Google Scholar
• [41] Zhou Y, Wei T, Li M, Li B (2024) A complete landscape of EFX allocations on graphs: Goods, chores and mixed manna. Larson K, ed. Proc. Thirty-Third Internat. Joint Conf. Artificial Intelligence IJCAI-24 (Jeju, Korea) (International Joint Conferences on Artificial Intelligence Organization), 3049–3056.Google Scholar