High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-20065S" target="_blank" >GA17-20065S: Tight Parameterized Results for Directed Connectivity Problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
EC '19 Proceedings of the 2019 ACM Conference on Economics and Computation
ISBN
9781450367929
ISSN
—
e-ISSN
—
Number of pages
19
Pages from-to
505-523
Publisher name
ACM
Place of publication
New York
Event location
Phoenix, TX
Event date
Jun 24, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000483848100057