按年被提到
20162016 · 2 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:1604.03655 · cs.DS

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

适用于任意数量参与者的离散有界无嫉妒切蛋糕协议
Haris Aziz, Simon Mackenzie · 2016

解决离散有界无嫉妒切蛋糕协议存在性的公开问题

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2016-10-07 · 最近 2024-01-19
4不同的人
3活跃月份
4讨论串
145被引(OpenAlex)

解决了“是否存在离散且有界的无嫉妒切蛋糕协议”这一重要开放问题,给出适用于任意 n 个参与者的协议,其最多查询次数为 n^{n^{n^{n^{n^n}}}}。还证明即使不运行到底,也能在至多 n^3(n^2)^n 次查询内得到同时满足比例性和无嫉妒的部分分配,以及每人拿到一块连续蛋糕、价值至少 1/(3n) 的无嫉妒部分分配。

HN 为什么提它

输入里没有可用的评论摘录,只知道有 4 个人在 3 个月里提到过它,具体讨论点无法判断。

方法难度 4 / 5约 45 分钟经得起时间
读之前最好知道
1切蛋糕问题与公平分配
2无嫉妒(envy-freeness)与比例性
3算法博弈论基础
4查询复杂度

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)
讨论串评论nomilk · 2024-01

“> The maximum number of queries required by the protocol is n^n^n^n^n^n I'm impressed that rendered correctly, never seen that before. Got a minimal version working: code: https://pastebin.com/CqCzH8H7 what it looks like: https://imgur.com/a/v2PU1mH”

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents (2016)原评论 ↗
讨论串评论RcouF1uZ4gsC · 2024-01

“> The maximum number of queries required by the protocol is n^n^n^n^n^n With 2 people taking 1 second per query you end up with 2^2^2^2^2^2 which is 2^(2^65536) seconds. I guess if not only the cake has decomposed and the people involved have died, but the universe itself has lost all thermodynamic free energy, I guess technically we are in an envy free…”

A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents (2016)原评论 ↗
被提交为 story · 4 次