betaFeedback

WorksComputer Science

Non-Existence of PMMS Allocations and a 4/34/3-PMMS Guarantee for Additive Chores

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/227226/227 for goods and 1.1020651.102065 for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a 4/34/3-PMMS allocation.

Paper details

vlnc:W_bdah3tks
Version
v1 · latest
Published
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…