Fair Cake-Cutting | Hacker News Reader

Fair Cake-Cutting

en.wikipedia.org

77 pointsRetroTechie27 comments

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.

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...

I love that as a skinning of that genre haha

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.

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?

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.

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.

> 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...

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)

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)

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

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.

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

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

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.

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.

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.

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.

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!

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.

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!

What system are you referring to?

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.

Algorithm for two people sharing any food:

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

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

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.

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

Reply on news.ycombinator.com