Position Fair Mechanisms Allocating Indivisible Goods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909904141287424 |
|---|---|
| author | Mahara, Ryoga Mizutani, Ryuhei Oki, Taihei Yokoyama, Tomohiko |
| author_facet | Mahara, Ryoga Mizutani, Ryuhei Oki, Taihei Yokoyama, Tomohiko |
| contents | Fair division mechanisms for indivisible goods require agent orderings to deterministically select one allocation when running the algorithm in practice. We introduce position envy-freeness up to one good (PEF1) as a fairness criterion for mechanisms: a mechanism is said to satisfy PEF1 if for any pair of agent orderings, no agent prefers their bundle determined under one ordering to that under another ordering by more than the utility of a single good. First, we propose a scale-invariant, polynomial-time mechanism that satisfies PEF1 and yields an envy-freeness up to one good (EF1) allocation. For the case of two agents, we establish that any mechanism producing a maximum Nash welfare allocation eliminates envy based on positions by removing one good, provided that utilities are positive. Additionally, we present a polynomial-time mechanism based on the adjusted winner procedure, which satisfies PEF1 and produces an EF1 and Pareto optimal allocation for two agents. In contrast, we demonstrate that well-known mechanisms such as round-robin and envy-cycle elimination do not generally satisfy PEF1. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06423 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Position Fair Mechanisms Allocating Indivisible Goods Mahara, Ryoga Mizutani, Ryuhei Oki, Taihei Yokoyama, Tomohiko Computer Science and Game Theory Data Structures and Algorithms Fair division mechanisms for indivisible goods require agent orderings to deterministically select one allocation when running the algorithm in practice. We introduce position envy-freeness up to one good (PEF1) as a fairness criterion for mechanisms: a mechanism is said to satisfy PEF1 if for any pair of agent orderings, no agent prefers their bundle determined under one ordering to that under another ordering by more than the utility of a single good. First, we propose a scale-invariant, polynomial-time mechanism that satisfies PEF1 and yields an envy-freeness up to one good (EF1) allocation. For the case of two agents, we establish that any mechanism producing a maximum Nash welfare allocation eliminates envy based on positions by removing one good, provided that utilities are positive. Additionally, we present a polynomial-time mechanism based on the adjusted winner procedure, which satisfies PEF1 and produces an EF1 and Pareto optimal allocation for two agents. In contrast, we demonstrate that well-known mechanisms such as round-robin and envy-cycle elimination do not generally satisfy PEF1. |
| title | Position Fair Mechanisms Allocating Indivisible Goods |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.06423 |