6 ms·

Fair Cake-Cutting

77 points by RetroTechie 3y ago

dang 3y ago
Recent and related: A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents (2016) - https://news.ycombinator.com/item?id=39060958 https://news.ycombinator.com/item?id=39060958 - Jan 2024 (9 comments) Also: New Algorithm Solves Cake-Cutting Problem (2016) - https://news.ycombinator.com/item?id=18432128 https://news.ycombinator.com/item?id=18432128 - Nov 2018 (37 comments) “I-Cut-You-Choose” Cake-Cutting Protocol Inspires Solution to Gerrymandering - https://news.ycombinator.com/item?id=17459008 https://news.ycombinator.com/item?id=17459008 - July 2018 (102 comments) A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents - https://news.ycombinator.com/item?id=15396643 https://news.ycombinator.com/item?id=15396643 - Oct 2017 (1 comment) New algorithm that can fairly divide a cake among any number of people - https://news.ycombinator.com/item?id=12920642 https://news.ycombinator.com/item?id=12920642 - Nov 2016 (1 comment) How to Cut Cake Fairly and Finally Eat It Too - https://news.ycombinator.com/item?id=12665340 https://news.ycombinator.com/item?id=12665340 - Oct 2016 (1 comment) How Mathematicians Cut Cake - https://news.ycombinator.com/item?id=12392936 https://news.ycombinator.com/item?id=12392936 - Aug 2016 (43 comments) Essential advice on how to cut a cake fairly at a party. - https://news.ycombinator.com/item?id=638480 https://news.ycombinator.com/item?id=638480 - June 2009 (6 comments)
13415 3y ago
There is a nice introduction to the topic in case someone is interested (but it's older): Cake-Cutting Algorithms, by Jack Robertson and William Webb. A.K. Peters 1998. IMHO it's worth pointing out that the topic has fewer applications than one might think. Many problems where cake-cutting algorithms might seem adequate are better addressed with social choice/voting theory.
jeeyoungk 3y ago
I've been thinking about the cake cutting problem recently, with a bit more "physical world" and dexterity in mind. Even in the two-player version, one can add few more criterion. * Cutting a cake is a skill; it takes an effort (thus associated cost) and you may not be accurate at cutting it. There may be some error bound epsilon. * If so, in the traditional "I cut you choose" model, as there are risks associated with cutting (what if you intend fairness, but you ended up with lopsided 49:51 cake due to an error?), one may not volunteer to cut the cake; if so, how can we encourage / compensate one to cut the cake? * The "skill" can go both ways; it takes an effort to figure out which cake is bigger - even more then the cut itself. both parties may volunteer to cut the cake. if so, how can we encourage / compensate one to be the chooser?
- deleted 3y ago
  [deleted]
- videogreg93 3y ago
  Assuming a homogeneous cake, I think you can get around this by cutting the cake in half, and then cutting a line perpendicular to that one. Each person takes 2 pieces that touch each other diagonally, which should in theory give each person half of the cake.
  - lupire 3y ago
    That requires "cutting the cake in half", which is begging the question, and also makes the second cut irrelevant. If the first cut is not a true half, then the method doesn't work. It gives you equal perimeter cuts, nt equal area cuts. That method is slightly better than making only one cut, though.
- MichaelZuo 3y ago
  > If so, in the traditional "I cut you choose" model, as there are risks associated with cutting (what if you intend fairness, but you ended up with lopsided 49:51 cake due to an error?), one may not volunteer to cut the cake; if so, how can we encourage / compensate one to cut the cake? Why is that important? There's always someone willing to step up to the plate, if person A doesn't want to, then person B, or C, etc...
dweinus 3y ago
Only a mathematician could think that when people are arguing over a cake, the best solution involves giving everyone a knife (Stromquist moving-knives procedure)
quonn 3y ago
I can‘t help but think that when I cut one half just slightly bigger or better the chooser will pick the smaller version due to wanting to be polite.
- deleted 3y ago
  [deleted]
cheeseomlit 3y ago
If I get a piece with big globs of decorative frosting I'm just gonna scrape most of it off anyways. Way too sweet
Pathogen-David 3y ago
Up and Atom recently made a great video explaining this class of problems and some of the algorithms for solving it: https://youtu.be/fvM8ow6zNw4 https://youtu.be/fvM8ow6zNw4
pitdicker 3y ago
When it comes to economics it never ceases to amaze me that we build an entire system on the basic assumption that everyone acts primarily in their own self-interest, and that that system somewhat manages to function. Luckily when it comes to regular cake cutting there may be a host involved that just wants to give his guests something nice. And the guests hopefully just enjoy the cake instead of being overly sensitive about the fairness of the divisions.
- shafyy 3y ago
  What system are you referring to?
- HEmanZ 3y ago
  When the host gives their guest something nice, the host is acting on their interest to please their guest. Or their interest in being a friend. Or their interest in seeing their guest happy. By definition, the only interest you posses is your own, even if that interest is a benefit to someone else. Only straw-man arguments in economics use self interest to literally mean like “hedonic self interest” or layman’s self interest. Economics actually does the opposite, the “self interest” is basically “whatever people want”. What do people want? They want to maximize their utility! What is utility? Whatever people want!
- crazygringo 3y ago
  I hope it's clear that this isn't about actual cake cutting. But rather as a stand-in for any resource that people want to figure out a fair, equitable way to distribute. So you should read this as a guide to how different countries might be willing to fairly divide a contested piece of land, when different parts of the land have different qualities (e.g. suitability for farming, value in mining) and the different countries value those things differently (e.g. one is good at building mines, the other prefers to protect the environment). There are a lot of conflicts in the world over resources that need to be divvied up in some way, where everyone really is looking out for the self-interest of their state or nation or community.
  - RetroTechie 3y ago
BizarroLand 3y ago
Reminds me of the book Triple Detente by Piers Anthony https://www.goodreads.com/book/show/263431.Triple_Detente https://www.goodreads.com/book/show/263431.Triple_Detente One of the core logical premises of the book is how three groups can handle an unsteady alliance where each group is primarily interested in saving their own people.
cpdean 3y ago
There's a really interesting boardgame based on the cake-cutting problem https://boardgamegeek.com/boardgame/173648/booty https://boardgamegeek.com/boardgame/173648/booty . You play many rounds of trying to fairly divvy up piles of loot. Different pieces combine in ways to increase their overall value, as well as each piece having a base level amount of value. As a result the actual act of dividing it fairly becomes complicated, and players will try to influence the outcome in order to maximize their score at the end of the game to win.
- shagie 3y ago
  I’d also recommended board game New York slice. https://boardgamegeek.com/boardgame/208895/new-york-slice https://boardgamegeek.com/boardgame/208895/new-york-slice and the “I cut you choose” mechanic section https://boardgamegeek.com/boardgamemechanic/2906/i-cut-you-choose https://boardgamegeek.com/boardgamemechanic/2906/i-cut-you-c...
  - cpdean 3y ago
    I love that as a skinning of that genre haha
    - shagie 3y ago
      It has a "cut here" mechanic to it - you can't decide on the order of slices. > The Slicer starts by choosing a stack of 11 slices and its corresponding Special. Then the Slicer first flips the Special face up in the center of the table, reading it to the players, and then flips each slice face up in the center of the table. As each slice is flipped, it is placed directly next to the previous slice; the Slicer must continue to place slices in the same direction (clockwise or counterclockwise), with each slice being next to the last. The 11 slices will form a circle, with the last slice being next to the first slice. > The Slicer then divides the pizza into as many portions as there are players. For instance, if there are four players, the pizza would be divided into four portions. Each portion can have any number of slices, as long as it has at least one slice or the Special (the Special may be either combined with slices or placed by itself as its own portion). When dividing the pizza, the Slicer may not rearrange or change the order of the slices in any way. Note the 1/11th of a circle makes it so that it is never an easy even cut.
crazygringo 3y ago
Oh wow. I'd never heard of any of this, but it reminds me a lot of the different methods for voting [1]. After all, at heart there are a lot of parallels -- how do you reconcile different preferences and resources to split up a cake fairly, vs. how do you reconcile different preferences to split up the resource of power fairly, whether to elect a single person (e.g. a president) or a parliament? [1] https://en.wikipedia.org/wiki/Electoral_system https://en.wikipedia.org/wiki/Electoral_system
- DominikPeters 3y ago
  Indeed, there are many parallels, and in academia the same sort of people study both topics (e.g. in "computational social choice"), and they are often taught in the same lecture series (e.g. https://sites.google.com/view/optdemocracy23 https://sites.google.com/view/optdemocracy23, https://rohitvaish.in/Teaching/2023-Fall/ https://rohitvaish.in/Teaching/2023-Fall/). There is an important difference though: elections concern making one decision that affects everyone, whereas (fair) allocation involves deciding who gets what, and everyone is only affected by what they themselves get. It's the distinction between public and private goods.
yboris 3y ago
Algorithm for two people sharing any food: 1st person cuts, 2nd person chooses which of the pieces to take.
- laweijfmvo 3y ago
  For three people: https://www.youtube.com/watch?v=kaMKInkV7Vs https://www.youtube.com/watch?v=kaMKInkV7Vs
nntwozz 3y ago
The perfect solution to this problem is to put the cake in a blender and serve it in cups.
Tagbert 3y ago
I recall reading a science fiction story in one of the magazines like “Analog” several decades ago that used this concept as a major plot point. Two Planets were at risk of all out war and were evenly matched such that the results would be devastation for both. They negotiated a solution whereby each would proceed to “invade” the other’s planet and rule but each would observe how well the other ruled and could retaliate. This caused them to be scrupulously fair in their ruling. I don’t recall the name of the story or the author. This was likely in the late 60’s or early 70’s. I’m not sure why, if they could negotiate such a complex solution that they couldn’t just negotiate a secession of hostilities but the point of the story was to illustrate the cake principle.

77 points by RetroTechie 3y ago

dang 3y ago

Recent and related: A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents (2016) - https://news.ycombinator.com/item?id=39060958 https://news.ycombinator.com/item?id=39060958 - Jan 2024 (9 comments) Also: New Algorithm Solves Cake-Cutting Problem (2016) - https://news.ycombinator.com/item?id=18432128 https://news.ycombinator.com/item?id=18432128 - Nov 2018 (37 comments) “I-Cut-You-Choose” Cake-Cutting Protocol Inspires Solution to Gerrymandering - https://news.ycombinator.com/item?id=17459008 https://news.ycombinator.com/item?id=17459008 - July 2018 (102 comments) A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents - https://news.ycombinator.com/item?id=15396643 https://news.ycombinator.com/item?id=15396643 - Oct 2017 (1 comment) New algorithm that can fairly divide a cake among any number of people - https://news.ycombinator.com/item?id=12920642 https://news.ycombinator.com/item?id=12920642 - Nov 2016 (1 comment) How to Cut Cake Fairly and Finally Eat It Too - https://news.ycombinator.com/item?id=12665340 https://news.ycombinator.com/item?id=12665340 - Oct 2016 (1 comment) How Mathematicians Cut Cake - https://news.ycombinator.com/item?id=12392936 https://news.ycombinator.com/item?id=12392936 - Aug 2016 (43 comments) Essential advice on how to cut a cake fairly at a party. - https://news.ycombinator.com/item?id=638480 https://news.ycombinator.com/item?id=638480 - June 2009 (6 comments)

13415 3y ago

There is a nice introduction to the topic in case someone is interested (but it's older): Cake-Cutting Algorithms, by Jack Robertson and William Webb. A.K. Peters 1998. IMHO it's worth pointing out that the topic has fewer applications than one might think. Many problems where cake-cutting algorithms might seem adequate are better addressed with social choice/voting theory.

jeeyoungk 3y ago

I've been thinking about the cake cutting problem recently, with a bit more "physical world" and dexterity in mind. Even in the two-player version, one can add few more criterion. * Cutting a cake is a skill; it takes an effort (thus associated cost) and you may not be accurate at cutting it. There may be some error bound epsilon. * If so, in the traditional "I cut you choose" model, as there are risks associated with cutting (what if you intend fairness, but you ended up with lopsided 49:51 cake due to an error?), one may not volunteer to cut the cake; if so, how can we encourage / compensate one to cut the cake? * The "skill" can go both ways; it takes an effort to figure out which cake is bigger - even more then the cut itself. both parties may volunteer to cut the cake. if so, how can we encourage / compensate one to be the chooser?

deleted 3y ago
[deleted]
videogreg93 3y ago
Assuming a homogeneous cake, I think you can get around this by cutting the cake in half, and then cutting a line perpendicular to that one. Each person takes 2 pieces that touch each other diagonally, which should in theory give each person half of the cake.
- lupire 3y ago
  That requires "cutting the cake in half", which is begging the question, and also makes the second cut irrelevant. If the first cut is not a true half, then the method doesn't work. It gives you equal perimeter cuts, nt equal area cuts. That method is slightly better than making only one cut, though.
MichaelZuo 3y ago
> If so, in the traditional "I cut you choose" model, as there are risks associated with cutting (what if you intend fairness, but you ended up with lopsided 49:51 cake due to an error?), one may not volunteer to cut the cake; if so, how can we encourage / compensate one to cut the cake? Why is that important? There's always someone willing to step up to the plate, if person A doesn't want to, then person B, or C, etc...

dweinus 3y ago

Only a mathematician could think that when people are arguing over a cake, the best solution involves giving everyone a knife (Stromquist moving-knives procedure)

quonn 3y ago

I can‘t help but think that when I cut one half just slightly bigger or better the chooser will pick the smaller version due to wanting to be polite.

deleted 3y ago
[deleted]

cheeseomlit 3y ago

If I get a piece with big globs of decorative frosting I'm just gonna scrape most of it off anyways. Way too sweet

Pathogen-David 3y ago

Up and Atom recently made a great video explaining this class of problems and some of the algorithms for solving it: https://youtu.be/fvM8ow6zNw4 https://youtu.be/fvM8ow6zNw4

pitdicker 3y ago

When it comes to economics it never ceases to amaze me that we build an entire system on the basic assumption that everyone acts primarily in their own self-interest, and that that system somewhat manages to function. Luckily when it comes to regular cake cutting there may be a host involved that just wants to give his guests something nice. And the guests hopefully just enjoy the cake instead of being overly sensitive about the fairness of the divisions.

shafyy 3y ago
What system are you referring to?
HEmanZ 3y ago
When the host gives their guest something nice, the host is acting on their interest to please their guest. Or their interest in being a friend. Or their interest in seeing their guest happy. By definition, the only interest you posses is your own, even if that interest is a benefit to someone else. Only straw-man arguments in economics use self interest to literally mean like “hedonic self interest” or layman’s self interest. Economics actually does the opposite, the “self interest” is basically “whatever people want”. What do people want? They want to maximize their utility! What is utility? Whatever people want!
crazygringo 3y ago
I hope it's clear that this isn't about actual cake cutting. But rather as a stand-in for any resource that people want to figure out a fair, equitable way to distribute. So you should read this as a guide to how different countries might be willing to fairly divide a contested piece of land, when different parts of the land have different qualities (e.g. suitability for farming, value in mining) and the different countries value those things differently (e.g. one is good at building mines, the other prefers to protect the environment). There are a lot of conflicts in the world over resources that need to be divvied up in some way, where everyone really is looking out for the self-interest of their state or nation or community.
- RetroTechie 3y ago

BizarroLand 3y ago

Reminds me of the book Triple Detente by Piers Anthony https://www.goodreads.com/book/show/263431.Triple_Detente https://www.goodreads.com/book/show/263431.Triple_Detente One of the core logical premises of the book is how three groups can handle an unsteady alliance where each group is primarily interested in saving their own people.

cpdean 3y ago

There's a really interesting boardgame based on the cake-cutting problem https://boardgamegeek.com/boardgame/173648/booty https://boardgamegeek.com/boardgame/173648/booty . You play many rounds of trying to fairly divvy up piles of loot. Different pieces combine in ways to increase their overall value, as well as each piece having a base level amount of value. As a result the actual act of dividing it fairly becomes complicated, and players will try to influence the outcome in order to maximize their score at the end of the game to win.

shagie 3y ago
I’d also recommended board game New York slice. https://boardgamegeek.com/boardgame/208895/new-york-slice https://boardgamegeek.com/boardgame/208895/new-york-slice and the “I cut you choose” mechanic section https://boardgamegeek.com/boardgamemechanic/2906/i-cut-you-choose https://boardgamegeek.com/boardgamemechanic/2906/i-cut-you-c...
- cpdean 3y ago
  I love that as a skinning of that genre haha
  - shagie 3y ago
    It has a "cut here" mechanic to it - you can't decide on the order of slices. > The Slicer starts by choosing a stack of 11 slices and its corresponding Special. Then the Slicer first flips the Special face up in the center of the table, reading it to the players, and then flips each slice face up in the center of the table. As each slice is flipped, it is placed directly next to the previous slice; the Slicer must continue to place slices in the same direction (clockwise or counterclockwise), with each slice being next to the last. The 11 slices will form a circle, with the last slice being next to the first slice. > The Slicer then divides the pizza into as many portions as there are players. For instance, if there are four players, the pizza would be divided into four portions. Each portion can have any number of slices, as long as it has at least one slice or the Special (the Special may be either combined with slices or placed by itself as its own portion). When dividing the pizza, the Slicer may not rearrange or change the order of the slices in any way. Note the 1/11th of a circle makes it so that it is never an easy even cut.

crazygringo 3y ago

Oh wow. I'd never heard of any of this, but it reminds me a lot of the different methods for voting [1]. After all, at heart there are a lot of parallels -- how do you reconcile different preferences and resources to split up a cake fairly, vs. how do you reconcile different preferences to split up the resource of power fairly, whether to elect a single person (e.g. a president) or a parliament? [1] https://en.wikipedia.org/wiki/Electoral_system https://en.wikipedia.org/wiki/Electoral_system

DominikPeters 3y ago
Indeed, there are many parallels, and in academia the same sort of people study both topics (e.g. in "computational social choice"), and they are often taught in the same lecture series (e.g. https://sites.google.com/view/optdemocracy23 https://sites.google.com/view/optdemocracy23, https://rohitvaish.in/Teaching/2023-Fall/ https://rohitvaish.in/Teaching/2023-Fall/). There is an important difference though: elections concern making one decision that affects everyone, whereas (fair) allocation involves deciding who gets what, and everyone is only affected by what they themselves get. It's the distinction between public and private goods.

yboris 3y ago

Algorithm for two people sharing any food: 1st person cuts, 2nd person chooses which of the pieces to take.

laweijfmvo 3y ago
For three people: https://www.youtube.com/watch?v=kaMKInkV7Vs https://www.youtube.com/watch?v=kaMKInkV7Vs

nntwozz 3y ago

The perfect solution to this problem is to put the cake in a blender and serve it in cups.

Tagbert 3y ago

I recall reading a science fiction story in one of the magazines like “Analog” several decades ago that used this concept as a major plot point. Two Planets were at risk of all out war and were evenly matched such that the results would be devastation for both. They negotiated a solution whereby each would proceed to “invade” the other’s planet and rule but each would observe how well the other ruled and could retaliate. This caused them to be scrupulously fair in their ruling. I don’t recall the name of the story or the author. This was likely in the late 60’s or early 70’s. I’m not sure why, if they could negotiate such a complex solution that they couldn’t just negotiate a secession of hostilities but the point of the story was to illustrate the cake principle.