Weighted Envy-Freeness in Indivisible Item Allocation

In this paper, we introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1) -- strong (where the envy can be eliminated by removing an item from the envied agent's bundle) and weak (where the envy can be eliminated either by removing an item as in the strong version or by replicating an item from the envied agent's bundle in the envious agent's bundle). We prove that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists; however, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1 but always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the classic adjusted winner algorithm. We also explore the connections of WEF1 with approximations to the weighted versions of two other fairness concepts: proportionality and the maximin share guarantee.