Pmms fairness does not always exist but guarantees hold for additive chores
Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores
Computer Science and Game Theory
Summary
Sometimes when dividing things that people dislike, called chores, it’s impossible to make everyone as fairly treated as a certain fairness measure called pairwise maximin share (PMMS) demands. The authors found a way to show that this difficulty also applies when dividing goods that people want. They proved that deciding if a perfectly fair PMMS allocation is possible is a hard problem to solve by a computer. Still, they showed that for chores, there is a way to make an allocation that is fairly close to the PMMS standard, within a factor of 4/3.
What this means in practice
- •For resource allocation engineers: Use the 4/3-PMMS guarantee to design fair division algorithms for distributing undesirable tasks when perfect fairness is impossible.
- •For optimization software developers: Incorporate the NP-hardness result when determining the feasibility of PMMS fairness in allocation models for discrete additive preferences.
A theory result. No direct application yet.
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.