High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00368936" target="_blank" >RIV/68407700:21240/23:00368936 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.3233/FAIA230284" target="_blank" >https://doi.org/10.3233/FAIA230284</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.3233/FAIA230284" target="_blank" >10.3233/FAIA230284</a>
Alternative languages
Result language
angličtina
Original language name
High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
Original language description
Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their 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 their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.
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
—
Continuities
V - Vyzkumna aktivita podporovana z jinych verejnych zdroju
Others
Publication year
2023
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
European Conference on Artificial Intelligence 2023
ISBN
978-1-64368-436-9
ISSN
0922-6389
e-ISSN
—
Number of pages
8
Pages from-to
303-310
Publisher name
IOS Press
Place of publication
Amsterdam
Event location
Krakov
Event date
Sep 30, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—