{"ID":2858527,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.06581","arxiv_id":"2510.06581","title":"Constant Weighted Maximin Share Approximations for Chores","abstract":"We study the fair allocation of indivisible chores among agents with asymmetric weights. Among the various fairness notions, weighted maximin share (WMMS) stands out as particularly compelling. However, whether WMMS admits a constant-factor approximation has remained unknown and is one of the important open problems in weighted fair division [ALMW22, Suk25]. So far, the best known approximation ratio is O(log n), where n is the number of agents. In this paper, we advance the state of the art and present the first constant-factor approximate WMMS algorithm. To this end, we introduce canonical instance reductions and different bounds of agents' valuations. We also prove that guaranteeing better than 2-approximation is not possible, which improves the best-known lower bound of 1.366.","short_abstract":"We study the fair allocation of indivisible chores among agents with asymmetric weights. Among the various fairness notions, weighted maximin share (WMMS) stands out as particularly compelling. However, whether WMMS admits a constant-factor approximation has remained unknown and is one of the important open problems in...","url_abs":"https://arxiv.org/abs/2510.06581","url_pdf":"https://arxiv.org/pdf/2510.06581v1","authors":"[\"Bo Li\",\"Fangxiao Wang\",\"Shiji Xing\"]","published":"2025-10-08T02:24:32Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}