[HN Gopher] Fair Cake-Cutting
___________________________________________________________________
Fair Cake-Cutting
Author : RetroTechie
Score : 53 points
Date : 2024-01-22 16:59 UTC (6 hours ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| dang wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| MichaelZuo wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| What system are you referring to?
| HEmanZ wrote:
| 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 wrote:
| 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.
| BizarroLand wrote:
| 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.
| cpdean wrote:
| 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.
| crazygringo wrote:
| 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
| yboris wrote:
| Algorithm for two people sharing any food:
|
| 1st person cuts, 2nd person chooses which of the pieces to take.
| laweijfmvo wrote:
| For three people: https://www.youtube.com/watch?v=kaMKInkV7Vs
| nntwozz wrote:
| The perfect solution to this problem is to put the cake in a
| blender and serve it in cups.
___________________________________________________________________
(page generated 2024-01-22 23:01 UTC)