Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

The price of fairness for a small number of indivisible items

Title data

Kurz, Sascha:
The price of fairness for a small number of indivisible items.
In: Lübbecke, Marco ; Koster, Arie ; Letmathe, Peter ; Madlener, Reinhard ; Peis, Britta ; Walther, Grit (ed.): Operations Research Proceedings 2014. - Cham : Springer , 2016 . - pp. 335-340
ISBN 978-3-319-28695-2
DOI: https://doi.org/10.1007/978-3-319-28697-6_47

Abstract in another language

Incorporating fairness criteria in optimization problems comes at a certain cost, which is measured by the so-called price of fairness. Here we consider the allocation of indivisible goods. For envy-freeness as fairness criterion it is known from the literature that the price of fairness can increase linearly in terms of the number of agents. For the constructive lower bound a quadratic number of items was used. In practice this might be inadequately large. So we introduce the price of fairness in terms of both the number of agents and items, i.e., key parameters which generally may be considered as common and available knowledge. It turns out that the price of fairness increases sublinearly if the number of items is not too
much larger than the number of agents. For the special case of coincide of both counts exact asymptotics are determined. Additionally, an efficient integer programming formulation is given.

Further data

Item Type: Article in a book
Refereed: Yes
Keywords: fair division; fairness; price of fairness; indivisible items; envy-freeness; few items
Subject classification: Mathematics Subject Classification Code: 91B32
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy
Profile Fields > Emerging Fields > Governance and Responsibility
Faculties
Profile Fields
Profile Fields > Emerging Fields
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 20 Apr 2016 09:45
Last Modified: 20 Apr 2016 09:45
URI: https://eref.uni-bayreuth.de/id/eprint/32234