Fair Cake-Cutting

https://en.wikipedia.org/wiki/Fair_cake-cutting

by RetroTechie • 2 years ago

77 27 2 years ago

en.wikipedia.org

dang• 2 years 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 - Jan 2024 (9 comments)

Also:

New Algorithm Solves Cake-Cutting Problem (2016) - 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 - 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 - Oct 2017 (1 comment)

New algorithm that can fairly divide a cake among any number of people - 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 - Oct 2016 (1 comment)

How Mathematicians Cut Cake - 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 - June 2009 (6 comments)

13415• 2 years 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• 2 years 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?

videogreg93• 2 years 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• 2 years 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• 2 years 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• 2 years 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• 2 years 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.

cheeseomlit• 2 years 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• 2 years 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

pitdicker• 2 years 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• 2 years ago

What system are you referring to?

HEmanZ• 2 years 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!

crazygringo2• 2 years 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• 2 years ago

Sadly that's not how it works.

There's maaany possible justificatons for contesting previously non-contested resources. Historic or otherwise, justified or not. And those reasons change over time, change of leadership, economic or climate conditions, or even technological progress (resource previously considered uninteresting suddenly becomes valuable - and thus, often contested). Fairly (?) dividing whatever is contested, doesn't solve that problem.

One fix is to just accept that changing circumstances enhance or degrade whatever piece of the pie you got.

Or to keep 'moving the knives' continously. (Re-)distribution possibly enforced by military power. Oh wait... that is how it works!

oreally• 2 years ago

The system functions? Maybe in the current times, but not long term as we exhaust the earth's resources and jobs get taken over by technology to the point it becomes meaningless.

BizarroLand• 2 years ago

Reminds me of the book Triple Detente by Piers Anthony

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.

cpdean2• 2 years ago

There's a really interesting boardgame based on the cake-cutting problem 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.

shagie2• 2 years ago

I’d also recommended board game 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-c...

cpdean2• 2 years ago

I love that as a skinning of that genre haha

crazygringo2• 2 years 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

DominikPeters• 2 years 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://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• 2 years ago

Algorithm for two people sharing any food:

1st person cuts, 2nd person chooses which of the pieces to take.

laweijfmvo• 2 years ago

For three people: https://www.youtube.com/watch?v=kaMKInkV7Vs

nntwozz• 2 years ago

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

Tagbert• 2 years 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.

Fair Cake-Cutting

Related Stories