跳到正文
研踪PaperTrail
← 研踪 PaperTrail
正在查看已观测的 v1。查看最新 v2 →

arXiv:2611.11424 · v1

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

Alireza FarhadiMohammadtaghi Hajiaghayi
cs.GT
首次提交 2026-11-08 22:36
版本更新 2026-11-08 22:36
雷达观测 2026-11-10 12:16
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 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.

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 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.

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