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^3{(n^2)}^n$
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 at most
$n^3{(n^2)}^n$ queries such that each agent gets a connected piece that gives
the agent at least $1/(3n)$ of the value of the whole cake.

我们提出了一种离散和有界的无嫉妒协议，可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议，我们也可以在至多 $n^3 {(n^2)}^n$ 个查询中找到一个部分分配，以实现比例分配和无嫉妒性。最后，我们还表明，可以在最多 $n^3 {(n^2)}^n$ 个查询中计算一个无嫉妒的部分分配，使得每个代理人都获得至少糕点总价值的 $1 / (3n)$ 的连接块。

一种离散且有界的无嫉妒蛋糕切分协议，适用于任意数量的代理

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

We consider the well-studied cake cutting problem in which the goal is to
identify a fair allocation based on a minimal number of queries from the
agents. The problem has attracted considerable attention within various
branches of computer science, mathematics, and economics. Although, the elegant
Selfridge-Conway envy-free protocol for three agents has been known since 1960,
it has been a major open problem for the last fifty years to obtain a bounded
envy-free protocol for more than three agents. We propose a discrete and
bounded envy-free protocol for four agents.

研究了蛋糕切分问题，提出了离散且有界的不嫉妒协议，以实现基于最少询问数的公平分配问题。