Fair division of mixed divisible and indivisible goods
We study the problem of fair division when the set of resources contains both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to this mixed goods setting. In this work, we propose a new fairness...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/159354 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | We study the problem of fair division when the set of resources contains both divisible
and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness
up to one good (EF1) cannot be directly applied to this mixed goods setting. In this
work, we propose a new fairness notion, envy-freeness for mixed goods (EFM), which is a
direct generalization of both EF and EF1 to the mixed goods setting. We prove that an
EFM allocation always exists for any number of agents with additive valuations. We also
propose efficient algorithms to compute an EFM allocation for two agents with general
additive valuations and for n agents with piecewise linear valuations over the divisible
goods. Finally, we relax the envy-freeness requirement, instead asking for ε-envy-freeness
for mixed goods (ε-EFM), and present an efficient algorithm that finds an ε-EFM allocation. |
|---|