To Give or Not to Give: Fair Division for Single Minded Valuations

Brânzei, Simina; Lv, Yuezhou; Mehta, Ruta

To Give or Not to Give: Fair Division for Single Minded Valuations

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 123-128.

Abstract

Single minded agents have strict preferences, in which a bundle is acceptable only if it meets a certain demand. Such preferences arise naturally in scenarios such as allocating computational resources among users, where the goal is to fairly serve as many requests as possible. In this paper we study the fair division problem for such agents, which is complex due to discontinuity and complementarities of preferences. Our solution concept — the competitive allocation from equal incomes (CAEI) — is inspired from market equilibria and implements fair outcomes through a pricing mechanism. We study existence and computation of CAEI for multiple divisible goods, discrete goods, and cake cutting. Our solution is useful more generally, when the players have a target set of goods, and very small positive values for any bundle other than their target set.

Simina Brânzei, Yuezhou Lv, and Ruta Mehta. 2016. To Give or Not to Give: Fair Division for Single Minded Valuations. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 123–128. https://ijcai.org/proceedings/2016/25

@inproceedings{ijcai2016p25,
  title     = {To Give or Not to Give: Fair Division for Single Minded Valuations},
  author    = {Brânzei, Simina and Lv, Yuezhou and Mehta, Ruta},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {123--128},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/25},
}

TY  - CPAPER
TI  - To Give or Not to Give: Fair Division for Single Minded Valuations
AU  - Brânzei, Simina
AU  - Lv, Yuezhou
AU  - Mehta, Ruta
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 123
EP  - 128
UR  - https://ijcai.org/proceedings/2016/25
ER  -