Almost (Weighted) Proportional Allocations for Indivisible Chores

Bo Li, Yingkai Li, Xiaowei Wu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents' ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.

Original languageEnglish
Title of host publicationWWW 2022 - Proceedings of the ACM Web Conference 2022
PublisherAssociation for Computing Machinery, Inc
Pages122-131
Number of pages10
ISBN (Electronic)9781450390965
DOIs
Publication statusPublished - 25 Apr 2022
Event31st ACM World Wide Web Conference, WWW 2022 - Virtual, Online, France
Duration: 25 Apr 202229 Apr 2022

Publication series

NameWWW 2022 - Proceedings of the ACM Web Conference 2022

Conference

Conference31st ACM World Wide Web Conference, WWW 2022
Country/TerritoryFrance
CityVirtual, Online
Period25/04/2229/04/22

Keywords

  • fair allocation
  • partial information
  • price of fairness
  • proportionality

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Cite this