CS Theory Seminar: Fully Polynomial-Time Approximation Schemes for Fair Rent Division
Speaker: Nidhi Rathi, IISc, Bangalore, India
Wednesday, January 23, 2019
We study the problem of fair rent division that entails splitting the rent and allocating the rooms of an apartment among roommates (agents) in a fair manner. In this setup, 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 for any other agent’s room. This work develops approximation algorithms for fair rent division with minimal assumptions.