The price of fairness for a small number of indivisible items

DOI10.1007/978-3-319-28697-6_47MaRDI QIDQ2806954zbMATHOpenAlexFDO

Authors Sascha Kurz

Publication date 19 May 2016

Published in Operations Research Proceedings (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.5722

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

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 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 turned out that the price of fairness increases sublinear 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 could be determined. Additionally an efficient integer programming formulation is given.

Recommendations

• The price of fairness for indivisible goods
• The efficiency of fair division
• Fair allocation of indivisible goods: the two-agent case
• Fair division of indivisible items
• Price of fairness for allocating a bounded resource

Cites work

• The efficiency of fair division
• The price of fairness

Cited in

(6)

• Computing welfare-maximizing fair allocations of indivisible goods
• The price of equity with binary valuations and few agent types
• The price of fairness for indivisible goods
• The price of fairness for a two-agent scheduling game minimizing total completion time
• The efficiency of fair division
• Optimal bounds on the price of fairness for indivisible goods

This page was built for publication: The price of fairness for a small number of indivisible items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806954)