Fair resource sharing and dorm assignment

Bo Li, Yingkai Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

In this work, we study the fair resource sharing problem, where a set of resources needs to be shared by a set of agents. Each agent is unit-demand and each resource can serve a limited number of agents. The agents have (heterogeneous) preferences for the resources, and preferences for other agents with whom they share the resources. Our definition of fairness is mainly captured by envy-freeness. Due to the fact that an envy-free assignment may not exist even in simple settings, we propose a way to relax the definition: Pareto envy-freeness, where an assignment is Pareto envy-free if for any two agents i and j, agent i does not envy agent j for her received resource or the set of agents she shares the resource with. We study to what extent Pareto envy-free assignments exist. Particularly, we are interested in a typical model, dorm assignment problem, where a number of students need to be accommodated to the dorms with the same capacity and the students' preferences for dorm-mates are binary. We show that when the capacities of the dorms are 2, a Pareto envy-free assignment always exists and can be found in polynomial time; however, if the capacities increase to 3, Pareto envy-freeness cannot be guaranteed any more.

Original languageEnglish
Title of host publicationProceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
EditorsBo An, Amal El Fallah Seghrouchni, Gita Sukthankar
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages708-716
Number of pages9
ISBN (Electronic)9781450375184
Publication statusPublished - 2020
Externally publishedYes
Event19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020 - Virtual, Auckland, New Zealand
Duration: 19 May 2020 → …

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2020-May
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020
Country/TerritoryNew Zealand
CityVirtual, Auckland
Period19/05/20 → …

Keywords

  • Dorm assignment
  • Fair division
  • Resource sharing

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Cite this