In the classical cake cutting problem, a resource must be divided among
agents with different utilities so that each agent believes they have received
a fair share of the resource relative to the other agents. We introduce a
variant of the problem in which we model an underlying social network on the
agents with a graph, and agents only evaluate their shares relative to their
neighbors' in the network. This formulation captures many situations in which
it is unrealistic to assume a global view, and also exposes interesting
phenomena in the original problem.
Specifically, we say an allocation is locally envy-free if no agent envies a
neighbor's allocation and locally proportional if each agent values her own
allocation as much as the average value of her neighbor's allocations, with the
former implying the latter. While global envy-freeness implies local
envy-freeness, global proportionality does not imply local proportionality, or
vice versa. A general result is that for any two distinct graphs on the same
set of nodes and an allocation, there exists a set of valuation functions such
that the allocation is locally proportional on one but not the other.
We fully characterize the set of graphs for which an oblivious single-cutter
protocol-- a protocol that uses a single agent to cut the cake into pieces
--admits a bounded protocol with $O(n^2)$ query complexity for locally
envy-free allocations in the Robertson-Webb model. We also consider the price
of envy-freeness, which compares the total utility of an optimal allocation to
the best utility of an allocation that is envy-free. We show that a lower bound
of $\Omega(\sqrt{n})$ on the price of envy-freeness for global allocations in
fact holds for local envy-freeness in any connected undirected graph. Thus,
sparse graphs surprisingly do not provide more flexibility with respect to the
quality of envy-free allocations.

研究分配问题，引入社交网络模型，通过局部比例和局部嫉妒性的概念，使用单人切割模型确定图形结构和嫉妒性代价下的最大效用分配。

公平分配

Fair Division via Social Comparison

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)$ 的连接块。