arXiv cs.AI· Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenh\"auser·· 12 小时前AI 评分18
将不可分割物品分配给策略性智能体：纯 Nash 均衡与公平性
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
AI 导读
研究在无货币转移、智能体可策略性虚报估值的设定下，是否存在对每个实例都有纯 Nash 均衡且均衡分配满足公平性的机制。
正文 · AI 翻译
摘要：我们考虑将一组不可分割的物品公平地分配给一组具有可加估值函数的策略性代理人的问题。我们假设不存在货币转移，因此，在我们的设定中，机制是一种算法，其输入是代理人报告的值（而非真实值）。我们的主要目标是探索是否存在这样的机制：对每个实例都具有纯纳什均衡，同时为对应于这些均衡的分配提供公平性保证。我们关注无嫉妒性的两种松弛，即至多一件物品无嫉妒（EF1）和至多任意一件物品无嫉妒（EFX），并对上述问题给出了肯定的回答。特别地，我们研究了两种已知在非策略性设定下能产生此类分配的算法：轮询（Round-Robin，对任意数量的代理人都能产生 EF1 分配）以及 Plaut 和 Roughgarden [SIAM Journal of Discrete Mathematics, 2020] 的切分选择算法（对两个代理人能产生 EFX 分配）。对于轮询，我们证明其所有纯纳什均衡所诱导的分配相对于底层真实值都是 EF1；而对于 Plaut 和 Roughgarden 的算法，我们证明相应的分配不仅是 EFX，还满足最大最小份额公平性，而这一点在该算法的非策略性设定下并不成立！此外，我们证明后一结果的一个较弱版本对任何两个代理人的机制都成立，只要该机制始终具有纯纳什均衡且所有这些均衡都诱导 EFX 分配。
| 评论： | 关于轮询的每个纯纳什均衡都是 EF1 的论断（此处为定理 3.3；会议版中的定理 3 和期刊版中的定理 4）是不正确的；缺陷在于引理 3.5 的证明（不等式 (2)）。反例和修正后的保证见 arXiv:2610.23686。其余结果不受影响 |
| 主题： | 计算机科学与博弈论（cs.GT）；人工智能（cs.AI）；离散数学（cs.DM） |
| 引用为： | arXiv:2109.08644 [cs.GT] |
| （或本版本的 arXiv:2109.08644v3 [cs.GT]） | |
| https://doi.org/10.48550/arXiv.2109.08644 由 DataCite 颁发的 arXiv DOI |
|
| 相关 DOI： | https://doi.org/10.1287/moor.2022.0058
链接到相关资源的 DOI |
提交历史
来自：Georgios Amanatidis [查看电子邮件]
[v1]
2021 年 9 月 17 日星期五 16:57:20 UTC（37 KB）
[v2]
2023 年 12 月 11 日星期一 16:33:10 UTC（99 KB）
[v3]
2026 年 10 月 21 日星期三 10:44:03 UTC（95 KB）
来源：arXiv cs.AI · arxiv.org