{"id":25309,"date":"2015-03-16T15:07:51","date_gmt":"2015-03-16T20:07:51","guid":{"rendered":"http:\/\/blogs.ams.org\/mathgradblog\/?p=25309"},"modified":"2015-11-01T23:25:10","modified_gmt":"2015-11-02T04:25:10","slug":"lone-divider-method-divide-pie","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/mathgradblog\/2015\/03\/16\/lone-divider-method-divide-pie\/","title":{"rendered":"Lone-Divider Method – How to Fairly Divide a Pie"},"content":{"rendered":"
\"Photo<\/a>

Photo acquired from Wikimedia Commons, the free media repository<\/p><\/div>\n

Saturday was the Pi Day of a lifetime \u2013 3\/14\/15 9:26:53! Hopefully all of you were able to share some delicious pie with your friends and family. When slicing up your pie how can you make sure everyone received a fair share? It’s the Lone-Divider Method to the rescue!<\/p>\n

<\/p>\n

The Lone-Divider Method for N players dividing a pie can be described by the following process:<\/p>\n

Preliminaries<\/b> \u2013 As the name suggests, one of the players is chosen to be the divider, D, while the other N-1 players act as choosers. It’s always better to be one of the choosers than to be the divider \u2013 the divider is guaranteed a piece worth exactly \"\frac{1}{N}\" of the total value of the pie whereas the choosers have a chance to get a piece worth more than \"\frac{1}{N}\" of the total value. Since we want this method to be fair to all players, everyone should have an equal chance of being the divider (which can be done randomly).<\/p>\n

Step 1 (Division)<\/b> \u2013 The divider, D, divides the pie into N pieces (\"s_{1},). The divider knows that he\/she will receive one of these pieces, but at this point does not know which one. This is important because it forces D to divide the cake into N slices that to him\/her have equal value.<\/p>\n

Step 2 (Bidding)<\/b> \u2013 Each of the N-1 choosers submits a bid that lists every piece he or she considers to be a fair share (i.e. worth \"\frac{1}{N}\" or more of the total value of the pie). These bids are made secretly and independently of the other choosers.<\/p>\n

Step 3 (Distribution)<\/b> \u2013 The bid lists are opened. Depending on these lists, there are two different ways we may have to proceed.<\/p>\n

Case 1<\/b> \u2013 If there is a way to assign a different slice of pie to each of the N-1 choosers, then that should be done. The divider (who equally prefers all of the pie slices)gets the last unassigned slice. At the end, the players may choose to swap pieces if they want.<\/p>\n

Case 2<\/b> \u2013 There is a standoff! In this case, there are two choosers bidding for the same piece of pie (or K choosers bidding for fewer than K pieces). This case is complicated and we give a brief overview of how to proceed when a standoff occurs. First, we set aside any of the pieces of pie that were involved in the standoff. In addition, we temporarily separate any players involved in the standoff from the others. It is possible for multiple standoffs to occur and each standoff is handled individually. For ease of explanation, we assume only one standoff has occurred. Once the standoff players and pie slices are isolated, each of the remaining players (including the divisor) is assigned a fair share from the remaining pie pieces. All the remaining pie pieces (those involved in the standoff) are then recombined into a new \u201cpie\u201d S to be divided among the players involved in the standoff and the process starts all over again.<\/p>\n

We will consider two examples to illustrate the two cases that can occur in the distribution step. Four friends, Abby, Jenny, Ellie, and Maddie, want to share a pie for pi day. Abby is randomly chosen as the divider and cuts the pie into four pieces (\"s_1, and \"s_4\"). The following table shows how each of the friends values the four pieces.<\/p>\n\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n
<\/td>\n\n

s1<\/sub><\/b><\/p>\n<\/td>\n

\n

s2<\/sub><\/b><\/p>\n<\/td>\n

\n

s3<\/sub><\/b><\/p>\n<\/td>\n

\n

s4<\/sub><\/b><\/p>\n<\/td>\n<\/tr>\n

\n

Abby<\/b><\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n<\/tr>\n

\n

Jenny<\/b><\/p>\n<\/td>\n

\n

40%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n<\/tr>\n

\n

Ellie<\/b><\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

40%<\/p>\n<\/td>\n

\n

15%<\/p>\n<\/td>\n<\/tr>\n

\n

Maddie<\/b><\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

30%<\/p>\n<\/td>\n

\n

30%<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

In this example, Jenny’s bid list is {\"s_{1}\"} only, Ellie’s bid list is {\"s_{1},}, and Maddie’s bid list is {\"s_{3},}. It is clear that Jenny must get \"s_{1}\" – there is no other option. This forces the rest of the distribution. Piece \"s_{3}\" must then go to Ellie and piece \"s_{4}\" goes to Maddie. Finally, the remaining piece of pie, \"s_{2}\" goes to the divider, Abby.<\/p>\n

In our next example, we see what happens when a standoff occurs. Again our four friends, Abby, Jenny, Ellie, and Maddie, want to share a pie for pi day, with Abby being named the divider. Abby cuts the pie into four pieces (\"s_1, and \"s_4\"). The following table shows how each of the friends values the four pieces.<\/p>\n\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n
<\/td>\n\n

s1<\/sub><\/b><\/p>\n<\/td>\n

\n

s2<\/sub><\/b><\/p>\n<\/td>\n

\n

s3<\/sub><\/b><\/p>\n<\/td>\n

\n

s4<\/sub><\/b><\/p>\n<\/td>\n<\/tr>\n

\n

Abby<\/b><\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n<\/tr>\n

\n

Jenny<\/b><\/p>\n<\/td>\n

\n

40%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n<\/tr>\n

\n

Ellie<\/b><\/p>\n<\/td>\n

\n

35%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

22%<\/p>\n<\/td>\n

\n

23%<\/p>\n<\/td>\n<\/tr>\n

\n

Maddie<\/b><\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

20%<\/p>\n<\/td>\n

\n

35%<\/p>\n<\/td>\n

\n

25%<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

In this example, Jenny’s bid list is {\"s_{1}\"} only, Ellie’s bid list is {\"s_{1}\"} only, and Maddie’s bid list is {\"s_{3},}. It is clear that we have a standoff \u2013 both Jenny and Ellie want piece \"s_{1}\"! The first step of the distribution process is to set piece \"s_{1}\" aside and assign Abby and Maddie a fair share from \"s_{2}, and \"s_{4}\". Notice that Maddie could be given either piece \"s_{3}\" or \"s_{4}\". She would prefer to have \"s_{3}\", but that’s not for her to decide at this point \u2013 a coin toss can be used to determine which piece Maddie receives. Let’s say Maddie ends up with \"s_{3}\". Then Abby could be given either piece \"s_{2}\" or \"s_{4}\". Another coin toss determines that Abby receives piece \"s_{2}\". Now we must determine what Jenny and Ellie receive. At this point, we recombine the remaining pie pieces (\"s_{1}\" and \"s_{4}\") into a single piece to be divided between Jenny and Ellie using the divider-chooser method. Since \"(s_{1} is worth 60% to Jenny and 58% to Ellie, regardless of how this final division plays out they are both guaranteed a final share worth more than 25% of the pie. When all is said and done, every player ends up with a fair share.<\/p>\n

This method works equally well for cake and pizza (or any other continuously divisible items). So go out and enjoy, knowing you are now equipped with a method to fairly divide your pie, cake, and pizza! Happy Pi Day!<\/p>\n

Sources:<\/p>\n

Tannenbaum, Peter. Excursions in Modern Mathematics (Sixth Edition)<\/i>. Upper Saddle River, N.J: Pearson Prentice Hall, 2007.<\/p>\n

\n

<\/div>","protected":false},"excerpt":{"rendered":"

Saturday was the Pi Day of a lifetime \u2013 3\/14\/15 9:26:53! Hopefully all of you were able to share some delicious pie with your friends and family. When slicing up your pie how can you make sure everyone received a … Continue reading →<\/span><\/a><\/p>\n

<\/div>\n","protected":false},"author":68,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[8,12,15],"tags":[],"class_list":["post-25309","post","type-post","status-publish","format-standard","hentry","category-general","category-math","category-mathematics-in-society"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3gbww-6Ad","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/25309","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/users\/68"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/comments?post=25309"}],"version-history":[{"count":12,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/25309\/revisions"}],"predecessor-version":[{"id":26431,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/25309\/revisions\/26431"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/media?parent=25309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/categories?post=25309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/tags?post=25309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}