“> 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”
按年被提到
20162016 · 2 次2026
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
适用于任意数量参与者的离散有界无嫉妒切蛋糕协议
Haris Aziz, Simon Mackenzie · 2016
解决离散有界无嫉妒切蛋糕协议存在性的公开问题
被提及 · 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
讨论串评论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…”
被提交为 story · 4 次
- Envy-Free Cake Cutting Protocol for Any Number of Agents ↗maverick_iceman · 2016-10-07 · 1 分
- A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents ↗apetresc · 2016-10-12 · 3 分
- A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents ↗tosh · 2017-10-03 · 20 分
- A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents (2016) ↗luu · 2024-01-19 · 24 分