Fair Division of Chores with Budget Constraints

被引：1

作者：

Elkind, Edith ^{[1
,2
]}

Igarashi, Ayumi ^{[3
]}

Teh, Nicholas ^{[1
]}

机构：

[1] Univ Oxford, Oxford, England

[2] Alan Turing Inst, London, England

[3] Univ Tokyo, Bunkyo City, Japan

来源：

ALGORITHMIC GAME THEORY, SAGT 2024 | 2024年 / 15156卷

关键词：

Fair Allocation; Chores; Budget Constraints;

D O I：

10.1007/978-3-031-71033-9_4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study fair allocation of indivisible chores to agents under budget constraints, where each chore has an objective size and disutility. This model captures scenarios where a set of chores need to be divided among agents with limited time, and each chore has a specific time needed for completion. We propose a budget-constrained model for allocating indivisible chores, and systematically explore the differences between goods and chores in this setting. We establish the existence of an EFX allocation. We then show that EF2 allocations are polynomial-time computable in general; for many restricted settings, we strengthen this result to EF1.

引用

页码：55 / 71

页数：17

共 24 条

[1]

Airiau S., 2023, P 26 EUR C ART INT E, P52

[2] Fair division of indivisible goods: Recent progress and open questions [J].