TY - GEN
T1 - Almost (Weighted) Proportional Allocations for Indivisible Chores
AU - Li, Bo
AU - Li, Yingkai
AU - Wu, Xiaowei
N1 - Funding Information:
The authors thank Haris Aziz, Hervé Moulin, Warut Suksompong and several anonymous reviewers for their valuable comments and for pointing out the connection between our work and the survey paper by Moulin.
Publisher Copyright:
© 2022 ACM.
PY - 2022/4/25
Y1 - 2022/4/25
N2 - 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.
AB - 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.
KW - fair allocation
KW - partial information
KW - price of fairness
KW - proportionality
UR - http://www.scopus.com/inward/record.url?scp=85129855908&partnerID=8YFLogxK
U2 - 10.1145/3485447.3512057
DO - 10.1145/3485447.3512057
M3 - Conference article published in proceeding or book
AN - SCOPUS:85129855908
T3 - WWW 2022 - Proceedings of the ACM Web Conference 2022
SP - 122
EP - 131
BT - WWW 2022 - Proceedings of the ACM Web Conference 2022
PB - Association for Computing Machinery, Inc
T2 - 31st ACM World Wide Web Conference, WWW 2022
Y2 - 25 April 2022 through 29 April 2022
ER -