跳到主要导航 跳到搜索 跳到主要内容

Assignment and pricing in roommate market

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

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

摘要

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

源语言英语
主期刊名30th AAAI Conference on Artificial Intelligence, AAAI 2016
出版商AAAI press
页446-452
页数7
ISBN(电子版)9781577357605
出版状态已出版 - 2016
已对外发布是
活动30th AAAI Conference on Artificial Intelligence, AAAI 2016 - Phoenix, 美国
期限: 12 2月 2016 → 17 2月 2016

丛书

姓名30th AAAI Conference on Artificial Intelligence, AAAI 2016

会议

会议30th AAAI Conference on Artificial Intelligence, AAAI 2016
国家/地区美国
市Phoenix
时期12/02/16 → 17/02/16

学术指纹

探究 'Assignment and pricing in roommate market' 的科研主题。它们共同构成独一无二的学术指纹。

引用此