On the Fairness of Normalized p-Means for Allocating Goods and Chores

References

• [1] Abdulkadiroğlu A, Sönmez T (2013) Matching markets: Theory and practice. Acemoglu D, Arellano M, Dekel E, eds. Adv. Econom. Econometrics 10th World Congress, vol. 1 (Cambridge University Press, Cambridge, UK), 3–47.Google Scholar
• [2] Alon N, Feldman M, Procaccia AD, Tennenholtz M (2010) Strategyproof approximation of the minimax on networks. Math. Oper. Res. 35(3):513–526.Link, Google Scholar
• [3] Arrow KJ, Intriligator MD, Hildenbrand W, Sonnenschein H (1981) Handbook of Mathematical Economics, vol. 1 (North-Holland, Amsterdam).Google Scholar
• [4] Aziz H (2020) Justifications of welfare guarantees under normalized utilities. ACM SIGecom Exchanges 17(2):71–75.Crossref, Google Scholar
• [5] Barman S, Krishnamurthy SK (2019) On the proximity of markets with integral equilibria. Proc. AAAI Conf. Artificial Intelligence 33(1):1748–1755.Crossref, Google Scholar
• [6] Barman S, Sundaram RG (2021) Uniform welfare guarantees under identical subadditive valuations. Bessiere C, ed. Proc. 29th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence), 46–52.Google Scholar
• [7] Barman S, Verma P (2022) Truthful and fair mechanisms for matroid-rank valuations. Proc. AAAI Conf. Artificial Intelligence 36(5):4801–4808.Crossref, Google Scholar
• [8] Barman S, Khan A, Maiti A (2022) Universal and tight online algorithms for generalized-mean welfare. Proc. AAAI Conf. Artificial Intelligence 36(5):4793–4800.Crossref, Google Scholar
• [9] Barman S, Narayan V, Verma P (2023) Fair chore division under binary supermodular costs. Proc. 2023 Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 2863–2865.Google Scholar
• [10] Barman S, Bhaskar U, Krishna A, Sundaram RG (2020) Tight approximation algorithms for p-mean welfare under subadditive valuations. Grandoni F, Herman G, Sanders P, eds. 28th Annual Eur. Sympos. Algorithms (ESA 2020) (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 11:1–11:17.Google Scholar
• [11] Bhaskar U, Sricharan A, Vaish R (2021) On approximate envy-freeness for indivisible chores and mixed resources. Wootters M, Sanità L, eds. Approximation Randomization Combin. Optim. Algorithms Techniques (APPROX/RANDOM 2021) (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 1:1–1:23.Google Scholar
• [12] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2017) Competitive division of a mixed manna. Econometrica 85(6):1847–1871.Crossref, Google Scholar
• [13] Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [14] Brânzei S, Sandomirskiy F (2023) Algorithms for competitive division of chores. Math. Oper. Res. 49(1):398–429.Link, Google Scholar
• [15] 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
• [16] Chaudhury BR, Garg J, Mehta R (2021) Fair and efficient allocations under subadditive valuations. Proc. AAAI Conf. Artificial Intelligence 35(6):5269–5276.Crossref, Google Scholar
• [17] Clarke EH (1971) Multipart pricing of public goods. Public Choice 11:17–33.Crossref, Google Scholar
• [18] Conitzer V, Freeman R, Shah N (2017) Fair public decision making. Proc. 2017 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 629–646.Google Scholar
• [19] Ebadian S, Peters D, Shah N (2022) How to fairly allocate easy and difficult chores. Proc. 21st Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 372–380.Google Scholar
• [20] Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Statist. 30(1):165–168.Crossref, Google Scholar
• [21] Foley DK (1966) Resource Allocation and the Public Sector (Yale University, New Haven, CT).Google Scholar
• [22] Garg J, Husic E, Murhekar A (2022) Tractable fragments of the maximum Nash welfare problem. Hansen KA, Liu TX, Malekian A, eds. Web Internet Econom. 18th Internat. Conf. WINE 2022 (Springer, Cham, Switzerland), 362–363.Google Scholar
• [23] Garg J, Murhekar A, Qin J (2022) Fair and efficient allocations of chores under bivalued preferences. Proc. AAAI Conf. Artificial Intelligence 36(5):5043–5050.Crossref, Google Scholar
• [24] Garg J, Murhekar A, Qin J (2023) New algorithms for the fair and efficient allocation of indivisible chores. Elkind E, ed. Proc. 32nd Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence), 2710–2718.Google Scholar
• [25] Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Hammer PL, Johnson EL, Korte BH, eds. Discrete Optimization II. Annals of Discrete Mathematics, vol. 5 (Elsevier, Amsterdam), 287–326.Crossref, Google Scholar
• [26] Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Proc. 5th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 125–131.Google Scholar
• [27] Mas-Colell A, Whinston MD, Green JR (1995) Microeconomic Theory, vol. 1 (Oxford University Press, New York).Google Scholar
• [28] Nash JF Jr (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• [29] Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discrete Math. 34(2):1039–1068.Crossref, Google Scholar
• [30] Steinhaus H (1948) The problem of fair division. Econometrica 16:101–104.Google Scholar
• [31] Varian HR (1974) Equity, envy, and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• [32] Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8–37.Crossref, Google Scholar
• [33] Viswanathan V, Zick Y (2023) A general framework for fair allocation under matroid rank valuations. Proc. 24th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1129–1152.Google Scholar
• [34] Yuen SM, Suksompong W (2023) Extending the characterization of maximum Nash welfare. Econom. Lett. 224:111030–111033.Crossref, Google Scholar