Speaker: 李博助理教授，香港理工大学

Inviter: 陈旭瑾研究员

Title: MMS Allocation of Indivisible Chores with Subadditive Valuations and the Fair Surveillance Assignment Problem

Language: English&Chinese

Time & Venue: 2024.12.31 17:00-18:00 数学院南楼224

Abstract: We study the maximin share (MMS) fair allocation of 𝑚 indivisible chores to 𝑛 agents who have costs for completing the assigned chores. It is known that exact MMS fairness cannot be guaranteed, and so far the best-known approximation for additive cost functions is 13/11 by Huang and Segal-Halevi [EC, 2023]; however, beyond additivity, very little is known. In this work, we first prove that no algorithm can ensure better than min{𝑛, log 𝑚/loglog 𝑚}-approximation if the cost functions are submodular. This result also shows a sharp contrast with the allocation of goods where constant approximations exist as shown by Barman and Krishnamurthy [TEAC, 2020] and Ghodsi et al. [AIJ, 2022]. We then prove that for subadditive costs, there always exists an allocation that is min{𝑛,⌈log 𝑚]}-approximation, and thus the approximation ratio is asymptotically tight. Due to the hardness result for general subadditive costs, we turn to study specific subadditive costs, e.g., vertex cover, which is called the fair surveillance assignment problem, and more. For these settings, we show that constant approximate allocations exist.