nach oben

Theory of Computing Systems

Erschienen in:

29.03.2021

The Price of Fairness for Indivisible Goods

verfasst von: Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong

Erschienen in: Theory of Computing Systems | Ausgabe 7/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We also introduce the concept of strong price of fairness, which captures the efficiency loss in the worst fair allocation as opposed to that in the best fair allocation as in the price of fairness. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions, for both the price of fairness and the strong price of fairness.

Vorheriger Artikel On the Expressive Power of Stateless Ordered Restart-Delete Automata

Nächster Artikel The Minimum Tollbooth Problem in Atomic Network Congestion Games with Unsplittable Flows

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

From the above example, one may think that such scenarios are rare exceptions. However, for envy-freeness, these scenarios are in fact common if the number of goods is not too large compared to the number of agents [19, 29].

Indeed, the instance that Caragiannis et al. used to show that the price of proportionality is at least n − 1 + 1/n admits no envy-free allocation. Thus, it is still possible that the price of envy-freeness is lower than the price of proportionality for indivisible goods.

See Section 2 for the formal definitions of these notions.

See the example in Theorem 3.5.

Moreover, a round-robin allocation is likely to be envy-free and proportional as long as the number of goods is sufficiently larger than the number of agents [28].

In addition to these exceptions, MNW, MEW, and leximin allocations are hard to compute regardless of price of fairness considerations (see, e.g., [33], footnote 7).

Interestingly, this stands in contrast to our result that the price of MNW for indivisible goods is Θ(n).

See [17] for the definitions of MMS and PMMS.

Recently, Chaudhury et al. [18] showed that the existence is also guaranteed for three agents.

In case there are ties between goods, we may assume worst-case tie breaking, since it is possible to obtain an instance with infinitesimal difference in welfare and any desired tie-breaking between goods by slightly perturbing the utilities.

In the case where the maximum Nash welfare is 0, an allocation is an MNW allocation if it gives positive utility to a set of agents of maximal size and moreover maximizes the product of utilities of the agents in that set.

To see the first and third inequalities, one may prove by induction that in general, if we have \(\frac {a_{1}}{b_{1}}\geq \dots \geq \frac {a_{k}}{b_{k}}\), then \(\frac {a_{1}}{b_{1}}\geq \frac {a_{1}+\dots +a_{k}}{b_{1}+\dots +b_{k}}\geq \frac {a_{k}}{b_{k}}\). The case k = 2 holds because \(\frac {a_{1}}{b_{1}}\geq \frac {a_{1}+a_{2}}{b_{1}+b_{2}}\) is equivalent to \(\frac {a_{1}}{b_{1}}\geq \frac {a_{2}}{b_{2}}\), and similarly for \(\frac {a_{1}+a_{2}}{b_{1}+b_{2}}\geq \frac {a_{2}}{b_{2}}\).

Amanatidis, G., Birmpas, G., Markakis, E.: Comparing approximate relaxations of envy-freeness. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp 42–48 (2018)

Amanatidis, G., Ntokos, A., Markakis, E.: Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. 841, 94–109 (2020)MathSciNetCrossRef

Aumann, Y., Dombb, Y.: The efficiency of fair division with connected pieces. ACM Trans. Econ. Comput. 3(4), 23:1–23:16 (2015)MathSciNetCrossRef

Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp 31–40 (2006)

Barman, S., Bhaskar, U., Shah, N.: Settling the price of fairness for indivisible goods. In: Proceedings of the 16th Conference on Web and Internet Economics (WINE), pp. 356–369 (2020)

Barman, S., Krishnamurthy, S.K.: Approximation algorithms for maximin fair division. ACM Trans. Econ. Comput. 8(1), 5:1–5:28 (2020)MathSciNetCrossRef

Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp 81–87 (2019)

Benabbou, N., Chakraborty, M., Igarashi, A., Zick, Y.: Finding fair and efficient allocations when valuations don’t add up. In: Proceedings of the 13th International Symposium on Algorithmic Game Theory, SAGT, pp 32–46 (2020)

Bérczi, K., Bérczi-Kovács, E.R., Boros, E., Gedefa, F.T., Kamiyama, N., Kavitha, T., Kobayashi, Y., Makino, K.: Envy-free relaxations for goods, chores, and mixed items. arXiv:2006.04428 (2020)

10.

Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17–31 (2011)MathSciNetCrossRef

11.

Bezáková, I., Dani, V.: Allocating indivisible goods. ACM SIGecom. Exchanges. 5(3), 11–18 (2005)CrossRef

12.

Bilò, V., Fanelli, A., Flammini, M., Monaco, G., Moscardelli, L.: The price of envy-freeness in machine scheduling. Theor. Comput. Sci. 613, 65–78 (2016)MathSciNetCrossRef

13.

Biswas, A., Barman, S.: Fair division under cardinality constraints. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp 91–97 (2018)

14.

Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72(1), 257–279 (2004)MathSciNetCrossRef

15.

Brams, S.J., Taylor, D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)CrossRef

16.

Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory. Comput. Syst. 50(4), 589–610 (2012)MathSciNetCrossRef

17.

Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. 7(3), 12:1–12:32 (2019)MathSciNetCrossRef

18.

Chaudhury, B.R., Garg, J., Mehlhorn, K.: EFX exists for three agents. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp 1–19 (2020)

19.

Dickerson, J.P., Goldman, J., Karp, J., Procaccia, A.D., Sandholm, T.: The computational rise and fall of fairness. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pp 1405–1411 (2014)

20.

Dubins, L.E., Spanier, E.H.: How to cut a cake fairly. Am. Math. Mon. 68(1), 1–17 (1961)MathSciNetCrossRef

21.

Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods Improvement and generalization. In: Proceedings of the 19th ACM Conference on Economics and Computation (EC), pp 539–556 (2018)

22.

Heydrich, S., van Stee, R.: Dividing connected chores fairly. Theor. Comput. Sci. 593, 51–61 (2015)MathSciNetCrossRef

23.

Kurokawa, D., Procaccia, A.D., Shah, N.: Leximin allocations in the real world. ACM Trans. Econ. Comput. 6(3–4), 11:1–11:24 (2018a)MathSciNet

24.

Kurokawa, D., Procaccia, A.D., Wang, J.: Fair enough: Guaranteeing approximate maximin shares. J. ACM 64(2), 8:1–8:27 (2018b)MathSciNetMATH

25.

Kurz, S.: The price of fairness for a small number of indivisible items. In: Operations Research Proceedings, pp 335–340 (2014)

26.

Kyropoulou, M., Suksompong, W., Voudouris, A.A.: Almost envy-freeness in group resource allocation. Theor. Comput. Sci. 841, 110–123 (2020)MathSciNetCrossRef

27.

Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pp 125–131 (2004)

28.

Manurangsi, P., Suksompong, W.: Closing gaps in asymptotic fair division. arXiv:2004.05563 (2020a)

29.

Manurangsi, P., Suksompong, W.: When do envy-free allocations exist? SIAM J. Discret. Math. 34(3), 1505–1521 (2020b)MathSciNetCrossRef

30.

Markakis, E.: Approximation algorithms and hardness results for fair division. In: Ulle, E. (ed.) Trends in Computational Social Choice, chapter 12. AI Access, pp 231–247 (2017)

31.

Michorzewski, M., Peters, D., Skowron, P.: Price of fairness in budget division and probabilistic social choice. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp 2184–2191 (2020)

32.

Oh, H., Procaccia, A.D., Suksompong, W.: Fairly allocating many goods with few queries. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp 2141–2148 (2019)

33.

Plaut, B., Roughgarden, T.: Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2), 1039–1068 (2020)MathSciNetCrossRef

34.

Segal-Halevi, E., Suksompong, W.: Democratic fair allocation of indivisible goods. Artif. Intell. 277, 103167 (2019)MathSciNetCrossRef

35.

Steinhaus, H.: The problem of fair division. Econometrica 16(1), 101–104 (1948)

36.

Suksompong, W.: Approximate maximin shares for groups of agents. Math. Soc. Sci. 92, 40–47 (2018)MathSciNetCrossRef

37.

Suksompong, W.: Fairly allocating contiguous blocks of indivisible items. Discret. Appl. Math. 260, 227–236 (2019)MathSciNetCrossRef

38.

Suksompong, W.: On the number of almost envy-free allocations. Discret. Appl. Math. 284, 606–610 (2020)MathSciNetCrossRef

Titel: The Price of Fairness for Indivisible Goods
verfasst von: Xiaohui Bei
Xinhang Lu
Pasin Manurangsi
Warut Suksompong
Publikationsdatum: 29.03.2021
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 7/2021
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-021-10039-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 7/2021

On the Expressive Power of Stateless Ordered Restart-Delete Automata

The Minimum Tollbooth Problem in Atomic Network Congestion Games with Unsplittable Flows

Correction to: Parameterized Complexity of Min-Power Asymmetric Connectivity

Lower-Bounds on the Growth of Power-Free Languages Over Large Alphabets

Computationally Efficient Approach to Implementation of the Chinese Remainder Theorem Algorithm in Minimally Redundant Residue Number System

Premium Partner