A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

• Published in 2016
• Added on 2016-10-13

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from $n$ agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is $n^{n^{n^{n^{n^n}}}}$. We additionally show that even if we do not run our protocol to completion, it can find in at most $n^{n+1}$ queries a partial allocation of the cake that achieves proportionality (each agent gets at least $1/n$ of the value of the whole cake) and envy-freeness. Finally we show that an envy-free partial allocation can be computed in $n^{n+1}$ queries such that each agent gets a connected piece that gives the agent at least $1/(3n)$ of the value of the whole cake.

Links

• http://arxiv.org/abs/1604.03655v10
• http://arxiv.org/pdf/1604.03655v10

Other information

BibTeX entry

@article{ADiscreteandBoundedEnvyFreeCakeCuttingProtocolforAnyNumberofAgents,
	key = {ADiscreteandBoundedEnvyFreeCakeCuttingProtocolforAnyNumberofAgents},
	type = {article},
	title = {A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of  Agents},
	author = {Haris Aziz and Simon Mackenzie},
	abstract = {We consider the well-studied cake cutting problem in which the goal is to
find an envy-free allocation based on queries from {\$}n{\$} agents. The problem has
received attention in computer science, mathematics, and economics. It has been
a major open problem whether there exists a discrete and bounded envy-free
protocol. We resolve the problem by proposing a discrete and bounded envy-free
protocol for any number of agents. The maximum number of queries required by
the protocol is {\$}n^{\{}n^{\{}n^{\{}n^{\{}n^n{\}}{\}}{\}}{\}}{\$}. We additionally show that even if we do
not run our protocol to completion, it can find in at most {\$}n^{\{}n+1{\}}{\$} queries a
partial allocation of the cake that achieves proportionality (each agent gets
at least {\$}1/n{\$} of the value of the whole cake) and envy-freeness. Finally we
show that an envy-free partial allocation can be computed in {\$}n^{\{}n+1{\}}{\$} queries
such that each agent gets a connected piece that gives the agent at least
{\$}1/(3n){\$} of the value of the whole cake.},
	comment = {},
	date_added = {2016-10-13},
	date_published = {2016-10-09},
	urls = {http://arxiv.org/abs/1604.03655v10,http://arxiv.org/pdf/1604.03655v10},
	collections = {Attention-grabbing titles,Easily explained,Protocols and strategies,Food,Fun maths facts},
	url = {http://arxiv.org/abs/1604.03655v10 http://arxiv.org/pdf/1604.03655v10},
	urldate = {2016-10-13},
	archivePrefix = {arXiv},
	eprint = {1604.03655},
	primaryClass = {cs.DS},
	year = 2016
}