[PDF][PDF] Pure Nash Equilibria in Online Fair Division.

M Aleksandrov, T Walsh - IJCAI, 2017 - ijcai.org
IJCAI, 2017ijcai.org
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 …
Abstract
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 (eg envy-freeness).
ijcai.org
以上显示的是最相近的搜索结果。 查看全部搜索结果