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 Sirius Huang -- 4676 2022-12-02 01:31:37

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 Cake-Cutting. Encyclopedia. Available online: https://encyclopedia.pub/entry/37851 (accessed on 30 September 2026).
HandWiki. Envy-Free Cake-Cutting. Encyclopedia. Available at: https://encyclopedia.pub/entry/37851. Accessed September 30, 2026.
HandWiki. "Envy-Free Cake-Cutting" Encyclopedia, https://encyclopedia.pub/entry/37851 (accessed September 30, 2026).
HandWiki. (2022, December 02). Envy-Free Cake-Cutting. In Encyclopedia. https://encyclopedia.pub/entry/37851
HandWiki. "Envy-Free Cake-Cutting." Encyclopedia. Web. 02 December, 2022.
Envy-Free Cake-Cutting
Edit
The content is sourced from: https://handwiki.org/wiki/Envy-free_cake-cutting

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation. When there are only two partners, the problem is easy and has been solved in Biblical times by the divide and choose protocol. When there are three or more partners, the problem becomes much more challenging. Two major variants of the problem have been studied: Connected pieces, e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are n partners, only n−1 cuts are needed. General pieces, e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals.

envy-free cake-cutting heterogeneous resource

References

  1. Gamow, George; Stern, Marvin (1958). Puzzle-math. ISBN 978-0670583355. https://books.google.com/books?id=_vdytgAACAAJ. 
  2. Stromquist, Walter (1980). "How to Cut a Cake Fairly". The American Mathematical Monthly 87 (8): 640–644. doi:10.2307/2320951.  https://dx.doi.org/10.2307%2F2320951
  3. Stromquist, Walter (2008). "Envy-free cake divisions cannot be found by finite protocols". Electronic Journal of Combinatorics 15. doi:10.37236/735. http://www.emis.ams.org/journals/EJC/Volume_15/PDF/v15i1r11.pdf. 
  4. Stromquist moving-knives procedure requires the three agents to adjust their knives whenever the sword of the referee moves. Since the sword moves continuously, the number of steps required is an uncountable infinity. Simmons cake-cutting protocol converges to an envy-free division, but the convergence might require an infinite number of steps.
  5. Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for Envy-Free Cake Cutting". Operations Research 60 (6): 1461–1476. doi:10.1287/opre.1120.1116.  https://dx.doi.org/10.1287%2Fopre.1120.1116
  6. Brânzei, Simina; Nisan, Noam (2018-07-13). "The Query Complexity of Cake Cutting". arXiv:1705.02946 [cs.GT]. //arxiv.org/archive/cs.GT
  7. Brânzei, S. (2015). "A note on envy-free cake cutting with polynomial valuations". Information Processing Letters 115 (2): 93–95. doi:10.1016/j.ipl.2014.07.005.  https://dx.doi.org/10.1016%2Fj.ipl.2014.07.005
  8. Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tajik, Ahmad S. (2017-02-10). "Envy-Free Mechanisms with Minimum Number of Cuts" (in en). Thirty-First AAAI Conference on Artificial Intelligence. https://www.aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14608. 
  9. Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "Waste Makes Haste". ACM Transactions on Algorithms 13: 1–32. doi:10.1145/2988232.  https://dx.doi.org/10.1145%2F2988232
  10. Aziz, Haris; MacKenzie, Simon (2016). "FOCS 2016". Bibcode: 2016arXiv160403655A.  http://adsabs.harvard.edu/abs/2016arXiv160403655A
  11. Erel Segal-Halevi and Avinatan Hassidim and Yonatan Aumann (Jan 2015). "Envy-Free Cake-Cutting in Two Dimensions". The 29th AAAI Conference on Artificial Intelligence (AAAI-15). Austin, Texas. pp. 1021–1028. doi:10.13140/RG.2.1.5047.7923.  https://dx.doi.org/10.13140%2FRG.2.1.5047.7923
  12. Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9. 
  13. Brams, Steven J.; Taylor, Alan D.; Zwicker, William S. (1997). "A Moving-Knife Solution to the Four-Person Envy-Free Cake Division". Proceedings of the American Mathematical Society 125 (2): 547–555. doi:10.1090/S0002-9939-97-03614-9. https://www.ams.org/journals/proc/1997-125-02/S0002-9939-97-03614-9/S0002-9939-97-03614-9.pdf. Retrieved 2 September 2014. 
  14. Amin Saberi and Ying Wang (2009). "Cutting a Cake for Five People". Algorithmic Aspects in Information and Management. doi:10.1007/978-3-642-02158-9_25.  https://dx.doi.org/10.1007%2F978-3-642-02158-9_25
  15. S. J. Brams, M. A. Jones, and C. Klamler, "Better ways to cut a cake," Notices of the AMS, 2005. [Online]. Available: http://www.ams.org/notices/200611/fea-brams.pdf
  16. Pikhurko, O. (2000). "On Envy-Free Cake Division". The American Mathematical Monthly 107 (8): 736–738. doi:10.2307/2695471.  https://dx.doi.org/10.2307%2F2695471
  17. Gasarch, William (2015). "Which Unbounded Protocol for Envy Free Cake Cutting is Better?". arXiv:1507.08497 [math.LO]. //arxiv.org/archive/math.LO
  18. Aziz, Haris; MacKenzie, Simon (2016). "Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing – STOC 2016". pp. 454. doi:10.1145/2897518.2897522. ISBN 9781450341325.  https://dx.doi.org/10.1145%2F2897518.2897522
  19. Kurokawa, David; Lai, John K.; Procaccia, Ariel D (2013). "How to Cut a Cake Before the Party Ends". AAAI. http://www.aaai.org/ocs/index.php/AAAI/AAAI13/paper/viewFile/6365/7206. Retrieved 2 September 2014. 
  20. Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor's Cake". IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence: 239–244. http://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/viewFile/274/634. 
  21. Zeng, Dao-Zhi (2000). "Approximate Envy-Free Procedures" (in en). Game Practice: Contributions from Applied Game Theory. Theory and Decision Library. 23. Springer. pp. 259–271. doi:10.1007/978-1-4615-4627-6_17. ISBN 9781461546276.  https://dx.doi.org/10.1007%2F978-1-4615-4627-6_17
  22. Idzik, Adam (1995). Optimal divisions of the unit interval. Jerusalem. 
  23. Ichiishi, T.; Idzik, A. (1999). "Equitable allocation of divisible goods". Journal of Mathematical Economics 32 (4): 389–400. doi:10.1016/s0304-4068(98)00053-6.  https://dx.doi.org/10.1016%2Fs0304-4068%2898%2900053-6
  24. Dall'Aglio, M.; MacCheroni, F. (2009). "Disputed lands". Games and Economic Behavior 66: 57–77. doi:10.1016/j.geb.2008.04.006. http://www.carloalberto.org/files/no.58.pdf. 
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: 1.4K
Entry Collection: HandWiki
Revision: 1 time (View History)
Update Date: 02 Dec 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