Scholarlink

We study the problem of fairly allocating a set of indivisible chores among a set of agents, who possess heterogeneous costs over the chores. We assume that agents’ costs are bounded and lie in the interval [1, k]. We aim to find both fair and efficient allocations under this setting. We first show that a k-EFX and fPO allocation can be computed in polynomial time. Next, we generalize the result to the weighted setting and show the existence of a k-WEFX and fPO allocation. Finally, for \(k = 2\) , we can compute an EFX allocation based on the well-known round-robin algorithm.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximate EFX and Efficient Allocations of Chores for Bounded Preferences

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Hui Liu,
  • Zhijie Zhang

摘要

We study the problem of fairly allocating a set of indivisible chores among a set of agents, who possess heterogeneous costs over the chores. We assume that agents’ costs are bounded and lie in the interval [1, k]. We aim to find both fair and efficient allocations under this setting. We first show that a k-EFX and fPO allocation can be computed in polynomial time. Next, we generalize the result to the weighted setting and show the existence of a k-WEFX and fPO allocation. Finally, for \(k = 2\) , we can compute an EFX allocation based on the well-known round-robin algorithm.