Assignment and Pricing in Roommate Market
- 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
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.
How to Cite
- Endnote/Zotero/Mendeley (RIS)
Information
- For Readers
- For Authors
- For Librarians
Developed By
Subscription.
Login to access subscriber-only resources.
Part of the PKP Publishing Services Network
Copyright © 2024, Association for the Advancement of Artificial Intelligence
- DOI: 10.1609/aaai.v30i1.10019
- Corpus ID: 7194645
Assignment and Pricing in Roommate Market
- P. Chan , Xin Huang , +2 authors Shengyu Zhang
- Published in AAAI Conference on Artificial… 12 February 2016
- Economics, Mathematics
Figures and Tables from this paper
13 Citations
3 . 2 constant approximation algorithm for online roommate market, room allocation with capacity diversity and budget constraints.
- Highly Influenced
- 10 Excerpts
Rent Division Among Groups
Fair resource sharing and dorm assignment, fair resource sharing with externailties ∗, the temporary exchange problem, secretary matching with vertex arrivals and no rejections, your college dorm and dormmates: fair resource sharing with externalities, repeatedly matching items to agents fairly and efficiently, algorithms for trip-vehicle assignment in ride-sharing, 27 references, two's company, three's a crowd: stable family and threesome roommates problems, room assignment-rent division: a market approach.
- Highly Influential
The assignment game I: The core
An efficient algorithm for the "stable roommates" problem, three-dimensional stable matching problems, strong stability in the hospitals/residents problem, the exchange-stable marriage problem, sponsored search, market equilibria, and the hungarian method, on the stability of multiple partner stable marriages with ties, stable matchings in three-sided systems with cyclic preferences, related papers.
Showing 1 through 3 of 0 Related Papers
- Microeconomics
- Game Theory
Assignment and Pricing in Roommate Market Pak Hay Chan Xin Huang Zhengyang Liu
- Distribute all flashcards reviewing into small sessions
- Get inspired with a daily photo
- Import sets from Anki, Quizlet, etc
- Add Active Recall to your learning and get higher grades!
Related documents
Add this document to collection(s)
You can add this document to your study collection(s)
Add this document to saved
You can add this document to your saved list
Suggest us how to improve StudyLib
(For complaints, use another form )
Input it if you want to receive answer
#1 Assignment and Pricing in Roommate Market [PDF ] [Copy] [Kimi ]
Authors : Pak Chan ; Xin Huang ; Zhengyang Liu ; Chihao Zhang ; Shengyu Zhang
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.
Stared Paper(s):
[P] [K] Assignment and Pricing in Roommate Market
Magic Token:
Kimi Language:
Desc Language:
Bug report? Issue submit? Please visit:
Github: https://github.com/bojone/papers.cool
Hope you will enjoy it.
More interesting features can be found at kexue.fm and kimi.ai .
- Advanced Search
Fair Resource Sharing and Dorm Assignment
New citation alert added.
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
New Citation Alert!
Please log in to your account
Information & Contributors
Bibliometrics & citations.
- Gross–Humbert N Benabbou N Beynier A Maudet N (2023) Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-based Utilities ACM Transactions on Economics and Computation 10.1145/3569704 10 :4 (1-24) Online publication date: 5-Apr-2023 https://dl.acm.org/doi/10.1145/3569704
Index Terms
Theory of computation
Models of computation
Theory and algorithms for application domains
Algorithmic game theory and mechanism design
Recommendations
Fair division of indivisible goods among strategic agents.
We study fair division of indivisible goods among strategic agents in a single-parameter environment. This work specifically considers fairness in terms of envy freeness up to one good (EF1) and maximin share guarantee (MMS). We show that (in a single-...
Mechanism design for fair division: allocating divisible items without payments
We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness . This solution, ...
Truthful fair division
We address the problem of fair division, or cake cutting, with the goal of finding truthful mechanisms. In the case of a general measure space ("cake") and non-atomic, additive individual preference measures - or utilities - we show that there exists a ...
Information
Published in.
- General Chairs:
Sorbonne University, France
University of Central Florida, United States
- Program Chairs:
Nanyang Technological University, Singapore
Delft University of Technology, Netherlands
- SIGAI: ACM Special Interest Group on Artificial Intelligence
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Check for updates, author tags.
- dorm assignment
- fair division
- resource sharing
- Research-article
Funding Sources
- European Research Council (ERC)
Acceptance Rates
Contributors, other metrics, bibliometrics, article metrics.
- 1 Total Citations View Citations
- 73 Total Downloads
- Downloads (Last 12 months) 10
- Downloads (Last 6 weeks) 0
View Options
Login options.
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
View options.
View or Download as a PDF file.
View online with eReader .
Share this Publication link
Copying failed.
Share on social media
Affiliations, export citations.
- Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
- Download citation
- Copy citation
We are preparing your search results for download ...
We will inform you here when the file is ready.
Your file of search results citations is now ready.
Your search export query has expired. Please try again.
IMAGES
VIDEO
COMMENTS
prices p. An desirable output is a price vector and a feasible assignment at which each seller maximizes revenues, each buyer maximizes net valuations, and markets clear. In this paper, we propose a novel roommate market model that takes both room sharing and pricing into consideration. In this model, each participant i 2Ihas a valuation v ir
An desirable output is a price vector and a feasible assignment at which each seller maximizes revenues, each buyer maximizes net valuations, and markets clear. In this paper, we propose a novel roommate market model that takes both room sharing and pricing into consideration. In this model, each participant i ∈ I has a valuation v ir
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.
Assignment and Pricing in Roommate Market. March 8, 2023. Authors. Pak Chan. The Chinese University of Hong Kong. Xin Huang. The Chinese University of Hong Kong. ... Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide ...
It is shown that maximizing the social welfare is NP-hard, and a polynomial-time algorithm is given that achieves at least 2/3 of the maximum social welfare. 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 ...
Assignment and pricing in roommate market; Article. Share on. Assignment and pricing in roommate market. Authors ...
Assignment and pricing in roommate market; Article . Free Access. Share on. Assignment and pricing in roommate market. Authors: Pak Hay Chan. The Chinese University of Hong Kong, HK. The Chinese University of Hong Kong, HK. View Profile, Xin Huang.
Request PDF | Assignment and Pricing in Roommate Market | 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 ...
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.
Assignment and Pricing in Roommate Market. Pak Hay Chan, Xin Huang, Zhengyang Liu, Chihao Zhang, Shengyu Zhang. Assignment and Pricing in Roommate Market. In Dale Schuurmans, Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA. pages 446-452, AAAI ...
Abstract. Roommates are a fundamental aspect of college expe rience, and better college outcom es in terms of. academic performance, social wellbeing and integr ation, ps ychological support etc ...
Our roommate market model is closely related to two problems: 3-Dimensional Stable Matching (Knuth 1997) and Room Assignment-Rent Division (Abdulkadiroglu, Sönmez, andÜnver 2004). The 3 ...
Free essays, homework help, flashcards, research papers, book reports, term papers, history, science, politics
We propose an auction mechanism for room assignment-rent division problems which mimics the market mechanism. Our auction mechanism is efficient, envy-free, individu-ally-rational and it yields a non-negative price to each room whenever that is possible with envy-freeness. group of friends rent a house and they shall allocate its rooms and ...
#1 Assignment and Pricing in Roommate Market [PDF] [Kimi]. Authors: Pak Chan; Xin Huang; Zhengyang Liu; Chihao Zhang; Shengyu Zhang. 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.
Pak Hay Chan, Xin Huang, Zhengyang Liu, Chihao Zhang, and Shengyu Zhang. 2016. Assignment and pricing in roommate market. In Thirtieth AAAI Conference on Artificial Intelligence. Google Scholar Digital Library; Joseph Cheriyan. 1997. Randomized O(M(|V|)) Algorithms for Problems in Matching Theory. SIAM J. Comput., Vol. 26, 6 (1997), 1635--1655.
its rooms and share the rent. We propose an auction mechanism for room assignment-rent division problems which mimics the market mechanism. Our auction mechanism is efficient, envy-free, individually-rational and it yields a non-negative price to each room whenever that is possible with envy-freeness.
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 valua
end market, which is likely to be seen more distinctly further on." prime Residential real estate market Supply Elite segment Dynamics* Premium segment Dynamics* Total supply, pcs. 801 -4% 1 402 4% Average price, thousand rub./sq m 1,110 12% 602 0% Average area, sq m 155 -1% 107 1% Average price, mln rub. 171 11% 64 1% Elite segment Dynamics ...
Average price, thousand rub./sq m 1,053 17% 546 -4% Average area, sq m 160 4% 114 7% Average price, mln rub. 168 22% 62 3% * Q1 2020/Q4 2019 ** Q1 2020/Q1 2019 Source: Knight Frank Research, 2020 Andrey Solovyev Director of City Sale Department, Knight Frank Supply Not a single new project entered the high-end residential real estate market in ...
lead to a leap in prices. So we expect some of the announced new launches to be postponed". prime Residential real estate market Supply Premium segment Dynamics* Elite segment Dynamics* Total supply, pcs. 1 346 -24% 837 6% Average price, thousand rub./sq m 600 6% 993 8% Average area, sq m 106 0% 156 4% Average price, mln rub. 63 7% 155 13% ...
An desirable output is a price vector and a feasible assignment at which each seller maximizes revenues, each buyer maximizes net valuations, and markets clear. In this paper, we propose a novel roommate market model that takes both room sharing and pricing into consideration.
Positive dynamics of the average weighted price in both segments. 2 PRIME RESIDENTIAL REAL ESTATE MARKET. MOSCOW Andrey Solovyev Director of City Sale Department, ... Supply volume and average price dynamics of the primary market Source: Knight Frank Research, 2019 Q1 Q2Q3 Q1 Q2 Q3Q1 2017 2018 2019 650 700 2 750 800 850 200 220 240 60 280 300 ...