Scholarlink

This paper addresses the fair division of indivisible chores in the additive setting. We propose a polynomial-time algorithm that guarantees either a 3.69-EFX or 1.24-proportional allocation for three agents. Additionally, we introduce a new fairness concept called discrete perfect (DP), which applies to chore allocations. We prove the existence of DP for two agents by providing an efficient algorithm and extend this by proposing an algorithm that approximates DP for the general case with n agents. We believe the DP concept holds independent value and could have broader applications.

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

Approximating EFX Through a New Notion of Fairness

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Rui Dai,
  • Yuxuan Wang,
  • Zhengyang Liu,
  • Zihe Wang

摘要

This paper addresses the fair division of indivisible chores in the additive setting. We propose a polynomial-time algorithm that guarantees either a 3.69-EFX or 1.24-proportional allocation for three agents. Additionally, we introduce a new fairness concept called discrete perfect (DP), which applies to chore allocations. We prove the existence of DP for two agents by providing an efficient algorithm and extend this by proposing an algorithm that approximates DP for the general case with n agents. We believe the DP concept holds independent value and could have broader applications.