arXiv · cs.AI · Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui · 11 小时前模型评分45
连续无嫉妒蛋糕切分的 PPAD 完全性被证明
PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations
导读
研究证明，在归一化有理分段常数加性估值下，计算完整的连续 ε-无嫉妒蛋糕分配是 PPAD 完全（PPAD-complete，Polynomial Parity Arguments on Directed graphs）的，即使 ε 以一元形式给出、密度仅取 λ 和 2λ 两值且断点不超过六个，精确连续无嫉妒分配同样如此。
分类置信度
低
- 缺少主分类。
来源级别：媒体与个人
事件类型：研究发布
证据摘录
- “We prove that computing a complete contiguous $\varepsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations.”
来源：arXiv · cs.AI · arxiv.org