High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming

Popis výsledku anglicky

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.

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

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2023

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

European Conference on Artificial Intelligence 2023

ISBN

978-1-64368-436-9

ISSN

0922-6389

e-ISSN

—

Počet stran výsledku

8

Strana od-do

303-310

Název nakladatele

IOS Press

Místo vydání

Amsterdam

Místo konání akce

Krakov

Datum konání akce

30. 9. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—