跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1208新增论文
+950其中 AI 相关
+153已有论文修订
+59新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-18 14:10各信源进度 →

统计口径与数据新鲜度

统计 2026-11-17 14:41 — 2026-11-18 14:41(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 14:10库内论文最新更新时间:2026-11-18 08:00

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

26,057 已收录论文21,704 AI 相关7,828 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.20890

Nearly Settling the Complexity of Connected $\varepsilon$-Envy-Free Cake Cutting

Simon Mackenzie, Mashbat Suzuki

原文摘要

Envy-free cake cutting has been one of the central problems in fair division. In cake cutting, agents' preferences over the cake are accessed through Robertson--Webb (RW) queries. For three or more agents, no algorithm that makes finitely many RW queries can always find a contiguous, exactly envy-free allocation. For contiguous $\varepsilon$-envy-free allocations, however, Hollender and Rubinstein~(JACM, 2025) showed that $\poly(\log(1/\varepsilon))$ RW queries suffice for four agents, leaving open whether such a bound is possible for five or more agents. In this paper, we establish a striking change in query complexity: $\poly(\log(1/\varepsilon))$ RW queries suffice for up to five agents, whereas $(1/\varepsilon)^{Ω(1)}$ queries are necessary for seven or more agents, even when valuations are additive. Thus, we resolve the five-agent case and, more broadly, determine whether polylogarithmic query complexity is possible for every number of agents except six. We also explore the computational complexity of finding contiguous $\varepsilon$-envy-free allocations. When monotone Lipschitz valuations are given by polynomial-time evaluation procedures (e.g., arithmetic circuits and efficiently computable Turing machines), we show that an $\varepsilon$-envy-free division can be computed in polynomial time for five agents. In contrast, even for additive valuations, finding an $\varepsilon$-envy-free division is UEOPL-hard for every fixed number of agents $n\ge7$ and PPAD-complete for every fixed $n\ge13$.

cs.GT · cs.CC

版本更新 · v4arXiv:2604.18216

EFX Need Not Exist

Hannaneh Akrami, Simon Mackenzie, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, Mashbat Suzuki, Christoph Weidenbach

原文摘要

The existence of envy-free up to any good (EFX) allocations has long been a central open problem in discrete fair division. We resolve it in the negative by constructing a counterexample with three agents and eight goods. The instance is invariant under every simultaneous permutation of the agents and their associated good types, and this symmetry yields a short, self-contained proof of nonexistence. The counterexample can be realized with weighted-coverage, and hence submodular, valuations, and it extends to $n$ agents and $m$ goods for all $n\ge3$ and $m\ge n+5$. For three agents, eight goods is the minimum: every instance with three agents and at most seven goods admits an EFX allocation under arbitrary monotone valuations. The proof relies on a new analysis, valid for any number of goods, of when the invariant-based technique of [AACGMM25] produces an EFX allocation. This analysis strictly extends the class of MMS-feasible valuations. We also give explicit bounds for approximate EFX. For subadditive valuations, $α$-EFX allocations need not exist for any $α>2^{-1/6}\approx0.891$, and for submodular valuations for any $α>0.958$. On the positive side, if two of three agents have arbitrary monotone valuations and the third has a subadditive valuation, there is always an allocation that is EFX for the first two and $2^{-1/3}$-EFX ($\approx0.794$) for the third. A first version of the counterexample and of the seven-goods result was obtained using SAT/SMT solving, and the insights it provided guided our classical, pen-and-paper proofs. We also describe the encoding, which we believe is a valuable tool in its own right: to our knowledge, this is the first use of SAT/SMT solving for EFX.

cs.GT · cs.DS