High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00332046" target="_blank" >RIV/68407700:21240/19:00332046 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1145/3328526.3329649" target="_blank" >http://dx.doi.org/10.1145/3328526.3329649</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3328526.3329649" target="_blank" >10.1145/3328526.3329649</a>

Jazyk výsledku

angličtina

Název v původním jazyce

High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming

Popis výsledku v původním jazyce

We study the (parameterized) computational complexity of problems in the context of fair allocations of indivisible goods. More specifically, we show fixed-parameter tractability results for a broad set of problems concerned with envy-free, Pareto-efficient allocations of items (with agent-specific utility functions) to agents. In principle, this implies efficient exact algorithms for these in general computationally intractable problems whenever we face instances with few agents and low maximum (absolute) utility values. This holds true also in high-multiplicity settings where we may have high numbers of identical items. On the technical side, our approach provides algorithmic meta-theorems covering a rich set of fair allocation problems in the additive preferences model. To achieve this, our main technical contribution is to make an elaborate use of tools from integer linear programming. More specifically, we exploit results originally going back to a famous theorem of Lenstra [Math. Oper. Res. 1983] concerning (the fixed-parameter tractability of) Integer Linear Programs (ILPs) with bounded dimension (that is, the dimension shall be considered as a (small) parameter) and the more recent framework of (combinatorial) N-fold ILPs. We reveal and exploit a fruitful interaction between these two cornerstones in the theory of integer linear programming, which may be of independent interest in applications going beyond fair allocations.

Název v anglickém jazyce

High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming

Popis výsledku anglicky

We study the (parameterized) computational complexity of problems in the context of fair allocations of indivisible goods. More specifically, we show fixed-parameter tractability results for a broad set of problems concerned with envy-free, Pareto-efficient allocations of items (with agent-specific utility functions) to agents. In principle, this implies efficient exact algorithms for these in general computationally intractable problems whenever we face instances with few agents and low maximum (absolute) utility values. This holds true also in high-multiplicity settings where we may have high numbers of identical items. On the technical side, our approach provides algorithmic meta-theorems covering a rich set of fair allocation problems in the additive preferences model. To achieve this, our main technical contribution is to make an elaborate use of tools from integer linear programming. More specifically, we exploit results originally going back to a famous theorem of Lenstra [Math. Oper. Res. 1983] concerning (the fixed-parameter tractability of) Integer Linear Programs (ILPs) with bounded dimension (that is, the dimension shall be considered as a (small) parameter) and the more recent framework of (combinatorial) N-fold ILPs. We reveal and exploit a fruitful interaction between these two cornerstones in the theory of integer linear programming, which may be of independent interest in applications going beyond fair allocations.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-20065S" target="_blank" >GA17-20065S: Těsné parametrizované výsledky pro problémy orientované souvislosti</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

EC '19 Proceedings of the 2019 ACM Conference on Economics and Computation

ISBN

9781450367929

ISSN

—

e-ISSN

—

Počet stran výsledku

19

Strana od-do

505-523

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Phoenix, TX

Datum konání akce

24. 6. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000483848100057