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]