{"id":519,"date":"2019-06-29T22:08:20","date_gmt":"2019-06-29T22:08:20","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=519"},"modified":"2019-11-19T00:23:42","modified_gmt":"2019-11-19T00:23:42","slug":"envy-free-cake-division","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/envy-free-cake-division\/","title":{"rendered":"Envy-free Cake Division"},"content":{"rendered":"\n
\"\"<\/figure><\/div>\n\n\n\n

Say you and a friend wish to share a cake. What is a “fair” way to split it? Probably you know this solution: one cuts, the other chooses. This is called a fair division algorithm<\/em>, because by playing a good strategy, each player can guarantee she gets at least 50 percent of the cake in her own measure<\/em>. See if you can reason why. <\/p>\n\n\n\n

Now, what about for 3 people? Is there an algorithm that guarantees each person what she feels is the largest<\/em> piece? Such a division is called an envy-free<\/em> division. Here is a procedure due to Selfridge and Conway. We mark strategies [in brackets]. Suppose the players are named Alice, Betty, Chuck.<\/p>\n\n\n\n

  1. Alice cuts [into what she thinks are thirds].<\/li>
  2. Betty trims one piece [to create a 2-way tie for largest], and sets the trimmings aside.<\/li>
  3. Let Chuck pick a piece, then Betty, then Alice. Require Betty to take a trimmed piece if Charlie does not. Call the person who tooked the trimmed piece T, and the other (of Betty and Chuck) NT.<\/li>
  4. To deal with the trimmings, let NT cut them [into what she thinks are thirds].<\/li>
  5. Let players pick pieces in this order: T, Alice, then NT.<\/li><\/ol>\n\n\n\n

    Presentation Suggestions:<\/strong>
    Be sure you follow the argument before you present it, because it can be confusing! Draw pictures.<\/p>\n\n\n\n

    The Math Behind the Fact:<\/strong>
    It is a good exercise to verify why each person is envy-free by the end of the procedure. The key observation is that for the trimmings, Alice has an “irrevocable advantage” with respect to T, since Alice will never envy T even if T gets all the trimmings. Thus Alice can pick after T, and this allows the procedure to terminate in a finite number of steps. For 4 or more players, there is an envy-free solution that is very complex, and can take arbitrarily long to resolve. See the references.<\/p>\n\n\n\n

    There are other notions of fairness besides envy-freeness. Proportional<\/em> fairness is weaker; it only demands each person gets what she feels is at least 1\/N of the cake. You might enjoy figuring out an N-person proportional procedure.<\/p>\n\n\n\n

    Questions of fairness are considered by mathematicians and economists in the subject of\u00a0game theory.<\/p>\n\n\n\n

    How to Cite this Page:<\/strong> 
    Su, Francis E., et al. “Envy-free Cake Division.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

    References:<\/strong>
    S.J. Brams and A.D. Taylor, Fair Division: from cake-cutting to dispute-resolution, Cambridge, 1996.
    J. Robertson and W. Webb, Cake-cutting Algorithms, AK Peters, 1998.<\/p>\n\n\n\n

    Fun Fact suggested by: <\/strong>
    Francis Su<\/p>\n","protected":false},"excerpt":{"rendered":"

    Say you and a friend wish to share a cake. What is a “fair” way to split it? Probably you...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[57,98,9,58,12,97],"class_list":["post-519","page","type-page","status-publish","hentry","tag-advanced","tag-cake-cutting","tag-combinatorics","tag-game-theory","tag-other","tag-social-science"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/519","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=519"}],"version-history":[{"count":5,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/519\/revisions"}],"predecessor-version":[{"id":1421,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/519\/revisions\/1421"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=519"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=519"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}