On the Fairness of Rent Division Among Roommates Open Access

Abstract

In this study, we aim to find a method for assigning rooms and dividing rent among roommates who wish to rent a house together. We assume there are n rooms to be allocated to the same number of roommates with quasi-linear utility functions. Our primary focus is on identifying different procedural algorithms that can generate an allocation meeting specific fairness criteria, including envy-freeness, equitability, individual rationality, and efficiency, among others. We demonstrated the incompatibility between envy-freeness and equitability in certain scenarios by proving a necessary and sufficient condition for the existence of an equitable and envy-free allocation. We also analyzed some main trade-offs in a rent division problem and the lack of incentive compatibility in our model. Besides deriving conclusions based on the valuation matrix, we developed a graph representation of the model that visualizes the envy network and guarantees the functionality of graph-based algorithms. By referencing previous studies in the field of fair division, we designed a procedure that generates an allocation that is individually rational, utilitarian, envy-free, and whenever possible, equitable.  

Table of Contents

1. Introduction …………………………………………………………….…………….. 1

2. Model and Fairness Criteria …………………………………………….……………. 5

2.1 Model Specification ……………………………………………………….…… 5

2.2 Different Criteria for Fairness ………………………………….…….………… 6

3. Equitability and Utility Maximization …………………………………….……….… 9

3.1 Equitable Allocation for Arbitrary n ……………………………….…….…..… 9

3.2 Utilitarian Room Assignment for Arbitrary n …………………………………. 10

3.3 Equitable and Utilitarian Allocation for Arbitrary n ……………..……..……... 12

4. Envy-freeness …………………………………………………………………..…… 15

4.1 Envy-free Allocations for n=2 and n=3 ……………………………….….…… 15

4.2 The Incompatibility Between Equitability and Envy-freeness ……….….......... 17

4.3 Graph Representation of the Envy Network ……………....….….................…. 24

4.4 Procedure for Finding an Envy-free Allocation ……………....……..........…… 32

5. Discussion ………………………………………………………………...…….…… 38

5.1 A Discussion on Truthfulness ………………………………….…………….… 38

5.2 A Discussion on Non-Negativity ………………………………….…………… 41

6. Conclusion …………………………………………………………………………… 45

About this Honors Thesis

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Quantitative Science
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Mathematics Sociology, Theory and Methods
Keyword	Fair Division Rent Division Allocation Theory
Committee Chair / Thesis Advisor	John Patty, Emory University
Committee Members	Elizabeth Newman, Emory University Ruoxuan Xiong, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	On the Fairness of Rent Division Among Roommates ()	2024-11-22 18:57:42 -0500	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions