High-Multiplicity Fair Allocation Made More Practical
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00350296" target="_blank" >RIV/68407700:21240/21:00350296 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.5555/3463952.3463988" target="_blank" >https://doi.org/10.5555/3463952.3463988</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5555/3463952.3463988" target="_blank" >10.5555/3463952.3463988</a>
Alternative languages
Result language
angličtina
Original language name
High-Multiplicity Fair Allocation Made More Practical
Original language description
The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC~2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for "high-multiplicity fair allocation", exploiting parameters such as the number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We "engineer" their work towards practical usefulness, thereby being able to solve all real-world instances from the state-of-art online platform "spliddit.org for provably fair solutions". Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e.g., allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain "solution paths" which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.
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/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
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
AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021
ISBN
978-1-7138-3262-1
ISSN
1548-8403
e-ISSN
—
Number of pages
9
Pages from-to
260-268
Publisher name
ACM
Place of publication
New York
Event location
virtual
Event date
May 3, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—