High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911760463691776 |
|---|---|
| author | Bredereck, Robert Kaczmarczyk, Andrzej Knop, Dušan Niedermeier, Rolf |
| author_facet | Bredereck, Robert Kaczmarczyk, Andrzej Knop, Dušan Niedermeier, Rolf |
| contents | Using insights from parametric integer linear programming, we significantly improve on our previous work [Proc. ACM EC 2019] on high-multiplicity fair allocation. Therein, answering an open question from previous work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter "number of agents" plus "number of item types." Our central improvement, compared to this result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary, thus greatly expanding the range of feasible values. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2005_04907 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming Bredereck, Robert Kaczmarczyk, Andrzej Knop, Dušan Niedermeier, Rolf Computer Science and Game Theory Data Structures and Algorithms F.2.2 Using insights from parametric integer linear programming, we significantly improve on our previous work [Proc. ACM EC 2019] on high-multiplicity fair allocation. Therein, answering an open question from previous work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter "number of agents" plus "number of item types." Our central improvement, compared to this result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary, thus greatly expanding the range of feasible values. |
| title | High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming |
| topic | Computer Science and Game Theory Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2005.04907 |