On the Incompatibility of Weighted PROPX and Pareto Optimality for Indivisible Chores
2026-08-17 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explore how to fairly divide chores (unpleasant tasks) among people with different preferences. They focus on a fairness rule called proportionality up to any item (PROPX), which means everyone feels their share is fair if any one chore is removed from their set. The authors show that for two or more people, achieving both this fairness and efficiency (Pareto optimality) at the same time is often impossible when there are more chores than people. They provide specific examples proving this incompatibility and also identify cases where fairness and efficiency can coexist. Their findings contrast with earlier work on a related fairness concept called envy-freeness up to one item (EF1).
proportionalityPROPXPareto optimalityadditive preferencesindivisible choresweighted fairnessenvy-freenessEF1fair divisionimpossibility result
Authors
Haris Aziz, Bo Li
Abstract
Proportionality (PROP) is one of the simplest fairness criteria for allocating items among agents with additive preferences. With indivisible chores, however, PROP is not always satisfiable. We study proportionality up to any item (PROPX), which requires every agent to satisfy proportionality after any chore is removed from her bundle. Under strictly positive costs, we settle the weighted compatibility question negatively: weighted PROPX and Pareto optimality are incompatible already for two agents and four chores. Moreover, for every $n\geq3$, we give an $n$-agent, $(n+1)$-chore counterexample whose shares can be arbitrarily close to equal. These counterexamples are item-minimal: under strictly positive costs, weighted PROPX and Pareto optimality are always compatible when the number of chores is at most the number of agents, and they are compatible for two agents with at most three chores. Our impossibility result contrasts with the compatibility theorem of Mahara (2026) for weighted envy-freeness up to one item (EF1) and Pareto optimality .