资源论文Maximin-Aware Allocations of Indivisible Goods

Maximin-Aware Allocations of Indivisible Goods

2019-09-26 | |  83 |   43 |   0 0 0
Abstract We study envy-free allocations of indivisible goods to agents in settings where each agent is unaware of the goods allocated to other agents. In particular, we propose the maximin aware (MMA) fairness measure, which guarantees that every agent, given the bundle allocated to her, is aware that she does not envy at least one other agent, even if she does not know how the other goods are distributed among other agents. We also introduce two of its relaxations, and discuss their egalitarian guarantee and existence. Finally, we present a polynomial-time algorithm, which computes an allocation that approximately satisfies MMA or its relaxations. Interestingly, the returned allocation is also 12 -approximate EFX when all agents have subadditive valuations, which improves the algorithm in [Plaut and Roughgarden, 2018]

上一篇:How Hard Is the Manipulative Design of Scoring Systems?

下一篇:Multi-Agent Pathfinding with Continuous Time

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

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

  • Rating-Boosted La...

    The performance of a recommendation system reli...