Weighted Envy-Freeness Revisited: Indivisible Resource and House Allocations

Abstract

Envy-freeness is a fundamental criterion in fair allocation. To address scenarios where agents have unequal entitlements, recent literature has focused on the concept of weighted envy-freeness (WEF). Under this concept, the valuation of each agent is divided by these weights when assessing fairness. While WEF promotes more fairness in some scenarios, it imposes strong constraints; experimental evidence suggests that weighted envy-freeness significantly reduces the likelihood of the existence of fair allocations. When the current concept of fairness is unattainable, it is standard to seek relaxed fairness concepts that are potentially more feasible to implement. In this paper, we revisit the weighted setting and propose a novel relaxation termed SumAvg-envy-freeness. This concept substantially improves the existence guarantees of fair allocations. This new concept can serve as a complement to the standard weighted envy-freeness. We systematically investigate the computational complexity of finding fair allocations under both the established and proposed weighted concepts across two classic problems: General Indivisible Resource Allocation and House Allocation. Our study provides a comprehensive characterization of various properties of weighted envy-freeness.

Keywords

Discrete Fair Division / Envy-Freeness / House Allocation / Parameterized Complexity

RIGHTS & PERMISSIONS

Higher Education Press 2026

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.