论文标题
无嫉妒的蛋糕切割：高概率的多项式查询数量
Envy-free cake cutting: A polynomial number of queries with high probability
论文作者
论文摘要
在本文中，我们提出了一个概率框架，以研究n个玩家之间的可分裂商品的公平分裂，例如蛋糕。我们的框架遵循的想法比在不可分割的商品的公平划分研究中使用的“完全独立模型”相同。我们表明，在此框架中，存在一种满足以下概率估计值的无嫉妒的分区算法：$$ \ mathbb {p} \ big（c（μ_1，\ ldots，μ_n）\ geq n^{7+b} \mathcal{O}\Big(n^{-\frac{b-1}{3}+1+o(1)}\Big),$$where $μ_1,\ldots, μ_n$ correspond to the preferences of the $n$ players,$C(μ_1, \ldots,μ_n)$ is the number of queries used by the algorithm and $ b> 4 $。 In particular, this gives$$\lim_{n \rightarrow + \infty}\mathbb{P}\big( C(μ_1, \ldots,μ_n) \geq n^{12}\big) = 0.$$ It must be noticed that nowadays few things are known about the complexity of envy-free division algorithms.确实，Procaccia在$ω（n^2）$中给出了下限，而Aziz和Mackenzie在$ n^{n^{n^{n^{n^{n^{n^{n}}}}}}} $中给出了上限。根据我们的估计，意味着我们具有$ c（μ_1，\ ldots，μ_n）<n^{12} $具有很高的概率，这给出了对嫉妒的无蛋糕切割算法的复杂性的新见解。我们的结果是根据对Webb算法的研究和Tao和Vu定理的研究，涉及随机矩阵的最小值。
In this article we propose a probabilistic framework in order to study the fair division of a divisible good, e.g., a cake, between n players. Our framework follows the same idea than the ''Full independence model'' used in the study of fair division of indivisible goods. We show that, in this framework, there exists an envy-free division algorithm satisfying the following probability estimate:$$\mathbb{P}\big( C(μ_1, \ldots,μ_n) \geq n^{7+b}\big) = \mathcal{O}\Big(n^{-\frac{b-1}{3}+1+o(1)}\Big),$$where $μ_1,\ldots, μ_n$ correspond to the preferences of the $n$ players,$C(μ_1, \ldots,μ_n)$ is the number of queries used by the algorithm and $b>4$. In particular, this gives$$\lim_{n \rightarrow + \infty}\mathbb{P}\big( C(μ_1, \ldots,μ_n) \geq n^{12}\big) = 0.$$ It must be noticed that nowadays few things are known about the complexity of envy-free division algorithms. Indeed, Procaccia has given a lower bound in $Ω(n^2)$ and Aziz and Mackenzie have given an upper bound in $n^{n^{n^{n^{n^{n}}}}}$. As our estimate means that we have $C(μ_1, \ldots, μ_n)<n^{12}$ with a high probability, this gives a new insight on the complexity of envy-free cake cutting algorithms. Our result follows from a study of Webb's algorithm and a theorem of Tao and Vu about the smallest singular value of a random matrix.
