Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations
Samuel Bismuth,
Ivan Bliznets and
Erel Segal-Halevi
Papers from arXiv.org
Abstract:
A set of objects is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If we consider the objects as indivisible, many instances of the decision problem: ``Is there a fair division of the objects among the agents'' are negative. In addition, this question is hard to solve even for most of the special cases. The latter reasons give us a good motivation to relax the problem for which the running time complexity is better, and the number of positive instances (admitting a fair division) will significantly grow. Whereas many works relax the fairness criteria, this paper introduces another relaxation: an agent is allowed to share a \emph{bounded} number of objects between two or more agents in order to attain fairness. The paper studies various notions of fairness, such as proportionality, envy-freeness, equitability, and consensus. We analyze the run-time complexity of finding a fair allocation with a given number of sharings under several restrictions on the agents' valuations, such as: binary, generalized-binary, and non-degenerate.
Date: 2019-12, Revised 2025-07
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://arxiv.org/pdf/1912.00459 Latest version (application/pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:1912.00459
Access Statistics for this paper
More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().