Assignment and Pricing in Roommate Market

Authors

  • Pak Chan The Chinese University of Hong Kong
  • Xin Huang The Chinese University of Hong Kong
  • Zhengyang Liu Shanghai Jiao Tong University
  • Chihao Zhang Shanghai Jiao Tong University
  • Shengyu Zhang The Chinese University of Hong Kong

DOI:

https://doi.org/10.1609/aaai.v30i1.10019

Keywords:

Stable roommate, Resource allocation, Assignment game

Abstract

We introduce a roommate market model, in which 2n people need to be assigned to n rooms, with two people in each room. Each person has a valuation to each room, as well as a valuation to each of other people as a roommate. Each room has a rent shared by the two people living in the room, and we need to decide who live together in which room and how much each should pay. Various solution concepts on stability and envy-freeness are proposed, with their existence studied and the computational complexity of the corresponding search problems analyzed. In particular, we show that maximizing the social welfare is NP-hard, and we give a polynomial time algorithm that achieves at least 2/3 of the maximum social welfare. Finally, we demonstrate a pricing scheme that can achieve envy-freeness for each room.

Downloads

Published

2016-02-21

How to Cite

Chan, P., Huang, X., Liu, Z., Zhang, C., & Zhang, S. (2016). Assignment and Pricing in Roommate Market. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10019

Issue

Section

Technical Papers: Game Theory and Economic Paradigms