{"id":41033,"date":"2024-05-02T10:56:48","date_gmt":"2024-05-02T10:56:48","guid":{"rendered":"https:\/\/news.talkwithrattan.com\/index.php\/2024\/05\/02\/cake-cutting-math-offers-lessons-that-go-far-beyond-dessert-plates\/"},"modified":"2024-05-02T10:56:48","modified_gmt":"2024-05-02T10:56:48","slug":"cake-cutting-math-offers-lessons-that-go-far-beyond-dessert-plates","status":"publish","type":"post","link":"https:\/\/news.talkwithrattan.com\/index.php\/2024\/05\/02\/cake-cutting-math-offers-lessons-that-go-far-beyond-dessert-plates\/","title":{"rendered":"Cake-cutting math offers lessons that go far beyond dessert plates"},"content":{"rendered":"<div style=\"text-align:center\"><img loading=\"lazy\" decoding=\"async\" width=\"592\" height=\"240\" src=\"https:\/\/i2.wp.com\/www.snexplores.org\/wp-content\/themes\/sciencenews-sns-child\/client\/src\/images\/cta-module-sm@2x.png?fit=592,240&amp;ssl=1\" class=\"attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"Cake-cutting math offers lessons that go far beyond dessert plates\" title=\"Cake-cutting math offers lessons that go far beyond dessert plates\" \/><\/div><p> <br \/>\n<\/p>\n<div data-component=\"video-embed\">\n<p>Ariel Procaccia has thought a lot about how to cut cake over the past 15 years. That\u2019s partly because he has three children. As a group, they\u2019ve celebrated more than two dozen birthdays. So Procaccia knows what it\u2019s like to stand with a knife before a tempting dessert. Sweet layers of cake. Buttercream frosting and chocolate curls. And a crowd of small, eager partygoers who will instantly spot if someone else gets a better slice.<\/p>\n<aside class=\"sn-conversion rich-text alignright\"\/>\n<p>But Procaccia is also a computer scientist at Harvard University in Cambridge, Mass. There, he studies the mathematical rules for dividing stuff up. And dessert is a handy way to think about that. It comes down to a deceptively simple question about fairness: How can you cut a cake to make sure everyone at the party is happy with what they get?<\/p>\n<p>The answers reach far beyond birthday parties. For more than 75 years, mathematicians have puzzled over how to fairly divide resources. Such questions have real-world uses. How can food be divvied up between hungry communities, for example? How should <a href=\"https:\/\/www.tandfonline.com\/doi\/abs\/10.1080\/00029890.1999.12005142\" target=\"_blank\" rel=\"noreferrer noopener\">roommates split up rent<\/a> or chores? How can <a href=\"https:\/\/www.sciencenews.org\/article\/mathematician-answers-supreme-court-plea\" rel=\"noopener\">communities draw boundaries for fair voting districts<\/a>.<\/p>\n<p>These questions include more than math, too. They must consider what people prefer and other issues. So they become interesting to scientists, economists and legal experts.<\/p>\n<p>But cake works as a stand-in for anything that can be divided, says Steven Brams. He\u2019s a game theorist and political scientist at New York University (NYU) in New York City. Cake-cutting ideas can easily be applied to splitting up land, time or other limited resources.<\/p>\n<h4 class=\"wp-block-heading\">Recipes for fair cake-cutting<\/h4>\n<p>Experts have come up with many rules, called algorithms, for how to cut a cake fairly. (Nearly all focus on rectangular cakes. The related but more recent <a href=\"https:\/\/www.sciencenews.org\/article\/cutting-pie-no-piece-cake\" rel=\"noopener\">\u201cpie-cutting\u201d problem<\/a> addresses circular desserts or pizza.) The simplest rules show how two people can fairly share a cake: One person cuts the cake into two pieces that they believe to be equal in value. The other person chooses between them. Each eater receives a piece that they feel is at least as valuable as the other\u2019s, if not better.<\/p>\n<aside class=\"wp-block-sciencenews-inline-related-post alignleft\">\n<h4><a href=\"https:\/\/www.snexplores.org\/article\/explainer-what-is-an-algorithm\">Explainer: What is an algorithm?<\/a><\/h4>\n<\/aside>\n<p>Reports of this strategy date back to ancient Greece.<\/p>\n<p>In the 1940s, mathematicians started using cake-cutting as a way to study fairness. The \u201cI cut, you choose\u201d method works for two people. What about sharing among three or more? That has led to new challenges, such as: What is fairness, exactly \u2014 and how do you prove it?<\/p>\n<p>Here\u2019s one way to think about fairness. Maybe each person is satisfied if they feel like their slice represents a fair share of the total. For two people, a fair share would be 1\/2; for three, it would be 1\/3, and so on. (And for some arbitrary n number of cake eaters, a fair share would be 1\/n.) If the cake is the same throughout, all the slices just need to be the same size. That\u2019s not too hard to manage with a knife and a ruler or kitchen scale.<\/p>\n<p>But what about when the cake is not all the same? Maybe it\u2019s topped with a few icing roses or artfully placed cookies. The corner pieces may have more frosting. A maraschino cherry\u2013lover might be happy with the smallest slice if they get the cake\u2019s only cherry. To them, that piece is more valuable than a larger slice.<\/p>\n<p>For two people, I-cut-you-choose still works with a non-uniform cake. The divider cuts the cake into two pieces they view as equal; the chooser then picks their preferred piece. But add more cake eaters, each with their own preferences, and easy solutions crumble.<\/p>\n<h4 class=\"wp-block-heading\">More eaters, more cuts<\/h4>\n<p>Hugo Steinhaus was one of the first mathematicians to dive into this complexity. He worked at the University of Warsaw in Poland in the 1940s. During World War II, he saw questions about fair division of land playing out on a large and violent scale. Steinhaus came up with a modified I-cut-you-choose strategy for three players.<\/p>\n<p>It came to be called the lone-divider method.<\/p>\n<p>Here, someone cuts the cake. Let\u2019s call her Alice. She cuts three pieces that she values equally (each at 1\/3 of the total). Then a second person, Bob, says which of the pieces he would accept. If he approves at least two pieces, then the third person, Carla, can take any piece she wants. At least one of the remaining pieces is acceptable to Bob. So he picks next. Alice gets what\u2019s left.<\/p>\n<p>If Bob and Carla both turn down the same piece, that piece goes to Alice. She valued all pieces equally, so it still seems fair to her. The remaining two pieces are recombined and shared between Bob and Carla using I-cut-you-choose.<\/p>\n<p>Steinhaus described this method in a short paper published in 1948. It was one of the first serious studies in the field of cake-cutting. And it worked for three eaters.<\/p>\n<div class=\"wp-block-group cheat-sheet-cta is-layout-flow\">\n<div class=\"wp-block-group__inner-container\">\n<h2 class=\"wp-block-heading has-text-align-center\">Do you have a science question? We can help!<\/h2>\n<p class=\"has-text-align-center\"><a href=\"https:\/\/forms.gle\/YbhPosFTMqjbSNnV7\" target=\"_blank\" rel=\"noreferrer noopener\">Submit your question here<\/a>, and we might answer it an upcoming issue of\u00a0<em>Science News Explores<\/em><\/p>\n<\/div>\n<\/div>\n<p>In the same paper, though, he discussed an algorithm developed by two of his colleagues. This \u201clast-diminisher\u201d method could work for any number of cake eaters.<\/p>\n<p>Here, someone cuts off a piece of cake they think is a fair share and passes it to the next person. Each other person at the party has a choice. They can pass the piece along, if they agree it\u2019s fair or less than a fair share. Or, if they think it\u2019s too big, they can trim it. Once everyone has had a chance to trim, or \u201cdiminish\u201d the slice, the last person who trimmed gets the piece and exits the game.<\/p>\n<p>Any bits trimmed off are added back to the remaining cake, and the process begins again with the remaining players. When only two players are left, they use I-cut-you-choose.<\/p>\n<p>The last-diminisher method guarantees that everyone judges their own piece to be at least a fair share. But it\u2019s not perfect. That\u2019s because it doesn\u2019t account for envy. In both the lone-divider and last-diminisher approaches, a person who gets an early slice may see a later one they wish they had instead \u2014 even though they had at first thought their piece was fair.<\/p>\n<p>Last-diminisher has another flaw, too. If lots of people trim, the cake may be reduced to crumbs in later rounds. And that might feel unfair no matter how big your pile is.<\/p>\n<h4 class=\"wp-block-heading\">Can cake cutting be free of envy?<\/h4>\n<p>After the lone diminisher, mathematicians continued to search for envy-free ways to divide something. In the 1960s, John Conway and John Selfridge each came up with the same idea for how three people can each feel they got a fair share, with no envy by others.<\/p>\n<p>In their plan, Alice first splits the cake into three pieces. She believes each are of equal value. Then, Bob can trim one piece \u2014 at most \u2014 to create a two-way tie for the most valuable. (Any trimmings are set aside.) Carla is left to choose among the three. Then the order reverses. If Carla didn\u2019t choose the trimmed piece, Bob takes it. Alice gets the one that remains. Then the eaters turn to the trimmings. They follow a similar process of cutting, trimming and choosing.<\/p>\n<p>In 1995, another team showed how to extend this approach to any number of people. Brams at NYU worked with Alan\u00a0D. Taylor of Union College in Schenectady, N.Y. Their method applied the \u201ctrimming\u201d idea using all possible pairs of cake diners. \u201cThat was considered a breakthrough of sorts,\u201d Brams says.<\/p>\n<p>The approach still had its limits, however. There was no guarantee of how many cuts it might take. \u201cWe showed in general that you could require three cuts or 3 million cuts,\u201d Brams says. Or even more.<\/p>\n<h4 class=\"wp-block-heading\">The cake-cutting problem endures<\/h4>\n<p>The algorithms discussed so far assume that all eaters play fair. That is, all try to achieve pieces that will feel like a fair share to everyone else. But people aren\u2019t always honest.<\/p>\n<p>This is something Biaoshuai Tao recognizes. Tao is a computer scientist at Shanghai Jiao Tong University in China. And he studied what happens <a href=\"https:\/\/arxiv.org\/pdf\/2104.07387.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">when you try to account for dishonest cake eaters<\/a>. \u201cIf everyone knows how the cake is allocated, then I should get more if I tell the truth,\u201d he says.<\/p>\n<p>But in some cases, dishonesty can give an advantage. Say Alice and Bob are going to split a cake. If Alice knew that Bob always preferred chocolate, she might cut the cake unequally on purpose so the smaller piece contained more chocolate. Then, if Bob chose according to his preference, Alice would get the larger slice.<\/p>\n<section class=\"newsletter-signup__wrapper___lZ0W1 wp-block-house-ads wp-block-newsletter-signup\">\n<picture><source srcset=\"https:\/\/www.snexplores.org\/wp-content\/themes\/sciencenews-sns-child\/client\/src\/images\/cta-module@1x.png 1x,&#10;&#9;&#9;&#9;&#9;https:\/\/www.snexplores.org\/wp-content\/themes\/sciencenews-sns-child\/client\/src\/images\/cta-module@2x.png 2x\" media=\"(min-width: 768px)\"><source srcset=\"https:\/\/www.snexplores.org\/wp-content\/themes\/sciencenews-sns-child\/client\/src\/images\/cta-module-sm@1x.png 1x,&#10;&#9;&#9;&#9;&#9;https:\/\/www.snexplores.org\/wp-content\/themes\/sciencenews-sns-child\/client\/src\/images\/cta-module-sm@2x.png 2x\"><\/source><\/source><\/picture>\n<div class=\"newsletter-signup__container___srNOL\" data-component=\"newsletter-signup\">\n<h3 class=\"newsletter-signup__heading___0EHmb\">\n\t\t\tEducators and Parents, Sign Up for The Cheat Sheet\t\t<\/h3>\n<div class=\"newsletter-signup__message___pemaq\">\n<p>Weekly updates to help you use <em>Science News Explores<\/em> in the learning environment<\/p>\n<\/p><\/div>\n<p class=\"newsletter-signup__thankyou___K6GGN\">Thank you for signing up!<\/p>\n<p class=\"newsletter-signup__error___hCsJI\">There was a problem signing you up.<\/p>\n<\/p><\/div>\n<\/section>\n<p>In a 2010 paper, Procaccia asked a curious question: Can there be a way to cut cake that guarantees honesty <em>and<\/em> fairness? More than 10 years later, the answer seems to be: no.<\/p>\n<p>Tao used math to show it is <a href=\"https:\/\/arxiv.org\/abs\/2104.07387v3\" rel=\"noopener\">impossible to cut cake in a way that promises truthfulness and fairness<\/a>, with no envy. He presented this at a July 2022 meeting in Boulder, Colo. It was held by the Association for Computing Machinery Conference on Economics and Computation.<\/p>\n<figure class=\"wp-block-image alignwide size-full\"><img loading=\"lazy\" width=\"1440\" height=\"810\" decoding=\"async\" src=\"https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover.jpg\" alt=\"Cartoon illustration shows four people around a cake with lots of dashed lines to indicate where one might cut. One person holds a knife and looks perplexed. Two people point to different sections, and one person holds frosting on their finger.\" class=\"wp-image-3131020\" srcset=\"https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover.jpg 1440w, https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover-680x383.jpg 680w, https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover-800x450.jpg 800w, https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover-330x186.jpg 330w, https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover-768x432.jpg 768w, https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover-1030x580.jpg 1030w, https:\/\/www.snexplores.org\/wp-content\/uploads\/2023\/09\/090923_cake_cover-1380x776.jpg 1380w\" sizes=\"(max-width: 1440px) 100vw, 1440px\"\/><figcaption class=\"wp-element-caption\"><span class=\"caption wp-caption-3131020\">The cake-cutting problem asks: How can you cut a cake to guarantee that everyone is happy with what they get?<\/span><span class=\"credit wp-credit-3131020\">MADELINE MCMAHON<\/span><\/figcaption><\/figure>\n<h4 class=\"wp-block-heading\">Beyond cake<\/h4>\n<p>Cake-cutting is easy to relate to, says Bettina Klaus. And it has lots of practical uses. At the University of Lausanne in Switzerland, Klaus studies fairness in real-world situations. Dividing things fairly \u201cis mathematically interesting and challenging,\u201d she says. And its complexity grows with the number of people who want to share.<\/p>\n<p>One example she studies is school choice. Here, a school district has limited seats in certain schools. \u201cIn the past, schools were just assigned [to students] \u2026 without asking people what they want,\u201d Klaus says. More recently, she notes, schools have tried to place students where they want to go (or where their parents want them to go). They also have to follow rules set by the school board. Deciding how to fairly assign those seats means balancing the priorities of these groups.<\/p>\n<p>Other real-world applications show up almost everywhere you look.<\/p>\n<p>Brams has used ideas from cake cutting to study fair voting procedures. (To elect their leaders, at least four scientific societies adopted an algorithm he developed. The Mathematical Association of America is one.)<\/p>\n<p>In 2014, Procaccia was part of a team that designed a web-based tool called Spliddit. Based on users\u2019 preferences, it produced mathematically fair ways to divide anything. It might be rent among roommates or even possessions among divorcees.<\/p>\n<p>Even after decades of study, cake cutting defies a simple solution. Indeed, the more researchers explore it, the more there seems to be to explore.<\/p>\n<p>\u201cI\u2019m interested in it now not only because it\u2019s beautiful in math,\u201d Tao says, but also because \u201cI still believe there\u2019s a lot to be done.\u201d<\/p>\n<aside class=\"sn-conversion rich-text\"\/><\/div>\n<p><br \/>\n<br \/><a href=\"https:\/\/www.snexplores.org\/article\/math-cake-cutting-fairness-sharing\">Source link <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ariel Procaccia has thought a lot about how to cut cake over the past 15 years. That\u2019s partly because he has three children. As a group, they\u2019ve celebrated more than two dozen birthdays. So Procaccia knows what it\u2019s like to stand with a knife before a tempting dessert. Sweet layers of cake. Buttercream frosting and [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":41034,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":"","fifu_image_url":"https:\/\/www.snexplores.org\/wp-content\/themes\/sciencenews-sns-child\/client\/src\/images\/cta-module-sm@2x.png","fifu_image_alt":"","footnotes":""},"categories":[606],"tags":[42926,42927,11896,38826,1069,42928],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/posts\/41033"}],"collection":[{"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/comments?post=41033"}],"version-history":[{"count":1,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/posts\/41033\/revisions"}],"predecessor-version":[{"id":41035,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/posts\/41033\/revisions\/41035"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/media\/41034"}],"wp:attachment":[{"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/media?parent=41033"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/categories?post=41033"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/news.talkwithrattan.com\/index.php\/wp-json\/wp\/v2\/tags?post=41033"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}