How Mathematicians Cut Cake | Hacker News Reader

How Mathematicians Cut Cake

priceonomics.com

98 pointsjonbaer43 comments

This article describes how economists cut cake, not mathematicians. Mathematicians cut cake into a finite number of non-measurable pieces, rearrange those pieces using only rotation and translation, and end up with two cakes.

Here a vsauce recipee to explain how to do that ! https://www.youtube.com/watch?v=s86-Z-CbaHA

No. If economists were cutting the cake, there would be no cake on the table because someone would already have eaten it.

Curious, but why would one of the economists have eaten the cake?

https://financingefficiency.wordpress.com/2011/10/19/the-20-...

I thought this was going to be about slicing a rectangle out the center of the cake and pushing the two new halves together[0].

[0]: https://youtu.be/wBU9N35ZHIw?t=131

Me too. I was thinking of this Nature article from 1906: http://www.nature.com/nature/journal/v75/n1938/abs/075173c0....

One thing to note is that no allocation mechanism for more than 2 parties cannot satisfy all 3 of these criteria for general preferences

a) Efficient - guarantees an allocation where making at least one party better off without making anyone else worse off is possible

b) Balanced budget - guarantees all prices sum to a fixed number eg the total rent share

c) Incentive compatibility - it always a Nash equilibrium for every party to report their true preferences for each good.

There is only one allocation mechanism (Vickery-Clarke-Groves) that satisfies the 1st and 3rd criteria and this will generally not also satisfy the 2nd.

Reference:

https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%9...

Thus, Su and Spliddit's algorithms by definition must be vulnerable to strategic reporting.

Example: V=[v1,v2,v3] = preferences for rooms 1,2,3. total rent = 1000

VA = [1000,0,0] VB = [0,1000,0] VC = [0,0,1000]

Truth Telling Spliddit Allocation A->1,B->2,C->3 prices = [333,333,333]

If C reports [500,500,0] and A,B report truth

A->1,B->2,C->3 prices = [500,500,0]

TLDR - fair and efficient allocation mechanisms can never avoid vulnerability to gaming for some preferences.

Another interesting piece: equal pizza slices.

http://www.popsci.com/cut-better-slice-pizza-with-math

http://arxiv.org/pdf/1512.03794v1.pdf

While that solution is cool for preserving shape across all slices, it was clearly postulated by theoreticians.

An experimentalist would point out that pizza components have a radial dependence (Ie, crust on the outside), so it's not actually equal slicing in practice, and the traditional sector slices are really the most optimal ;-)

High stakes "I cut you chose" with nba ownership. I love this:

"""The situation could drag on until October of 2017 as Kaplan and Pera have a deal in which he has the option to make a bid for controlling interest in the team at a price of their choosing. At that point Pera would have two options: buy out Kaplan and Straus at that named price, or sell his shares to them based on the same valuation. """

http://basketball.realgm.com/wiretap/241181/sale-of-wolves-h...

I didn't think “I cut, you choose” is that fair.

Since often it's difficult to cut fairly, so the other person gets to pick a bigger piece always.

Add a step 0: flip coin for who cuts

Interestingly, I've used this technique for a long time with young kids at parties etc. that I have only just met. It is usually a great indicator of their personality traits, i.e. who has a compassionate, generous nature, or who is inherently greedy/selfish.

...or who is smart enough to realize there is a social metagame outside the obvious game of cake optimization.

The REALLY smart ones may have done a cost-benefit analysis and decided that the payoff from the metagame - an increment in your opinion of them - is not worth as much utility as the incrementally bigger cake.

Alternately the greedy ones have concluded your opinion of them is worth less than the extra cake :).

That's the point. It provides an incentive to cut as evenly as possible.

Unless you know there will be a punishment for doing so later.

An alternative method with kids, is to have the youngest going under the table and say who is to receive the next slice of cake. Used that every year for the epiphany (Kings cake).

If you know the preferences of the other person, its often an advantage for a non-regular cake because you can offer them a small amount of stuff they value more highly than you

Fair voting is almost exactly analogous (I think it is even the same math).

I had a fantastic math teacher in high school who showed how it is fairly difficult to make any voting scheme fair.

s/fairly difficult/impossible/

https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theore...

I was going to say impossible as the teacher even said that but I think for small numbers it is possible IIRC.

There was some joke I think by Kenneth that the only fair voted government is a dictatorship.

Joke? Non-dictatorship is one of the mutually impossible criteria of Arrow's impossibility theorem. "The only fair voted government is a dictatorship" is an accurate statement of the theorem, as far as it goes.

Yes, but there's some equivocation there. The meaning of 'dictator' isn't quite what you might think it is.

The meaning of "dictator", as used in Arrow's theorem, is that the outcome of an election is exactly what the dictator says it should be. More technically, the election outcome considers only the dictator's vote, and is independent of the votes of everyone who is not the dictator.

I don't see how that differs at all from the colloquial understanding. It's a perfect reflection of the principle of One Man, One Vote, as described for Ankh-Morpork ("The Patrician was the Man; he had the Vote").

Bu then why does the theorem only hold with more than two candidates?

Arrow's only proves you can't meet a certain set of criteria. It doesn't prove that set of voting criteria is necessary for a fair vote outcome. IIAC is particularly problematic.

Surprised there's no mention of Nash. It's mentioned often in their book and a popular culture reference many would recognize.

https://books.google.com/books?id=cLUA-sRhJ5QC&q=nash#v=snip...

> In an overview of fair division applications published in Nautilus, science writer Erica Klarreich offers one such example. In the event of the contentious breakup of a marriage or relationship, the algorithm, which Ring and Brams call “Fair Buy-Sell” requires each partner to simultaneously propose a price.

> “If John proposes $110,000 and Jane proposes $100,000 then John, the higher bidder, will buy out Jane for $105,000,” explains Klarreich. “Each participant ends up with something—either money or the business—at a price that is better than his or her offer.”

I'm curious how that would work in a marriage, given that the couple's assets are generally commingled (how can I spend our assets to pay you for our assets?).

I think that'd work better when the husband & wife each have their own personal assets, and only the common property is held in common.

I think that's a much more generally advisable choice, no matter how unromantic it may seem to the naïve. (It is unromantic! It has that going against it. But banking on romance to last, while heartbreakingly understandable, is often unwise - and heartbreaking.)

I think this is how it works.

1) A judge awards the estate be split in a given proportion

2) Illiquid assets are priced and allocated using the mechanism

3) The judge's split-proportion is achieved using the liquid assets' market prices

If there are many assets, then it's just to decide on value when splitting them; if a large item (e.g. house) is the majority of everything, then one gets the asset at the decided value; and mortgages it to pay half of that value (minus the value of other smaller assets) in cash.

Along these same lines, Five Thirty Eight had a neat Riddler last week about how to choose the heights of a 3 layer cake to fit under a glass cone:

http://fivethirtyeight.com/features/can-you-bake-the-optimal...

Excellent article

Fair does not mean equal and equal does not mean fair.

I wonder how mathematicians eat corn on the cob? Across left to right? In circles? I was told by future in-laws that I was "confident" Because I ate left to right like a typewriter. They eat in circles. Ever since then I eat randomly. Bite here.. Row right to ledt there. .....

Plover has an article about his unnscientific survey of about 6 mathematicians, eating corn by the style of tbeir subfield of math.

Splitting a sandwich and not feeling deceived

https://math.stackexchange.com/questions/637728/splitting-a-...

"Suppose I cut a piece. It's... crumbly, but good..."

I always cut more pieces than eaters and unevenly, because some people want just one small piece, some want a big piece, and some will be happy to have another piece later.

How do you cut a cake in a way that gives me a piece that is only large enough to satisfy the host's expectation that I will like the cake they made?

How Mathematicians eat a cake? Do they calculate the optimal angle of fork, optimal mouth opening? Im more interested in to eat than to cut.

Some design patterns for founder equity allocation based on these principles would be useful.

See, that headline would have been awesome if there was 'pie' somewhere in it :)

Reply on news.ycombinator.com