Fair Division with Indivisible Goods, Chores, and Cake
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908635527905280 |
|---|---|
| author | Aziz, Haris Lu, Xinhang Mackenzie, Simon Suzuki, Mashbat |
| author_facet | Aziz, Haris Lu, Xinhang Mackenzie, Simon Suzuki, Mashbat |
| contents | We study the problem of fairly allocating indivisible items and a desirable heterogeneous divisible good (i.e., cake) to agents with additive utilities. In our paper, each indivisible item can be a good that yields non-negative utilities to some agents and a chore that yields negative utilities to the other agents. Given a fixed set of divisible and indivisible resources, we investigate almost envy-free allocations, captured by the natural fairness concept of envy-freeness for mixed resources (EFM). It requires that an agent $i$ does not envy another agent $j$ if agent $j$'s bundle contains any piece of cake yielding positive utility to agent $i$ (i.e., envy-freeness), and agent $i$ is envy-free up to one item (EF1) towards agent $j$ otherwise. We prove that with indivisible items and a cake, an EFM allocation always exists for any number of agents with additive utilities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_04891 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair Division with Indivisible Goods, Chores, and Cake Aziz, Haris Lu, Xinhang Mackenzie, Simon Suzuki, Mashbat Computer Science and Game Theory We study the problem of fairly allocating indivisible items and a desirable heterogeneous divisible good (i.e., cake) to agents with additive utilities. In our paper, each indivisible item can be a good that yields non-negative utilities to some agents and a chore that yields negative utilities to the other agents. Given a fixed set of divisible and indivisible resources, we investigate almost envy-free allocations, captured by the natural fairness concept of envy-freeness for mixed resources (EFM). It requires that an agent $i$ does not envy another agent $j$ if agent $j$'s bundle contains any piece of cake yielding positive utility to agent $i$ (i.e., envy-freeness), and agent $i$ is envy-free up to one item (EF1) towards agent $j$ otherwise. We prove that with indivisible items and a cake, an EFM allocation always exists for any number of agents with additive utilities. |
| title | Fair Division with Indivisible Goods, Chores, and Cake |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2511.04891 |