Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	陈礴教授，华威大学
Inviter:	陈旭瑾研究员
Title:	Fairness Criteria for Allocating Indivisible Chores: Connections and Efficiencies
Language:	Chinese
Time & Venue:	2023.03.24 14:30-15:30 南楼N226
Abstract:	We study several fairness notions in allocating indivisible chores (i.e., items with non-positive utilities) to agents, who have additive and submodular cost functions. The fairness criteria we are concerned with are envy-free up to any item (EFX), envy-free up to one item (EF1), maximin share (MMS), and pairwise maximin share (PMMS), which are proposed as relaxations of envy-freeness in the setting of additive cost functions. For allocations under each fairness criterion, we establish their approximation guarantee for other fairness criteria. Under the additive setting, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between allocations of goods (i.e., items with positive utilities) and chores. However, such strong relationships cannot be inherited by the submodular setting, under which PMMS and MMS are no longer relaxations of envy-freeness and even worse, few non-trivial guarantees exist. We also investigate efficiency loss under these fairness constraints and establish their prices of fairness.