Abstract
In the allocation of resources to a set of agents, how do fairness guarantees impact social welfare? A quantitative measure of this impact is the price of fairness, which measures the worst-case loss of social welfare due to fairness constraints. While initially studied for divisible goods, recent work on the price of fairness also studies the setting of indivisible goods.
In this paper, we resolve the price of two well-studied fairness notions in the context of indivisible goods: envy-freeness up to one good (\(\textsc {EF1} \)) and approximate maximin share (\(\textsc {MMS} \)). For both \(\textsc {EF1} \) and
we show, via different techniques, that the price of fairness is \(O(\sqrt{n})\), where n is the number of agents. From previous work, it follows that these guarantees are tight. We, in fact, obtain the price-of-fairness results via efficient algorithms. For
our bound holds for additive valuations, whereas for \(\textsc {EF1} \), it holds for the more general class of subadditive valuations. This resolves an open problem posed by Bei et al. (2019).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The canonical example is that of a single indivisible good and two agents—the agent that does not receive the good will inevitably envy the other.
- 2.
A valuation is additive iff the value of a bundle of goods is equal to the sum of the values of the individual goods in the bundle.
- 3.
Section 2 provides a formal description of the valuation classes and the query models.
- 4.
This allocation serves as a reference in our algorithm, and may not be \(\textsc {EF1} \) itself.
- 5.
For example, we can index the goods such that \(W_i = \Big \{g_k : 1 + \sum _{j=1}^{i-1} |W_{j}| \le k \le \sum _{j=1}^i |W_i|\Big \}\) for each agent \(i \in [n]\).
References
Amanatidis, G., Markakis, E., Nikzad, A., Saberi, A.: Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms (TALG) 13(4), 1–28 (2017)
Amanatidis, G., Markakis, E., Ntokos, A.: Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination. In: AAAI 2020, pp. 1790–1797. AAAI Press (2020)
Arunachaleswaran, E.R., Barman, S., Kumar, R., Rathi, N.: Fair and efficient cake division with connected pieces. In: Caragiannis, I., Mirrokni, V., Nikolova, E. (eds.) WINE 2019. LNCS, vol. 11920, pp. 57–70. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35389-6_5
Barman, S., Bhaskar, U., Shah, N.: Optimal bounds on the price of fairness for indivisible goods. CoRR abs/2007.06242 (2020)
Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. In: Kraus, S. (ed.) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 10–16 August 2019, pp. 81–87 (2019)
Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17–31 (2011)
Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72, 257–279 (2004)
Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061–1103 (2011)
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. In: Proceedings of the 5th Conference on Web and Internet Economics (WINE), pp. 475–482 (2009)
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. (TEAC) 7(3), 1–32 (2019)
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589–610 (2012)
Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res. 35(1), 1–13 (2010)
Dutta, B., Peters, H., Sen, A.: Strategy-proof cardinal decision schemes. Soc. Choice Welfare 28(1), 163–179 (2007)
Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1), 122–142 (2009)
Foley, D.: Resource allocation and the public sector. Yale Economics Essays, vol. 7, pp. 45–98 (1967)
Garg, J., Taki, S.: An improved approximation algorithm for maximin shares. In: EC 2020, pp. 379–380. ACM (2020)
Ghodsi, M., Hajiaghayi, M., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods: improvements and generalizations. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 539–556 (2018)
Kurokawa, D., Procaccia, A.D., Wang, J.: When can the maximin share guarantee be guaranteed? In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 523–529 (2016)
Kurokawa, D., Procaccia, A.D., Shah, N.: Leximin allocations in the real world. ACM Trans. Econ. Comput. (TEAC) 6(3–4), 1–24 (2018)
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, pp. 125–131 (2004)
Mirrokni, V., Schapira, M., Vondrák, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proceedings of the 9th ACM Conference on Electronic Commerce, pp. 70–77 (2008)
Suzuki, M., Vetta, A.: How many freemasons are there? The consensus voting mechanism in metric spaces. In: Harks, T., Klimm, M. (eds.) SAGT 2020. LNCS, vol. 12283, pp. 322–336. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57980-7_21
Procaccia, A.D., Wang, J.: Fair enough: guaranteeing approximate maximin shares. In: Proceedings of the 14th ACM Conference on Economics and Computation (EC), pp. 675–692 (2014)
Rawls, J.: A Theory of Justice. Harvard University Press, Cambridge (1971)
Woeginger, G.J.: A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4), 149–154 (1997)
Acknowledgements
SB gratefully acknowledges the support of a Ramanujan Fellowship (SERB - SB/S2/RJN-128/2015) and a Pratiksha Trust Young Investigator Award. UB’s research is generously supported the Department of Atomic Energy, Government of India (project no. RTI4001), a Ramanujan Fellowship (SERB - SB/S2/RJN-055/2015), and an Early Career Research Award (SERB - ECR/2018/002766). NS was partially supported by an NSERC Discovery Grant.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Barman, S., Bhaskar, U., Shah, N. (2020). Optimal Bounds on the Price of Fairness for Indivisible Goods. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_25
Download citation
DOI: https://doi.org/10.1007/978-3-030-64946-3_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64945-6
Online ISBN: 978-3-030-64946-3
eBook Packages: Computer ScienceComputer Science (R0)