2022/09/08 by Martin Hoefer, Hoefer, Martin, Marco Schmalhofer +3
Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #Ethics and Social Impacts of AI #FOS: Computer and information sciences #Game Theory and Voting Systems #Law, Economics, and Judicial Systems
paper · pdf · doi:10.48550/arxiv.2209.03908
openalex publication_date 2022/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fair division of indivisible goods is a central challenge in artificial intelligence. For many prominent fairness criteria including envy-freeness (EF) or proportionality (PROP), no allocations satisfying these criteria might exist. Two popular remedies to this problem are randomization or relaxation of fairness concepts. A timely research direction is to combine the advantages of both, commonly referred to as Best of Both Worlds (BoBW). We consider fair division with entitlements, which allows to adjust notions of fairness to heterogeneous priorities among agents. This is an important generalization to standard fair division models and is not well-understood in terms of BoBW results. Our main result is a lottery for additive valuations and different entitlements that is ex-ante weighted envy-free (WEF), as well as ex-post weighted proportional up to one good (WPROP1) and weighted transfer envy-free up to one good (WEF(1,1)). It can be computed in strongly polynomial time. We show that this result is tight - ex-ante WEF is incompatible with any stronger ex-post WEF relaxation. In addition, we extend BoBW results on group fairness to entitlements and explore generalizations of our results to instances with more expressive valuation functions.