跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.11424 · v2

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

无嫉妒分配的查询复杂度：蛋糕、杂务与混合资源

Alireza FarhadiMohammadtaghi Hajiaghayi
cs.GT
首次提交 2026-11-08 22:36
版本更新 2026-11-11 00:43
雷达观测 2026-11-11 13:07
arXiv ↗PDF ↗

摘要

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using 2nlog⁡2n+O(n)2^{n\log_2 n+O(n)} queries and cuts. For both cake and chores, a Las Vegas protocol uses O(n12log⁡(2n))O(n^{12}\log(2n)) expected queries and O(n11log⁡(2n))O(n^{11}\log(2n)) expected cuts. Conversely, every exact protocol with fixed positive success probability requires Ω(n2)Ω(n^2) expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

研究蛋糕、杂务及正负混合资源在无嫉妒分配下的查询复杂度，给出上界协议与下界不可能性结果。

正在读取账号与研究记录…

版本差异

仅对比实际观测的元数据，不代表 PDF 正文或实验变化。版本可能不连续；带删除线为移除，下划线为新增。

摘要变化

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using $2^{3nn\log_2 n+O(n)}$ queries and cuts. For both cake and chores, a Las Vegas protocol uses $O(n^{2112}\log^2(2n))$ expected queries and $O(n^{2011}\log^2(2n))$ expected cuts. Conversely, every exact protocol with fixed positive success probability requires $Ω(n^2)$ expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

观测到的版本

相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-11 00:43 · 最新观测版本

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using 2nlog⁡2n+O(n)2^{n\log_2 n+O(n)} queries and cuts. For both cake and chores, a Las Vegas protocol uses O(n12log⁡(2n))O(n^{12}\log(2n)) expected queries and O(n11log⁡(2n))O(n^{11}\log(2n)) expected cuts. Conversely, every exact protocol with fixed positive success probability requires Ω(n2)Ω(n^2) expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

查看此版本解读 →查看此版本原文 ↗
v1 · 2026-11-08 22:36

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using 23nlog⁡2n+O(n)2^{3n\log_2 n+O(n)} queries and cuts. For both cake and chores, a Las Vegas protocol uses O(n21log⁡2(2n))O(n^{21}\log^2(2n)) expected queries and O(n20log⁡2(2n))O(n^{20}\log^2(2n)) expected cuts. Conversely, every exact protocol with fixed positive success probability requires Ω(n2)Ω(n^2) expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

查看此版本解读 →查看此版本原文 ↗