Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number

Published Online:22 Nov 2023https://doi.org/10.1287/moor.2021.0252

References

  • [1] Akrami H, Alon N, Chaudhury BR, Garg J, Mehlhorn K, Mehta R (2023) EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. Leyton-Brown K, Hartline JD, Samuelson L, eds. Proc. 24th ACM Conf. Econom. Comput., EC 23 (ACM, New York), 61.Google Scholar
  • [2] Alon N, Yuster R, Zwick U (1995) Color-coding. J. ACM 42(4):844–856.Crossref, Google Scholar
  • [3] 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
  • [4] Amanatidis G, Markakis E, Nikzad A, Saberi A (2017) Approximation algorithms for computing maximim share allocations. ACM Trans. Algorithms 13(4):52:1–52:28.Crossref, Google Scholar
  • [5] 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.Google Scholar
  • [6] 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
  • [7] 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) (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 1–12.Google Scholar
  • [8] 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
  • [9] Barman S, Krishnamurthy SK (2020) Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput. 8(1):5:1–5:28.Google Scholar
  • [10] Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Tardos É, Elkind E, Vohra R, eds. Proc. 19th ACM Conf. Econom. Comput. (EC) (ACM, New York), 557–574.Google Scholar
  • [11] Barman S, Krishnamurthy SK, Vaish R (2018) Greedy algorithms for maximizing Nash social welfare. André E, Koenig S, Dastani M, Sukthankar G, eds. Proc. 17th Internat. Conf. Autonomous Agents MultiAgent Systems (AAMAS) (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC/ACM, New York), 7–13.Google Scholar
  • [12] Berendsohn BA, Boyadzhiyska S, Kozma L (2022) Fixed-point cycles and approximate EFX allocations. Szeider S, Ganian R, Silva A, eds. 47th Internat. Sympos. Mathematical Foundations of Computer Science, MFCS 2022, LIPIcs, vol. 241 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 17:1–17:13.Google Scholar
  • [13] 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 Applications of Artificial Intelligence, IAAI 2022, The Twelfth Sympos. Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event (AAAI Press, Palo Alto, CA), 4826–4833.Google Scholar
  • [14] 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
  • [15] Brams SJ, Kilgour DM, Klamler C (2017) Maximin envy-free division of indivisible items. Group Decision Negotiation 26(1):115–131.Crossref, Google Scholar
  • [16] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
  • [17] Caragiannis I, Gravin N, Huang X (2019) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Karlin A, Immorlica N, Johari R, eds. Proc. 20th ACM Conf. Econom. Comput. (EC) (ACM, New York), 527–545.Google Scholar
  • [18] 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. 17th ACM Conf. Econom. Comput. (EC) (ACM, New York), 305–322.Google Scholar
  • [19] 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) (ACM, New York), 1–19.Google Scholar
  • [20] 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) (SIAM, Philadelphia), 2658–2672.Google Scholar
  • [21] 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. (EC) (ACM, New York), 310–311.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] Conlon D, Ferber A (2021) Lower bounds for multicolor Ramsey numbers. Adv. Math. 378:107528.Crossref, Google Scholar
  • [24] Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms, vol. 5 (Springer, Cham, Switzerland).Crossref, Google Scholar
  • [25] Darmann A, Schauer J (2015) Maximizing Nash product social welfare in allocating indivisible goods. Eur. J. Oper. Res. 247(2):548–559.Google Scholar
  • [26] Diestel R (2012) Graph Theory, 4th ed., Graduate Texts in Mathematics, vol. 5 (Springer, Cham, Switzerland).Google Scholar
  • [27] Erdős P, Szekeres G (1935) A combinatorial problem in geometry. Compositio Mathdmatica 2:463–470.Google Scholar
  • [28] Garg J, Murhekar A (2021) Computing fair and efficient allocations with few utility values. Caragiannis I, Hansen KF, eds. Proc. 14th Internat. Sympos. Algorithmic Game Theory (SAGT), vol. 12885 (Springer, New York), 345–359.Google Scholar
  • [29] Garg J, Taki S (2021) An improved approximation algorithm for maximin shares. Artificial Intelligence 300:103547.Crossref, Google Scholar
  • [30] Garg J, McGlaughlin P, Taki S (2019) Approximating maximin share allocations. Fineman JT, Mitzenmacher M, eds. Proc. 2nd Sympos. Simplicity Algorithms (SOSA), vol. 69 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 1–20.Google Scholar
  • [31] Ghodsi M, Hajiaghayi MT, Seddighin M, Seddighin S, Yami H (2018) Fair allocation of indivisible goods: Improvements and generalizations. Tardos É, Elkind E, Vohra R, eds. Proc. 19th ACM Conf. Econom. Comput. (EC) (ACM, New York), 539–556.Google Scholar
  • [32] Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8:1–8:27.Crossref, Google Scholar
  • [33] Lefmann H (1987) A note on Ramsey numbers. Studia Scientiarum Mathematicarum Hungarica. 22(1–4):445–446.Google Scholar
  • [34] 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) (ACM, New York), 125–131.Google Scholar
  • [35] Mahara R (2021) Extension of additive valuations to general valuations on the existence of EFX. ESA LIPIcs, vol. 204 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 66:1–66:15.Google Scholar
  • [36] Manurangsi P, Suksompong W (2021) Closing gaps in asymptotic fair division. SIAM J. Discret. Math. 35(2):668–706.Google Scholar
  • [37] Moulin H (2019) Fair division in the internet age. Annual Rev. Econom. 11(1):407–441.Crossref, Google Scholar
  • [38] Naor M, Schulman LJ, Srinivasan A (1995) Splitters and near-optimal derandomization. Proc. IEEE 36th Annual Foundations Comput. Sci. (IEEE, Piscataway, NJ), 182–191.Google Scholar
  • [39] Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2):1039–1068.Google Scholar
  • [40] Procaccia AD (2020) Technical perspective: An answer to fair division’s most enigmatic question. Comm. ACM 63(4):118.Crossref, Google Scholar
  • [41] Steinhaus H (1949) Sur la division pragmatique. Econometrica 17:315–319.Crossref, Google Scholar
  • [42] Walsh T (2020) Fair division: The computer scientist’s perspective. Bessiere C, ed. Proc. Twenty-Ninth Internat. Joint Conf. Artificial Intelligence (IJCAI) (IJCAI, CA), 4966–4972.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree