Given a set of $p$ players we consider problems concerning envy-free
allocation of collections of $k$ pieces from a given set of goods or chores. We
show that if $p\le n$ and each player can choose $k$ pieces out of $n$ pieces
of a cake, then there exist a division of the cake and an allocation of the
pieces where at least $\frac{p}{2(k^2-k+1)}$ players get their desired $k$
pieces each. We further show that if $p\le k(n-1)+1$ and each player can choose
$k$ pieces, one from each of $k$ cakes that are divided into $n$ pieces each,
then there exist a division of the cakes and allocation of the pieces where at
least $\frac{p}{2k(k-1)}$ players get their desired $k$ pieces. Finally we
prove that if $p\ge k(n-1)+1$ and each player can choose one shift in each of
$k$ days that are partitioned into $n$ shifts each, then, given that the
salaries of the players are fixed, there exist $n(1+\ln k)$ players covering
all the shifts, and moreover, if $k=2$ then $n$ players suffice. Our proofs
combine topological methods and theorems of F\"uredi, Lov\'asz and Gallai from
hypergraph theory.

本文将枚举的方式应用于一些常见的分配问题，并使用拓扑学方法和 Furedi，Lovasz 和 Gallai 的超图定理进行了证明。

多件公平分割

Fair division with multiple pieces

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