Adjusted Winner: from Splitting to Selling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908830212816896 |
|---|---|
| author | Bredereck, Robert Sun, Bin Briman, Eyal Talmon, Nimrod |
| author_facet | Bredereck, Robert Sun, Bin Briman, Eyal Talmon, Nimrod |
| contents | The Adjusted Winner (AW) method is a fundamental procedure for the fair division of indivisible resources between two agents. However, its reliance on splitting resources can lead to practical complications. To address this limitation, we propose an extension of AW that allows the sale of selected resources under a budget constraint, with the proceeds subsequently redistributed, thereby aiming for allocations that remain as equitable as possible. Alongside developing this extended framework, we provide an axiomatic analysis that examines how equitability and envy-freeness are modified in our setting. We then formally define the resulting combinatorial problems, establish their computational complexity, and design a fully polynomial-time approximation scheme (FPTAS) to mitigate their inherent intractability. Finally, we complement our theoretical results with computer-based simulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12231 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Adjusted Winner: from Splitting to Selling Bredereck, Robert Sun, Bin Briman, Eyal Talmon, Nimrod Computer Science and Game Theory The Adjusted Winner (AW) method is a fundamental procedure for the fair division of indivisible resources between two agents. However, its reliance on splitting resources can lead to practical complications. To address this limitation, we propose an extension of AW that allows the sale of selected resources under a budget constraint, with the proceeds subsequently redistributed, thereby aiming for allocations that remain as equitable as possible. Alongside developing this extended framework, we provide an axiomatic analysis that examines how equitability and envy-freeness are modified in our setting. We then formally define the resulting combinatorial problems, establish their computational complexity, and design a fully polynomial-time approximation scheme (FPTAS) to mitigate their inherent intractability. Finally, we complement our theoretical results with computer-based simulations. |
| title | Adjusted Winner: from Splitting to Selling |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.12231 |