Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918079575883776 |
|---|---|
| author | Bismuth, Samuel Bliznets, Ivan Segal-Halevi, Erel |
| author_facet | Bismuth, Samuel Bliznets, Ivan Segal-Halevi, Erel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1912_00459 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations Bismuth, Samuel Bliznets, Ivan Segal-Halevi, Erel Computer Science and Game Theory Theoretical Economics 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. |
| title | Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/1912.00459 |