Theory Seminar: Fully Polynomial-Time Approximation Schemes for Fair Rent Division
Wednesday, January 23, 2019
CS4310, Computer Sciences and Statistics
Speaker: Nidhi Rathi, Indian Institute of Science. Abstract: 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. 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.