Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 20

The DOI matches its Crossref record.

Fair Division of Indivisible Goods: A Survey

Amanatidis, Georgios, Birmpas, Georgios, Filos-Ratsikas, Aris, Voudouris, Alexandros A.·2022·Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
DOI 10.24963/ijcai.2022/756
Open this paper in CoChat — free account

Abstract

Allocating resources to individuals in a fair manner has been a topic of interest since the ancient times, with most of the early rigorous mathematical work on the problem focusing on infinitely divisible resources. Recently, there has been a surge of papers studying computational questions regarding various different notions of fairness for the indivisible case, like maximin share fairness (MMS) and envy-freeness up to any good (EFX). We survey the most important results in the discrete fair division literature, focusing on the case of additive valuation functions and paying particular attention to the progress made in the last 10 years.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.24963/ijcai.2022/756

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 67

  1. M. Aleksandrov and T. Walsh. Online fair division: A survey. In AAAI, pages 13557-13562, 2020.
  2. M. Aleksandrov, H. Aziz, S. Gaspers, and T. Walsh. Online fair division: Analysing a food bank problem. In IJCAI, pages 2540-2546, 2015.
  3. G. Amanatidis, G. Birmpas, and E. Markakis. On truthful mechanisms for maximin share allocations. In IJCAI, pages 31-37, 2016.
  4. Amanatidis et al., 2017a] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness. In ACM EC, pages 545-562, 2017.
  5. Amanatidis et al., 2017b] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. Approximation algorithms for computing maximin share allocations. ACM Trans. Algo- rithms, 13(4):52:1-52:28, 2017.
  6. G. Amanatidis, G. Birmpas, and E. Markakis. Comparing approximate relaxations of envy- freeness. In IJCAI, pages 42-48, 2018.
  7. Amanatidis et al., 2021b] G. Amanatidis, G. Birmpas, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser. Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. In WINE, pages 149-166, 2021.
  8. E. Anshelevich, A. Filos- Ratsikas, N. Shah, and A. A. Voudouris. Distortion in social choice problems: The first 15 years and beyond. In IJCAI, pages 4294-4301, 2021.
  9. H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh. Algorithms for max-min share fair allocation of indivisible chores. In AAAI, pages 335-341, 2017.
  10. H. Aziz, H. Moulin, and F. Sandomirskiy. A polynomial-time algorithm for computing a pareto op- timal and almost proportional allocation. Oper. Res. Lett., 48(5):573-578, 2020.
  11. H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation of indivisible goods and chores. Auton. Agents Multi Agent Syst., 36(1):3, 2022.
  12. H. Aziz. Simultaneously achieving ex-ante and ex-post fairness. In WINE, pages 341-355, 2020.
  13. Babaioff et al., 2021a] M. Babaioff, T. Ezra, and U. Feige. Fair and truthful mechanisms for dichotomous valuations. In AAAI, pages 5119-5126, 2021.
  14. Babaioff et al., 2021b] M. Babaioff, T. Ezra, and U. Feige. Fair-share allocations for agents with arbitrary entitle- ments. In ACM EC, page 127, 2021.
  15. Babaioff et al., 2021c] M. Babaioff, N. Nisan, and I. Talgam-Cohen. Competitive equilibrium with in- divisible goods and generic budgets. Math. Oper. Res., 46(1):382-403, 2021.
  16. Baklanov et al., 2021a] A. Baklanov, P. Garimidi, V. Gkatzelis, and D. Schoepflin. Achieving propor- tionality up to the maximin item with indivisible goods. In AAAI, pages 5143-5150, 2021.
  17. Baklanov et al., 2021b] A. Baklanov, P. Garimidi, V. Gkatzelis, and D. Schoepflin. Propm allocations of indivisible goods to multiple agents. In IJCAI, pages 24-30, 2021.
  18. S. Barman and S. K. Kr- ishnamurthy. On the proximity of markets with integral equilibria. In AAAI, pages 1748-1755, 2019.
  19. S. Barman and S. K. Kr- ishnamurthy. Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput., 8(1):5:1- 5:28, 2020.
  20. Barman et al., 2018a] S. Barman, A. Biswas, S. K. Krishna- murthy, and Y. Narahari. Groupwise maximin fair alloca- tion of indivisible goods. In AAAI, pages 917-924, 2018.
  21. Barman et al., 2018b] S. Barman, S. K. Krishnamurthy, and R. Vaish. Finding fair and efficient allocations. In EC, pages 557-574, 2018.
  22. S. Barman, U. Bhaskar, and N. Shah. Optimal bounds on the price of fairness for indivisible goods. In WINE, pages 356-369, 2020.
  23. Bei et al., 2021] X. Bei, X. Lu, P. Manurangsi, and W. Suk- sompong. The price of fairness for indivisible goods. The- ory Comput. Syst., 65(7):1069-1093, 2021.
  24. G. Benade, A. M. Kazachkov, A. D. Procaccia, and C.-A. Psomas. How to make envy vanish over time. In ACM EC, pages 593-610, 2018.
  25. B. Berger, A. Cohen, M. Feldman, and A. Fiat. (Almost full) EFX exists for four agents (and be- yond). CoRR, abs/2102.10654, 2021. · arXiv
  26. D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. Oper. Res., 59(1):17- 31, 2011.
  27. S. Bouveret and M. Lemaître. Characterizing conflicts in fair divi- sion of indivisible goods using a scale of criteria. Auton. Agents Multi Agent Syst., 30(2):259-290, 2016.
  28. J. Brustle, J. Dippel, V. V. Narayan, M. Suzuki, and A. Vetta. One dollar each eliminates envy. In ACM EC, pages 23-39, 2020.
  29. E. Budish. The combinatorial assign- ment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061-1103, 2011.
  30. Caragiannis and Ioannidis, 2021] I. Caragiannis and S. Ioannidis. Computing envy-freeable allocations with limited subsidies. In WINE, pages 522-539, 2021.
  31. Caragiannis et al., 2009] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. On low-envy truth- ful allocations. In ADT, pages 111-119, 2009.
  32. Caragiannis et al., 2012] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, and M. Kyropoulou. The efficiency of fair division. Theory Comput. Syst., 50(4):589-610, 2012.
  33. Caragiannis et al., 2019a] I. Caragiannis, N. Gravin, and X. Huang. Envy-freeness up to any item with high Nash welfare: The virtue of donating items. In EC, pages 527- 545, 2019.
  34. Caragiannis et al., 2019b] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum Nash welfare. ACM Trans. Economics and Comput., 7(3):12:1-12:32, 2019.
  35. Caragiannis et al., 2021] I. Caragiannis, P. Kanellopoulos, and M. Kyropoulou. On interim envy-free allocation lot- teries. In ACM EC, pages 264-284, 2021.
  36. M. Chakraborty, A. Igarashi, W. Suksompong, and Y. Zick. Weighted envy-freeness in indivisible item allocation. ACM Trans. Economics and Comput., 9(3):18:1-18:39, 2021.
  37. H. Chan, J. Chen, B. Li, and X. Wu. Maximin-aware allocations of indivisible goods. In IJCAI, pages 137-143, 2019.
  38. B. R. Chaudhury, Kavitha T, K. Mehlhorn, and A. Sgouritsa. A little charity guaran- tees almost envy-freeness. In SODA, pages 2658-2672, 2020.
  39. B. R. Chaudhury, J. Garg, K. Mehlhorn, R. Mehta, and P. Misra. Improving EFX guarantees through rainbow cycle number. In EC, pages 310-311, 2021.
  40. V. Conitzer, R. Freeman, and N. Shah. Fair public decision making. In ACM EC, pages 629-646, 2017.
  41. V. Conitzer, R. Freeman, N. Shah, and J. W. Vaughan. Group fairness for the allocation of indi- visible goods. In AAAI, pages 1853-1860, 2019.
  42. Soroush Ebadian, Dominik Peters, and Nisarg Shah. How to fairly allocate easy and difficult chores. CoRR, abs/2110.11285, 2021. · arXiv
  43. A. Farhadi, M. Hajiaghayi, M. Lati- fian, M. Seddighin, and H. Yami. Almost envy-freeness, envy-rank, and Nash social welfare matchings. In AAAI, pages 5355-5362, 2021.
  44. U. Feige, A. Sapir, and L. Tauber. A tight negative example for MMS fair allocations. In WINE, vol- ume 13112, pages 355-372, 2021.
  45. R. Freeman, N. Shah, and R. Vaish. Best of both worlds: Ex-ante and ex-post fairness in re- source allocation. In ACM EC, pages 21-22, 2020.
  46. G. Gamow and M. Stern. Puzzle- Math. Viking press, 1958.
  47. J. Garg and A. Murhekar. Com- puting fair and efficient allocations with few utility values. In SAGT, pages 345-359, 2021.
  48. M. Ghodsi, M. T. Hajiaghayi, M. Sed- dighin, S. Seddighin, and H. Yami. Fair allocation of indivisible goods: Improvement. Math. Oper. Res., 46(3):1038-1053, 2021.
  49. L. Gourvès, J. Monnot, and L. Tlilane. Near fairness in matroids. In ECAI, vol- ume 263, pages 393-398, 2014.
  50. D. Halpern and N. Shah. Fair di- vision with subsidy. In SAGT, pages 374-389, 2019.
  51. D. Halpern and N. Shah. Fair and efficient resource allocation with partial information. In IJCAI, pages 224-230, 2021.
  52. D. Halpern, A. D. Procaccia, A. Pso- mas, and N. Shah. Fair division with binary valuations: One rule to rule them all. In WINE, pages 370-383, 2020.
  53. J. He, A. D. Procaccia, A. Psomas, and D. Zeng. Achieving a fairer future by changing the past. In IJCAI, pages 343-349, 2019.
  54. M. Hoefer, M. Schmalhofer, and G. Varricchio. Approximating Nash social welfare in 2- valued instances. CoRR, abs/2107.08965, 2021. · arXiv
  55. D. Kurokawa, A. D. Procaccia, and J. Wang. When can the maximin share guarantee be guar- anteed? In AAAI, pages 523-529, 2016.
  56. D. Kurokawa, A. D. Procaccia, and J. Wang. Fair enough: Guaranteeing approximate max- imin shares. J. ACM, 65(2):8:1-8:27, 2018.
  57. D. Kurokawa. Fair Division in Game Theoretic Settings. PhD thesis, Carnegie Mellon Univer- sity, 2017.
  58. B. Li, Y. Li, and X. Wu. Almost proportional allocations for indivisible chores. CoRR, abs/2103.11849, 2021. · arXiv
  59. R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indi- visible goods. In EC, pages 125-131, 2004.
  60. P. Manurangsi and W. Suksompong. Almost envy-freeness for groups: Improved bounds via discrepancy theory. In IJCAI, pages 335-341, 2021.
  61. B. Plaut and T. Roughgar- den. Almost envy-freeness with general valuations. SIAM J. Discret. Math., 34(2):1039-1068, 2020.
  62. Ariel D Procaccia. Technical perspec- tive: An answer to fair division's most enigmatic question. Communications of the ACM, 63(4):118-118, 2020.
  63. W. Suksompong. Constraints in fair di- vision. SIGecom Exch., 19(2):46-61, 2021.
  64. A. Sun, B. Chen, and X. Vinh Doan. Con- nections between fairness criteria and efficiency for allo- cating indivisible chores. In AAMAS, pages 1281-1289, 2021.
  65. H. R. Varian. Equity, envy and efficiency. Journal of Economic Theory, 9:63-91, 1974.
  66. G. J. Woeginger. A polynomial-time ap- proximation scheme for maximizing the minimum ma- chine completion time. Oper. Res. Lett., 20(4):149-154, 1997.
  67. D. Zeng and A. Psomas. Fairness- efficiency tradeoffs in dynamic fair division. In ACM EC, pages 911-912, 2020.

Cited by

See all 20

Metadata

Authors
Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., & Voudouris, A. A.
Affiliations
  • University of Essex
  • Sapienza University of Rome
  • University of Liverpool
Venue
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Publisher
International Joint Conferences on Artificial Intelligence Organization
Published
2022-07
Pages
5385-5393
DOI
10.24963/ijcai.2022/756
Cited by
20
References
0

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Fair Division of Indivisible Goods: A Survey. https://app.cochat.ai/papers/10.24963/ijcai.2022/756
The paper
Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., & Voudouris, A. A. (2022). Fair Division of Indivisible Goods: A Survey. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. https://doi.org/10.24963/ijcai.2022/756

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.