Article

EFX Allocations Exist for Binary Valuations

Authors:

Ziqi YuAuthors Info & Claims

Frontiers of Algorithmics: 17th International Joint Conference, IJTCS-FAW 2023 Macau, China, August 14–18, 2023 Proceedings

Pages 252 - 262

https://doi.org/10.1007/978-3-031-39344-0_19

Published: 26 August 2023 Publication History

Abstract

We study the fair division problem and the existence of allocations satisfying the fairness criterion envy-freeness up to any item (EFX). The existence of EFX allocations is a major open problem in the fair division literature. We consider binary valuations where the marginal gain of the value by receiving an extra item is either 0 or 1. Babaioff et al. (2021) proved that EFX allocations always exist for binary and submodular valuations. In this paper, by using completely different techniques, we extend this existence result to general binary valuations that are not necessarily submodular, and we present a polynomial time algorithm for computing an EFX allocation.

References

[1]

Abdulkadiroğlu A, Pathak PA, and Roth AE The New York City high school match Am. Econ. Rev. 2005 95 2 364-367

[2]

Akrami, H., Chaudhury, B.R., Garg, J., Mehlhorn, K., Mehta, R.: EFX allocations: Simplifications and improvements. arXiv preprint arXiv:2205.07638 (2022)

[3]

Aumann Y and Dombb Y The efficiency of fair division with connected pieces ACM Trans. Econ. Comput. 2015 3 4 1-16

[4]

Aumann, Y., Dombb, Y., Hassidim, A.: Computing socially-efficient cake divisions. In: Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 343–350 (2013)

[5]

Aziz H, Huang X, Mattei N, and Segal-Halevi E Computing welfare-maximizing fair allocations of indivisible goods Eur. J. Oper. Res. 2023 307 2 773-784

[6]

Babaioff, M., Ezra, T., Feige, U.: Fair and truthful mechanisms for dichotomous valuations. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 5119–5126 (2021)

[7]

Barman S, Bhaskar U, and Shah N Chen X, Gravin N, Hoefer M, and Mehta R Optimal bounds on the price of fairness for indivisible goods Web and Internet Economics 2020 Cham Springer 356-369

[8]

Barman, S., Krishnamurthy, S.K., Vaish, R.: Finding fair and efficient allocations. In: Proceedings of the ACM Conference on Economics and Computation (EC), pp. 557–574 (2018)

[9]

Bei, X., Chen, N., Hua, X., Tao, B., Yang, E.: Optimal proportional cake cutting with connected pieces. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 1263–1269 (2012)

[10]

Bei, X., Chen, N., Huzhang, G., Tao, B., Wu, J.: Cake cutting: envy and truth. In: IJCAI, pp. 3625–3631 (2017)

[11]

Bei, X., Li, Z., Liu, J., Liu, S., Lu, X.: Fair division of mixed divisible and indivisible goods. Artif. Intell. 293, 103436 (2021a)

[12]

Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. Theory Comput. Syst. 65(7), 1069–1093 (2021b)

[13]

Berger, B., Cohen, A., Feldman, M., Fiat, A.: Almost full EFX exists for four agents. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 4826–4833 (2022)

[14]

Brams, S.J., Feldman, M., Lai, J., Morgenstern, J., Procaccia, A.D.: On maxsum fair cake divisions. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 1285–1291 (2012)

[15]

Bu, X., Li, Z., Liu, S., Song, J., Tao, B.: On the complexity of maximizing social welfare within fair allocations of indivisible goods. arXiv preprint arXiv:2205.14296 (2022)

[16]

Xiaolin, B., Song, J., Tao, B.: On existence of truthful fair cake cutting mechanisms. Artif. Intell. 319(2023), 103904 (2023).

[17]

Budish E The combinatorial assignment problem: approximate competitive equilibrium from equal incomes J. Polit. Econ. 2011 119 6 1061-1103

[18]

Budish E and Cantillon E The multi-unit assignment problem: theory and evidence from course allocation at harvard Am. Econ. Rev. 2012 102 5 2237-2271

[19]

Caragiannis, I., Gravin, N., Huang, X.: Envy-freeness up to any item with high nash welfare: the virtue of donating items. In: Proceedings of the ACM Conference on Economics and Computation (EC), pp. 527–545 (2019a)

[20]

Caragiannis I, Kaklamanis C, Kanellopoulos P, and Kyropoulou M The efficiency of fair division Theory Comput. Syst. 2012 50 4 589-610

[21]

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), 1–32 (2019b)

[22]

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

[23]

Chaudhury BR, Kavitha T, Mehlhorn K, and Sgouritsa A A little charity guarantees almost envy-freeness SIAM J. Comput. 2021 50 4 1336-1358

[24]

Cohler, Y.J., Lai, J.K., Parkes, D.S., Procaccia, A.D.: Optimal envy-free cake cutting. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 626–631 (2011)

[25]

Feldman, M., Mauras, S., Ponitka, T.: On optimal tradeoffs between EFX and nash welfare. arXiv preprint arXiv:2302.09633 (2023)

[26]

Ghodsi, A., Zaharia, M., Hindman, B., Konwinski, A., Shenker, S., Stoica, I.: Dominant resource fairness: fair allocation of multiple resource types. In: Proceedings of USENIX Symposium on Networked Systems Design and Implementation (NSDI) (2011)

[27]

Lian, J.W., Mattei, N., Noble, R., Walsh, T.: The conference paper assignment problem: using order weighted averages to assign indivisible goods. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 1138–1145 (2018)

[28]

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

[29]

Murhekar, A., Garg, J.: On fair and efficient allocations of indivisible goods. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 5595–5602 (2021)

[30]

Plaut B and Roughgarden T Almost envy-freeness with general valuations SIAM J. Discrete Math. 2020 34 2 1039-1068

[31]

Steinhaus H The problem of fair division Econometrica 1948 16 1 101-104

[32]

Steinhaus H Sur la division pragmatique Econometrica 1949 17 1949 315-319

[33]

Tao, B.: On existence of truthful fair cake cutting mechanisms. In: Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 404–434 (2022)

Cited By

Viswanathan MMehta RDastani MSichman JAlechina NDignum V(2024)On the existence of EFX under picky or non-differentiative agentsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663218(2534-2536)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663218
Misra NSethia A(2024)Envy-Free and Efficient Allocations for Graphical ValuationsAlgorithmic Decision Theory10.1007/978-3-031-73903-3_17(258-272)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-73903-3_17

Recommendations

EFX Allocations for Indivisible Chores: Matching-Based Approach
Algorithmic Game Theory
Abstract
One of the most important topics in discrete fair division is whether an EFX allocation exists for any instance. Although the existence of EFX allocations is a standing open problem for both goods and chores, the understanding of the existence of ...
Envy-Free and Efficient Allocations for Graphical Valuations
Algorithmic Decision Theory
Abstract
We consider the complexity of finding envy-free allocations for the class of graphical valuations. Graphical valuations were introduced by Christodoulou et al. [14] as a structured class of valuations that admit allocations that are envy-free up ...
Existence of EFX for two additive valuations
Abstract
Fair division of indivisible items is a well-studied topic in Economics and Computer Science. The objective is to allocate items to agents in a fair manner, where each agent has a valuation for each subset of items. Envy-freeness is one of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Frontiers of Algorithmics: 17th International Joint Conference, IJTCS-FAW 2023 Macau, China, August 14–18, 2023 Proceedings

Aug 2023

311 pages

ISBN:978-3-031-39343-3

DOI:10.1007/978-3-031-39344-0

Editors:
Minming Li
City University of Hong Kong, Hong Kong SAR, China
,
Xiaoming Sun
Chinese Academy of Sciences, Beijing, China
,
Xiaowei Wu
University of Macau, Macau, China

© Springer Nature Switzerland AG 2023.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 August 2023

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Viswanathan MMehta RDastani MSichman JAlechina NDignum V(2024)On the existence of EFX under picky or non-differentiative agentsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663218(2534-2536)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663218
Misra NSethia A(2024)Envy-Free and Efficient Allocations for Graphical ValuationsAlgorithmic Decision Theory10.1007/978-3-031-73903-3_17(258-272)Online publication date: 14-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-73903-3_17

View Options

View options

Media

Figures

Other

Tables

View Table of Contents