PMMS fairness allocations may not exist but chores allow good approximations
Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores
Computer Science and Game Theory
Summary
The paper looks at how to fairly divide items, whether good or bad (called chores), among people who value each item differently. The authors show that sometimes it’s impossible to split items exactly fairly according to a known fairness concept called pairwise maximin share (PMMS). They find that deciding if a perfectly fair division exists is a hard problem computer-wise. However, when dividing chores, they prove that you can always find a division that is close enough to fair, within a factor of about 1.33. This helps understand the limits and possibilities of fair division when items aren’t all positive.
pairwise maximin share (PMMS)indivisible itemsadditive preferencesfair divisionchoresgoodsNP-hardapproximation guaranteepolynomial-time reduction
Authors
Xiaohui Bei, Zehan Lin, Shengxin Liu, Rong Luan, Biaoshuai Tao
Abstract
We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existence of a PMMS allocation. Together with known nonexistence results for chores, this yields nonexistence for additive goods. In addition, we show that deciding if a given instance admits a PMMS allocation is NP-hard. We also give explicit instances whose PMMS factors are $226/227$ for goods and $1.102065$ for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a $4/3$-PMMS allocation.