Seminars

View all Seminars  |  Download ICal for this event

Fair Rent Division

Series: Theory Seminar Series

Speaker: Ms. Nidhi Rathi IntPh.D Student Dept. of Mathematics

Date/Time: Mar 13 13:00:00

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Faculty Advisor:

Abstract:
The theory of fair division addresses the fundamental problem of allocating resources among agents with equal entitlements but distinct preferences. In this talk, I will focus on the classic problem of fair rent division that entails splitting the rent (money) and allocating the rooms (indivisible resources) of an apartment among roommates (agents) in a fair manner. Here, a distribution of the rent and an accompanying allocation is said to be fair if it is envy free, i.e., under the imposed rents, no agent has a strictly stronger preference (utility) for any other agent’s room. While envy-free solutions are guaranteed to exist under reasonably general utility functions, efficient algorithms for finding them were known only for quasilinear utilities. Our work addresses this notable gap and develops approximation algorithms for fair rent division with minimal assumptions on the utility functions. Specifically, we show that if the agents have continuous, monotone decreasing, and piecewise- linear utilities, then the fair rent division problem admits a fully polynomial-time approximation scheme (FPTAS). We complement the algorithmic results by proving that the fair rent division problem (under continuous, monotone decreasing, and piecewise-linear utilities) lies in the intersection of the complexity classes PPAD and PLS. This talk is based on a joint work with Eshwar Arunachaleswaran and Siddharth Barman that appeared in SODA 2019.

Speaker Bio:

Host Faculty: Dr. Anand Louis