资源论文Pure Nash Equilibria in Online Fair Division

Pure Nash Equilibria in Online Fair Division

2019-10-29 | |  56 |   44 |   0
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 (e.g. envy-freeness).

上一篇:Probabilistic Inference in Hybrid Domains

下一篇:Safe Inductions: An Algebraic Study

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...