Lance: Bill, there is a new result on cake cutting that was presented at STOC! Do you want to blog about it?
Bill: Do snakes have hips! Do chickens have lips!
Lance: No to the first one and I don't know to the second one.
Bill: Yes I'll blog about it! Whats the paper?
Lance: It's this paper by Aziz and Mackenzie.
Bill: Oh. That's not new. Five people emailed me about it a while back. But yes I will blog about it.
Cake Cutting: There are n people with different tastes in cake (some like chocolate and some... OH, who doesn't like chocolate? Okay, someone prefers kale which is on the cake.) They want a protocol that divides the cake in a way that is fair. What is fair? There are many definitions but I'll talk about two of them.
Proportional: Everyone gets 1/n of the cake (in their own opinion- I will omit saying this from now on).
Proportional sounds fair but consider the following scenario: Alice thinks she got 1/3 but she thinks Bob got 1/2 and Eve got 1/6. Alice will envy Bob.
Envy Free: Everyone thinks they have the largest piece (or are tied for it).
What is a protocol? It is a set of instructions and advice so that if (1) if the players all follow the advice then the end result is fair, and (2) if a player does not follow the advice then that player might get less than his fair share. Hence all players are motivated to follow the advice. We assume that everyone acts in their own self interest and that they are at a diamond cutters convention (perhaps co-located with STOC) so they really can cut cake very finely.
We will only consider discrete protocols. We won't define this formally.
Prior Results:
1) There is a protocol for Prop fairness for n people that uses O(n log n) cuts. See my notes
2) Jeff Edmonds and Kirk Pruhs showed a lower bound of Omega(n log n). See their paper.
3) There is a protocol for Envy Free fairness for 3 people due to Conway and Selfridge. This was in 1960. This protocol took 5 cuts. (It is in the doc I point to in next item)
4) In 1995 Brams and Taylor obtained a protocol for envy free fairness for n people. But there is a catch- there is no bound on the number of cuts. For all N there is a way to set four peoples tastes so that the protocol takes more than N cuts. See my notes.
All items to follow are for an envy free protocol for n people.
5) It was an open question to determine if there is a bounded protocol. Stromquest proved that there can be no bounded protocol if all of the players got a contiguous piece, though this was not the case in the Brams-Taylor protocol. See his paper
At the time I thought there would be no bounded protocol. I found a way to measure unbounded protocols using ordinals and wrote a paper on it: See my paper.
6) Aziz and MacKenzie showed there was a bounded protocol for 4 people. See their paper.
7) Aziz and MacKenzie, STOC 2016, showed there was, a protocol that takes at most TOW(n) cuts.
(thats roughly n to the n to the n ... to the n, n times). Hence a bounded protocol! See their paper.
What's next? Either improve the number of cuts or show it can't be done!
Bill accidentally deleted some comments. I've recovered a few of them.
ReplyDeleten^O(n) seems fairly HUGE as a bound. not Ackermann function huge, but it feels like if someone said “Hey, I’ve got a 3-SAT solver that runs in n^1,000,000 time; something to establish it can be bounded, but not in any useful way.
-> A 3-SAT solver that runs in n^1,000,000 time would be a pretty huge result.
The general result has a huge and impractical bound. The result for 4 agents still seems nice because it requires around 200 cuts whereas the previous algorithms had no bound on the cuts.
I believe I've found a problem with this result please let me know what you think: https://justincarcher.wordpress.com/2016/10/05/problems-cake-cutting-aziz-mackenzie-2016/
ReplyDelete