To give or not to give: Fair division for single minded valuations

Simina Brânzei, Yuezhou Lv, Ruta Mehta

Research output: Contribution to journalConference article

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.

Original languageEnglish (US)
Pages (from-to)123-129
Number of pages7
JournalIJCAI International Joint Conference on Artificial Intelligence
Volume2016-January
StatePublished - Jan 1 2016
Event25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, United States
Duration: Jul 9 2016Jul 15 2016

Fingerprint

Costs

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this

To give or not to give : Fair division for single minded valuations. / Brânzei, Simina; Lv, Yuezhou; Mehta, Ruta.

In: IJCAI International Joint Conference on Artificial Intelligence, Vol. 2016-January, 01.01.2016, p. 123-129.

Research output: Contribution to journalConference article

@article{26795d6cd5714b9eb7b2c5a849c97779,
title = "To give or not to give: Fair division for single minded valuations",
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.",
author = "Simina Br{\^a}nzei and Yuezhou Lv and Ruta Mehta",
year = "2016",
month = "1",
day = "1",
language = "English (US)",
volume = "2016-January",
pages = "123--129",
journal = "IJCAI International Joint Conference on Artificial Intelligence",
issn = "1045-0823",

}

TY - JOUR

T1 - To give or not to give

T2 - Fair division for single minded valuations

AU - Brânzei, Simina

AU - Lv, Yuezhou

AU - Mehta, Ruta

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85006166558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85006166558&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85006166558

VL - 2016-January

SP - 123

EP - 129

JO - IJCAI International Joint Conference on Artificial Intelligence

JF - IJCAI International Joint Conference on Artificial Intelligence

SN - 1045-0823

ER -