Title: Assignment Problems in Rental Markets
Speaker: Dr. Vijay Kumar
Date: March 24, 2008
Abstract:
I will talk about my experience with variations of the classical assignment and stable marriage problems in connection with some efforts in the DVD rentals area.
There are a collection of assignment problems with one-sided preferences that arise naturally in rental markets. These problems possess a rich mathematical structure and are related to well-known assignment problems. We formalize and characterize these problems in terms of one-sided matching problems and consider several solution concepts. We choose some "value" functions to capture objectives such as fairness, efficiency and social welfare, in order to evaluate and compare solution concepts. We also consider models of rental markets corresponding to static, online and dynamic customer valuations. We provide some approximation results and hardness results, as well as some results based on experimental evaluation.
This is joint work with David Abraham, Ning Chen and Vahab Mirrokni. Time permitting, I will perhaps give a small overview of other interesting challenges encountered.
About the Speaker:
Vijay Kumar works at Amazon.com where he is building a small team working on online advertising and ad auctions. He earlier worked at IBM India Research Lab from 1998 to 2001. He has a BTech in CSE from IIT Delhi and a PhD from Northwestern University.