Szczegóły publikacji
Opis bibliograficzny
High-multiplicity fair allocation using parametric integer linear programming / Robert Bredereck, Andrzej KACZMARCZYK, Dušan Knop, Rolf Niedermeier // W: ECAI 2023 : 26th European Conference on Artificial Intelligence : including 12th conference on Prestigious Applications of Intelligent Systems (PAIS 2023) : September 30 - October 4, 2023, Kraków, Poland : proceedings / ed. by Kobi Gal, [et al.] ; European Association for Artificial Intelligence (EurAI), Polish Artificial Intelligence Society (PSSI). — Amsterdam : IOS Press BV, cop. 2023. — (Frontiers in Artificial Intelligence and Applications ; ISSN 0922-6389 ; vol. 372). — ISBN: 978-1-64368-436-9; e-ISBN: 978-1-64368-437-6. — S. 303-310. — Bibliogr. s. 309-310, Abstr. — Dod. abstrakt dostępny w: https://ecai2023.eu/acceptedpapers [2023-11-06]. — A. Kaczmarczyk - dod. afiliacja: Technische Universität Berlin
Autorzy (4)
- Bredereck Robert
- AGHKaczmarczyk Andrzej
- Knop Dušan
- Niedermeier Rolf
Dane bibliometryczne
| ID BaDAP | 149121 |
|---|---|
| Data dodania do BaDAP | 2023-10-16 |
| Tekst źródłowy | URL |
| DOI | 10.3233/FAIA230284 |
| Rok publikacji | 2023 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Creative Commons | |
| Wydawca | IOS Press |
| Konferencja | European Conference on Artificial Intelligence 2023 |
| Czasopismo/seria | Frontiers in Artificial Intelligence and Applications |
Abstract
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.
