Maximin-Aware Allocations of Indivisible Goods

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