Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

References

• [1] Akrami H, Garg J (2023) Breaking the 3/4 barrier for approximate maximin share. Preprint, submitted July 14, https://arxiv.org/abs/2307.07304.Google Scholar
• [2] Amanatidis G, Birmpas G, Markakis E (2016) On truthful mechanisms for maximin share allocations. Kambhampati S, ed. Proc. 25th Internat. Joint Conf. Artificial Intelligence (IJCAI/AAAI Press, Palo Alto, CA), 31–37.Google Scholar
• [3] Amanatidis G, Birmpas G, Markakis E (2018) Comparing approximate relaxations of envy-freeness. Lang J, ed. Proc. 27th Internat. Joint Conf. Artificial Intelligence (IJCAI, Stockholm, Sweden), 42–48.Google Scholar
• [4] Amanatidis G, Markakis E, Ntokos A (2020) Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Comput. Sci. 841:94–109.Crossref, Google Scholar
• [5] Amanatidis G, Birmpas G, Christodoulou G, Markakis E (2017) Truthful allocation mechanisms without payments: Characterization and implications on fairness. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput. (ACM, New York), 545–562.Google Scholar
• [6] 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
• [7] Amanatidis G, Birmpas G, Filos-Ratsikas A, Hollender A, Voudouris AA (2021) Maximum Nash welfare and other stories about EFX. Theoretical Comput. Sci. 863:69–85.Crossref, Google Scholar
• [8] Amanatidis G, Birmpas G, Lazos P, Leonardi S, Reiffenhäuser R (2023) Round-robin beyond additive agents: Existence and fairness of approximate equilibria. Leyton-Brown K, Hartline JD, Samuelson L, eds. Proc. 24th ACM Conf. Econom. Comput. (ACM, New York), 67–87.Google Scholar
• [9] Amanatidis G, Birmpas G, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2021) Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. Feldman M, Fu H, Talgam-Cohen I, eds. Proc. 17th Internat. Conf. Web Internet Econom. (Springer, Berlin, Germany), 149–166.Google Scholar
• [10] 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
• [11] Aziz H, Goldberg P, Walsh T (2017) Equilibria in sequential allocation. Rothe J, ed. Proc. Fifth Internat. Conf. Algorithmic Decision Theory (Springer, Berlin, Germany), 270–283.Google Scholar
• [12] Aziz H, Bouveret S, Lang J, Mackenzie S (2017) Complexity of manipulating sequential allocation. Singh S, Markovitch S, eds. Proc. 31st AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 328–334.Google Scholar
• [13] Babaioff M, Feige U (2022) Fair shares: Feasibility, domination and incentives. Pennock DM, Segal I, Seuken S, eds. Proc. 23rd ACM Conf. Econom. Comput. (ACM, New York), 435.Google Scholar
• [14] Babaioff M, Ezra T, Feige U (2021) Fair and truthful mechanisms for dichotomous valuations. Yang Q, ed. Proc. 35th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 5119–5126.Google Scholar
• [15] Barman S, Krishnamurthy SK (2020) Approximation algorithms for maximin fair division. ACM Trans. Econom. Comput. 8(1):1–28.Crossref, Google Scholar
• [16] Barman S, Biswas A, Murthy SKK, Narahari Y (2018) Groupwise maximin fair allocation of indivisible goods. McIlraith SA, Weinberger KQ, eds. Proc. 32nd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 917–924.Google Scholar
• [17] Bei X, Chen N, Huzhang G, Tao B, Wu J (2017) Cake cutting: Envy and truth. Sierra C, ed. Proc. 26th Internat. Joint Conf. Artificial Intelligence, vol. 17, 3625–3631.Google Scholar
• [18] Berger B, Cohen A, Feldman M, Fiat A (2022) Almost full EFX exists for four agents. Sycara K, ed. Proc. 36th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 4826–4833.Google Scholar
• [19] Bouveret S, Lang J (2014) Manipulating picking sequences. Schaub T, Friedrich G, O’Sullivan B, eds. Proc. 21st Eur. Conf. Artificial Intelligence, vol. 263 (IOS Press, Amsterdam), 141–146.Google Scholar
• [20] Bouveret S, Chevaleyre Y, Maudet N (2016) Fair allocation of indivisible goods. Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD, eds. Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK), 284–310.Crossref, Google Scholar
• [21] Brânzei S, Gkatzelis V, Mehta R (2022) Nash social welfare approximation for strategic agents. Oper. Res. 70(1):402–415.Link, Google Scholar
• [22] Brânzei S, Caragiannis I, Kurokawa D, Procaccia AD (2016) An algorithmic framework for strategic fair division. Schuurmans D, Wellman MP, eds. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 418–424.Google Scholar
• [23] Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
• [24] 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. 2019 ACM Conf. Econom. Comput. (ACM, New York), 527–545.Google Scholar
• [25] Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M (2009) On low-envy truthful allocations. Rossi F, Tsoukiàs A, eds. First Internat. Conf. Algorithmic Decision Theory (Springer, Berlin, Germany), 111–119.Google Scholar
• [26] 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
• [27] Chaudhury BR, Garg J, Mehlhorn K (2020) EFX exists for three agents. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. 2020 ACM Conf. Econom. Comput. (ACM, New York), 1–19.Google Scholar
• [28] 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
• [29] Chaudhury BR, Garg J, Mehlhorn K, Mehta R, Misra P (2021) Improving EFX guarantees through rainbow cycle number. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. 22nd ACM Conf. Econom. Comput. (ACM, New York), 310–311.Google Scholar
• [30] Chen Y, Lai JK, Parkes DC, Procaccia AD (2013) Truth, justice, and cake cutting. Games Econom. Behav. 77(1):284–297.Crossref, Google Scholar
• [31] Cole R, Gkatzelis V, Goel G (2013) Mechanism design for fair division: Allocating divisible items without payments. Kearns MJ, McAfee RP, Tardos E, eds. Proc. 14th ACM Conf. Electronic Commerce (ACM, New York), 251–268.Google Scholar
• [32] Ehlers L, Klaus B (2003) Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems. Soc. Choice Welfare 21(2):265–280.Crossref, Google Scholar
• [33] Foley DK (1967) Resource allocation and the public sector. Yale Econom. Essays 7:45–98.Google Scholar
• [34] Gamow G, Stern M (1958) Puzzle-Math (Viking Press, New York).Google Scholar
• [35] Garg J, Murhekar A (2023) Computing fair and efficient allocations with few utility values. Theoretical Comput. Sci. 962:113932.Crossref, Google Scholar
• [36] Garg J, Taki S (2021) An improved approximation algorithm for maximin shares. Artificial Intelligence 300:103547.Crossref, Google Scholar
• [37] Garg J, McGlaughlin P, Taki S (2019) Approximating maximin share allocations. Fineman JT, Mitzenmacher M, eds. Proc. Second Sympos. Simplicity Algorithms (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Germany), 1–11.Google Scholar
• [38] Ghodsi M, Hajiaghayi MT, Seddighin M, Seddighin S, Yami H (2021) Fair allocation of indivisible goods: Improvements and generalizations. Math. Oper. Res. 46(3):1038–1053.Link, Google Scholar
• [39] Gourvès L, Monnot J, Tlilane L (2014) Near fairness in matroids. Schaub T, Friedrich G, O’Sullivan B, eds. Proc. 21st Eur. Conf. Artificial Intelligence, vol. 263 (IOS Press, Amsterdam), 393–398.Google Scholar
• [40] 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. Proc. 16th Internat. Conf. Web Internet Econom. (Springer, Berlin, Germany), 370–383.Google Scholar
• [41] Klaus B, Miyagawa E (2002) Strategy-proofness, solidarity, and consistency for multiple assignment problems. Internat. J. Game Theory 30(3):421–435.Crossref, Google Scholar
• [42] Kohler DA, Chandrasekaran R (1971) A class of sequential games. Oper. Res. 19(2):270–277.Link, Google Scholar
• [43] Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):1–27.Crossref, Google Scholar
• [44] Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Breese JS, Feigenbaum J, Seltzer MI, eds. Proc. Fifth ACM Conf. Electronic Commerce (ACM, New York), 125–131.Google Scholar
• [45] Mahara R (2023) Existence of EFX for two additive valuations. Discrete Appl. Math. 340:115–122.Crossref, Google Scholar
• [46] Markakis E (2017) Approximation algorithms and hardness results for fair division with indivisible goods. Trends in Computational Social Choice (AI Access).Google Scholar
• [47] Papai S (2000) Strategyproof multiple assignment using quotas. Rev. Econom. Design 5(1):91–105.Crossref, Google Scholar
• [48] Papai S (2001) Strategyproof and nonbossy multiple assignments. J. Public Econom. Theory 3(3):257–271.Crossref, Google Scholar
• [49] Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discrete Math. 34(2):1039–1068.Crossref, Google Scholar
• [50] Procaccia AD (2016) Cake cutting algorithms. Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD, eds. Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK), 311–330.Crossref, Google Scholar
• [51] Steinhaus H (1949) Sur la division pragmatique. Econometrica 17:315–319.Crossref, Google Scholar
• [52] Varian HR (1974) Equity, envy and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• [53] Woeginger GJ (1997) A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4):149–154.Crossref, Google Scholar
• [54] Xiao M, Ling J (2020) Algorithms for manipulating sequential allocation. Rossi F, ed. Proc. 34th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 2302–2309.Google Scholar