Your browser does not fully support modern features. Please upgrade for a smoother experience.
Submitted Successfully!
Thank you for your contribution! You can also upload a video entry or images related to this topic. For video creation, please contact our Academic Video Service.
Version Summary Created by Modification Content Size Created at Operation
1 handwiki Camila Xu -- 3992 2022-10-21 01:33:08

Video Upload Options

We provide professional Academic Video Service to translate complex research into visually appealing presentations. Would you like to try it?
No, upload directly Yes
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. Envy-free Item Allocation. Encyclopedia. Available online: https://encyclopedia.pub/entry/30599 (accessed on 03 October 2026).
HandWiki. Envy-free Item Allocation. Encyclopedia. Available at: https://encyclopedia.pub/entry/30599. Accessed October 03, 2026.
HandWiki. "Envy-free Item Allocation" Encyclopedia, https://encyclopedia.pub/entry/30599 (accessed October 03, 2026).
HandWiki. (2022, October 21). Envy-free Item Allocation. In Encyclopedia. https://encyclopedia.pub/entry/30599
HandWiki. "Envy-free Item Allocation." Encyclopedia. Web. 21 October, 2022.
Envy-free Item Allocation
Edit
The content is sourced from: https://handwiki.org/wiki/Social:Envy-free_item_allocation

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.:296–297 Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. Therefore, the division procedures provide various kinds of relaxations.

envy-freeness envy-free envy

References

  1. Svensson, Lars-Gunnar (1983). "Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness". Econometrica 51 (4): 939–954. doi:10.2307/1912044. ISSN 0012-9682.  https://dx.doi.org/10.2307%2F1912044
  2. Demange, Gabrielle; Gale, David; Sotomayor, Marilda (1986). "Multi-Item Auctions". Journal of Political Economy 94 (4): 863–872. doi:10.1086/261411.  https://dx.doi.org/10.1086%2F261411
  3. Maskin, Eric S. (1987), Feiwel, George R., ed., "On the Fair Allocation of Indivisible Goods" (in en), Arrow and the Foundations of the Theory of Economic Policy (London: Palgrave Macmillan UK): pp. 341–349, doi:10.1007/978-1-349-07357-3_12, ISBN 978-1-349-07357-3, https://doi.org/10.1007/978-1-349-07357-3_12, retrieved 2021-02-16 
  4. Tadenuma, Koichi; Thomson, William (1991). "No-Envy and Consistency in Economies with Indivisible Goods". Econometrica 59 (6): 1755–1767. doi:10.2307/2938288. ISSN 0012-9682.  https://dx.doi.org/10.2307%2F2938288
  5. Aragones, Enriqueta (1995). "A derivation of the money rawlsian solution". Social Choice and Welfare 12 (3): 267–276. doi:10.1007/BF00179981. ISSN 0176-1714.  https://dx.doi.org/10.1007%2FBF00179981
  6. Alkan, Ahmet; Demange, Gabrielle; Gale, David (1991). "Fair Allocation of Indivisible Goods and Criteria of Justice". Econometrica 59 (4): 1023–1039. doi:10.2307/2938172. ISSN 0012-9682.  https://dx.doi.org/10.2307%2F2938172
  7. Klijn, Flip (2000-03-01). "An algorithm for envy-free allocations in an economy with indivisible objects and money" (in en). Social Choice and Welfare 17 (2): 201–215. doi:10.1007/s003550050015. ISSN 1432-217X. https://doi.org/10.1007/s003550050015. 
  8. Meertens, Marc; Potters, Jos; Reijnierse, Hans (2002-12-01). "Envy-free and Pareto efficient allocations in economies with indivisible goods and money" (in en). Mathematical Social Sciences 44 (3): 223–233. doi:10.1016/S0165-4896(02)00064-1. ISSN 0165-4896. https://www.sciencedirect.com/science/article/pii/S0165489602000641. 
  9. Ruggiero Cavallo (2012). "Fairness and Welfare Through Redistribution When Utility is Transferable". AAAI-12. http://www.eecs.harvard.edu/~cavallo/papers/cavallo-aaai12.pdf. 
  10. Bailey, Martin J. (1997). "The demand revealing process: To distribute the surplus". Public Choice 91 (2): 107–126. doi:10.1023/A:1017949922773.  https://dx.doi.org/10.1023%2FA%3A1017949922773
  11. Cavallo, Ruggiero (2006). "Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems - AAMAS '06". pp. 882. doi:10.1145/1160633.1160790. ISBN 1595933034.  https://dx.doi.org/10.1145%2F1160633.1160790
  12. Halpern, Daniel; Shah, Nisarg (2019). Fotakis, Dimitris; Markakis, Evangelos. eds. "Fair Division with Subsidy" (in en). Algorithmic Game Theory. Lecture Notes in Computer Science (Cham: Springer International Publishing) 11801: 374–389. doi:10.1007/978-3-030-30473-7_25. ISBN 978-3-030-30473-7. https://link.springer.com/chapter/10.1007/978-3-030-30473-7_25. 
  13. Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (2020-07-13). "One Dollar Each Eliminates Envy". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20 (Virtual Event, Hungary: Association for Computing Machinery): 23–39. doi:10.1145/3391403.3399447. ISBN 978-1-4503-7975-5. https://doi.org/10.1145/3391403.3399447. 
  14. Caragiannis, Ioannis; Ioannidis, Stavros (2020-02-06). "Computing envy-freeable allocations with limited subsidies". arXiv:2002.02789 [cs.GT]. //arxiv.org/archive/cs.GT
  15. Mu'alem, Ahuva (2014). "Fair by design: Multidimensional envy-free mechanisms". Games and Economic Behavior 88: 29–46. doi:10.1016/j.geb.2014.08.001.  https://dx.doi.org/10.1016%2Fj.geb.2014.08.001
  16. Aziz, Haris (2020-03-18). "Achieving Envy-freeness and Equitability with Monetary Transfers". arXiv:2003.08125 [cs.GT]. //arxiv.org/archive/cs.GT
  17. Sylvain Bouveret, Ulle Endriss, Jérôme Lang (2010). "Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods". ECAI 2010. pp. 387–392. 
  18. Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016) (in en). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. https://books.google.com/books?id=nMHgCwAAQBAJ.  (free online version)
  19. Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Proceedings of the 5th ACM conference on Electronic commerce - EC '04". pp. 125. doi:10.1145/988772.988792. ISBN 1-58113-771-0.  https://dx.doi.org/10.1145%2F988772.988792
  20. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). "Communication Complexity of Discrete Fair Division". SIAM Journal on Computing 49 (1): 206–243. doi:10.1137/19M1244305. ISSN 0097-5397. https://epubs.siam.org/doi/abs/10.1137/19M1244305. 
  21. Bouveret, S.; Lang, J. (2008). "Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity". Journal of Artificial Intelligence Research 32: 525–564. doi:10.1613/jair.2467.  https://dx.doi.org/10.1613%2Fjair.2467
  22. De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "Algorithmic Decision Theory". 5783. pp. 98. doi:10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4.  https://dx.doi.org/10.1007%2F978-3-642-04428-1_9
  23. Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16 (New York, New York, USA: AAAI Press): 102–108. ISBN 978-1-57735-770-4. https://dl.acm.org/doi/abs/10.5555/3060621.3060636. 
  24. Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy 119 (6): 1061–1103. doi:10.1086/664613.  https://dx.doi.org/10.1086%2F664613
  25. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). "The Unreasonable Fairness of Maximum Nash Welfare". Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. pp. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360. http://eprints.gla.ac.uk/123283/1/123283.pdf. 
  26. Oh, Hoon; Procaccia, Ariel D.; Suksompong, Warut (2019-07-17). "Fairly Allocating Many Goods with Few Queries" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 33 (1): 2141–2148. doi:10.1609/aaai.v33i01.33012141. ISSN 2374-3468. https://www.aaai.org/ojs/index.php/AAAI/article/view/4046. 
  27. Bérczi, Kristóf; Bérczi-Kovács, Erika R.; Boros, Endre; Gedefa, Fekadu Tolessa; Kamiyama, Naoyuki; Kavitha, Telikepalli; Kobayashi, Yusuke; Makino, Kazuhisa (2020-06-08). "Envy-free Relaxations for Goods, Chores, and Mixed Items". arXiv:2006.04428 [econ.TH]. //arxiv.org/archive/econ.TH
  28. Bilò, Vittorio; Caragiannis, Ioannis; Flammini, Michele; Igarashi, Ayumi; Monaco, Gianpiero; Peters, Dominik; Vinci, Cosimo; Zwicker, William S. (2018-08-28). "Almost Envy-Free Allocations with Connected Bundles". arXiv:1808.09406 [cs.GT]. //arxiv.org/archive/cs.GT
  29. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). "The Unreasonable Fairness of Maximum Nash Welfare". Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. pp. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360. http://eprints.gla.ac.uk/123283/1/123283.pdf. 
  30. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). "Almost Envy-Freeness with General Valuations". SIAM Journal on Discrete Mathematics 34 (2): 1039–1068. doi:10.1137/19M124397X. ISSN 0895-4801. https://epubs.siam.org/doi/abs/10.1137/19M124397X. 
  31. Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A. (2020-06-01). "Maximum Nash Welfare and Other Stories About EFX". arXiv:2001.09838 [cs.GT]. //arxiv.org/archive/cs.GT
  32. Mahara, Ryoga (2020-08-20). "Existence of EFX for Two Additive Valuations". arXiv:2008.08798 [cs.GT]. //arxiv.org/archive/cs.GT
  33. Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt (2020-05-30). "EFX Exists for Three Agents". arXiv:2002.05119 [cs.GT]. //arxiv.org/archive/cs.GT
  34. Chan, Hau; Chen, Jing; Li, Bo; Wu, Xiaowei (2019-10-25). "Maximin-Aware Allocations of Indivisible Goods". arXiv:1905.09969 [cs.GT]. //arxiv.org/archive/cs.GT
  35. Amanatidis, Georgios; Ntokos, Apostolos; Markakis, Evangelos (2020). "Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination". Theoretical Computer Science 841: 94–109. doi:10.1016/j.tcs.2020.07.006.  https://dx.doi.org/10.1016%2Fj.tcs.2020.07.006
  36. Caragiannis, Ioannis; Gravin, Nick; Huang, Xin (2019-06-17). "Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items". Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19 (Phoenix, AZ, USA: Association for Computing Machinery): 527–545. doi:10.1145/3328526.3329574. ISBN 978-1-4503-6792-9. https://doi.org/10.1145/3328526.3329574. 
  37. Chaudhury, Bhaskar Ray; Kavitha, Telikepalli; Mehlhorn, Kurt; Sgouritsa, Alkmini (2019-12-23), "A Little Charity Guarantees Almost Envy-Freeness", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Proceedings (Society for Industrial and Applied Mathematics): pp. 2658–2672, doi:10.1137/1.9781611975994.162, ISBN 978-1-61197-599-4, https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.162, retrieved 2020-10-02 
  38. Suksompong, Warut (2020-09-30). "On the number of almost envy-free allocations" (in en). Discrete Applied Mathematics 284: 606–610. doi:10.1016/j.dam.2020.03.039. ISSN 0166-218X. http://www.sciencedirect.com/science/article/pii/S0166218X20301384. 
  39. Bei, Xiaohui; Li, Zihao; Liu, Jinyan; Liu, Shengxin; Lu, Xinhang (2021). "Fair division of mixed divisible and indivisible goods". Artificial Intelligence 293: 103436. doi:10.1016/j.artint.2020.103436.  https://dx.doi.org/10.1016%2Fj.artint.2020.103436
  40. Aigner-Horev, Elad; Segal-Halevi, Erel (2020-12-22). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527 [cs.DS]. //arxiv.org/archive/cs.DS
  41. John P. Dickerson; Jonathan Goldman; Jeremy Karp; Ariel D. Procaccia; Tuomas Sandholm (2014). "The Computational Rise and Fall of Fairness". In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (2014). pp. 1405–1411.  ACM link http://dl.acm.org/citation.cfm?id=2894091
More
©Text is available under the terms and conditions of the Creative Commons-Attribution ShareAlike (CC BY-SA) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Others
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
HandWiki
View Times: 2.6K
Entry Collection: HandWiki
Revision: 1 time (View History)
Update Date: 21 Oct 2022
Table of Contents
    Notice
    You are not a member of the advisory board for this topic. If you want to update advisory board member profile, please contact office@encyclopedia.pub.
    OK
    Confirm
    Only members of the Encyclopedia advisory board for this topic are allowed to note entries. Would you like to become an advisory board member of the Encyclopedia?
    Yes
    No
    ${ textCharacter }/${ maxCharacter }
    Submit
    Cancel
    There is no comment~
    ${ textCharacter }/${ maxCharacter }
    Submit
    Cancel
    ${ selectedItem.replyTextCharacter }/${ selectedItem.replyMaxCharacter }
    Submit
    Cancel
    Confirm
    Are you sure to Delete?
    Yes No
    Academic Video Service
    Feedback