pith. sign in

arxiv: 1507.08497 · v2 · pith:EJZ7QF7Vnew · submitted 2015-07-28 · 🧮 math.LO · cs.GT

Which Unbounded Protocol for Envy Free Cake Cutting is Better?

classification 🧮 math.LO cs.GT
keywords cutsenvyfreenumberprotocoltakescakepeoples
0
0 comments X
read the original abstract

A division of a cake by n people is envy free if everyone thinks they got the biggest pieces. Note that peoples tastes can differ. There is a discrete protocol for envy free division for n=3 which takes at most 5 cuts. For n=4 and beyond there is a protocol but the number of cuts it takes is unbounded. In particular the number of cuts depends on peoples tastes. Given any number N peoples tastes can be set so that the algorithm takes over N cuts. There are three such algorithms known. Which is better? We have devised a way to measure the number of cuts even though it is unbounded. We use ordinals; therefore, a statement like "this protocol takes at most 2omega steps" makes sense. We analyse all three discrete algorithms for envy free cake cutting with this measure.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.