Fair Division Under Boolean Valuations: Beyond Normalization
Nisarg Shah, Paritosh Verma
原文摘要
We study fair division of indivisible items when agents have arbitrary two-level preferences: the value of each agent for any set of items is Boolean, which need not be monotone or additive. Notably, we do not impose the standard assumption of normalization, i.e., different agents may value the empty set at different Boolean levels. Since the preferences are nonmonotone, envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) each admit several variants, depending on which items are tested for removal and whether they are removed from the envious agent's bundle or the envied agent's bundle. This paper investigates the existence of these variants of EF1 and EFX, on their own and together with economic efficiency, incentive compatibility, feasibility constraints, and lottery-based randomization. Our paper presents a wide range of positive and negative results that collectively highlight an interesting phenomenon: the landscape of achievable guarantees depends crucially on the number of normalized agents, who value the empty bundle at the lower Boolean level.
cs.GT