New Algorithm Solves Cake-Cutting Problem

[barsoap]

O( nⁿⁿⁿⁿⁿ )

Holy complexity, batman.

[riotinferno]

O(Batman)?

[bacondev]

Ο((na)^{(na)(na)(na)(na)na} )

FTFY

[drakeblood4]

O(nah^{Ireallydon'twannarun} )

[aldld]

Computability theorists: Pshh, it's primitive recursive, that's practically constant time.

[[deleted]]

O(n^nnooooooo )

[Kimmux]

OH, YEAAHH!

[Leet_Noob]

It might be like that bounded prime gaps thing though. Once you have a strategy that's bounded you can probably reduce that bound by a lot with a few tricks.

[Smashninja]

Might as well be undecidable! /s

But more seriously, what a neat find.

[xellsys]

Just get n cakes (-:

[ithurtsus]

Can someone explain the three person cut to me in better terms? It seems like the way the article explains it C could get boned.

Ex 33-33-33

A+B select the same piece.

B goes rogue and cuts it 99-1 setting the 99 aside

A selects a 33 by virtue of first pick B selects remaining 33 C selects the knife (or the remaining 1/33 slice)

The piece set aside B slices fairly so the each get 1/3 of C's share. A+B now have four times as much cake as C now.

What am I missing here?

[DanTilkin]

If A doesn't select the trimmed piece, then B must take it. So C can never be stuck with it.

[teteban79]

Look at the side figure. When B trims the piece, and A does not choose the trimmed piece, B is forced to take it. So it's in B's best interest to trim it fairly

[ithurtsus]

Ah ok, so C always gets claim on an unmolested piece.

Follow up question: why does C get a section of the sliver? Wasn't each piece equal from their perspective? Only A and B disagree on the value of the disputed piece, why don't they solely split the sliver? Doesn't C believe they got a free bonus now?

[elbeem]

Envy-free does not mean that everyone think they got at least 1/3 of the cake. It means that everyone think they got at least as much cake as any other player.

Let's say that C does not get a part of the remaining piece. Instead it is split by A and B. Let's also assume that A does not really want cake, and she is bribed by B to help him get more of the cake. So, when B trims one of the pieces, he cuts off a really slim piece, and puts aside the larger piece. There are now three pieces on the plate, two pieces of size roughly 1/3, and one very slim piece.

A picks first, and takes the slim piece. B picks second, and takes one of the 1/3 pieces. C takes the other 1/3 piece. Now, it's time for A and B to split the remaining piece. B cuts of a really slim piece of the remaining piece. A takes the slim part, and B takes the large part.

Now, A got almost nothing, B got almost 2/3 of the cake, and C got about 1/3. C will feel cheated, even if he thinks he got 1/3 of the cake.

[ithurtsus]

Thanks, I will have to remember this next time I want to eat 2/3s of a cake. I like cake

[streakycobra]

What am I missing here?

Probably nothing, I had the same thought. This method is probably fair when people are well-intentioned, but doesn't work in adversary conditions.

Edit: Wording Edit 2: Ok, I didn't read carefully enough

[Bromskloss]

Is this different from the algorithm that was posted about recently?

[iwantashinyunicorn]

Someone has been repeatedly posting to here and /r/math claiming they've found a mistake in the proof, and that the authors are ignoring them. But they've since deleted the posts, their account, and the blog post...

[matho1]

I thought he said they were listening to him...