Hi all,
We will kick off the theory seminar this semester with a talk on fair division tomorrow. The speaker, Nidhi Rathi, is a Ph.D. student at IISc, Bangalore working with Siddharth Barman, whom some of you might remember as an alum who graduated from our department in 2012. The details of the seminar are below. See you all there.
Shuchi
Title:ÂFully Polynomial-Time Approximation Schemes for ÂFair Rent Division
Speaker: Nidhi Rathi, IISc, Bangalore, India
Location/time: CS 4310, January 23 12-1 pmÂ
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. 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. The cardinal preferences of theÂagents are expressed via functions which specify the utilities of the agents for the rooms for everyÂpossible room rent/price. While envy-free solutions are guaranteed to exist under reasonably generalÂutility functions, efficient algorithms for finding them were known only for quasilinear utilities. ThisÂwork addresses this notable gap and develops approximation algorithms for fair rent division withÂminimal assumptions on the utility functions. This is joint work with Eshwar Arunachaleswaran and Siddharth Barman, and appeared in SODA'19.
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}