bei Google ScholarTitelangaben
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
(Hrsg.):
Operations Research Proceedings 2014. -
Cham
: Springer
,
2016
. - S. 335-340
ISBN 978-3-319-28695-2
DOI: https://doi.org/10.1007/978-3-319-28697-6_47
Abstract
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.
Weitere Angaben
| Publikationsform: | Aufsatz in einem Buch |
|---|---|
| Begutachteter Beitrag: | Ja |
| Keywords: | fair division; fairness; price of fairness; indivisible items; envy-freeness; few items |
| Fachklassifikationen: | Mathematics Subject Classification Code: 91B32 |
| Institutionen der Universität: | Fakultäten > Fakultät für Mathematik, Physik und Informatik Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik Profilfelder > Emerging Fields > Governance and Responsibility Fakultäten Profilfelder Profilfelder > Emerging Fields |
| Titel an der UBT entstanden: | Ja |
| Themengebiete aus DDC: | 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik 500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Eingestellt am: | 20 Apr 2016 09:45 |
| Letzte Änderung: | 20 Apr 2016 09:45 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/32234 |