Pure Nash Equilibria in Online Fair Division
Pure Nash Equilibria in Online Fair Division
复制标题
在线公平划分中的纯纳什均衡
DOI：
10.24963/ijcai.2017/7
复制
发表时间：
2017
影响因子：
2.3
通讯作者：
T. Walsh
中科院分区：
文献类型：
--
作者：
M. Aleksandrov;T. Walsh
我们考虑一种公平的分配设置，其中物品一件一件到达，并通过两种现有机制分配给代理：LIKE 和 BALANCED LIKE。 LIKE 机制是策略证明的，而 BALANCED LIKE 机制则不然。虽然 LIKE 是防策略的，但我们证明它不是防群体策略的。事实上，我们的第一个主要结果是，没有任何在线机制能够抵御群体策略。然后我们关注这两种机制的纯纳什均衡。我们的第二个主要结果是，计算纯纳什均衡对于 LIKE 来说很容易处理，而对于 BALANCED LIKE 来说则很难处理。我们的第三个主要结果是，可能存在多个这样的配置文件，即使我们将注意力限制在特定属性（例如无嫉妒）的平衡上，对它们进行计数也很棘手。
We consider a fair division setting in which items arrive one by one and are allocated to agents via two existing mechanisms: LIKE and BALANCED LIKE. The LIKE mechanism is strategy-proof whereas the BALANCED LIKE mechanism is not. Whilst LIKE is strategy-proof, we show that it is not group strategy-proof. Indeed, our first main result is that no online mechanism is group strategyproof. We then focus on pure Nash equilibria of these two mechanisms. Our second main result is that computing a pure Nash equilibrium is tractable for LIKE and intractable for BALANCED LIKE. Our third main result is that there could be multiple such profiles and counting them is also intractable even when we restrict our attention to equilibria with a specific property (e.g. envy-freeness).