Online Matching with Stochastic Rewards

Series: 
Graph Theory Seminar
Tuesday, February 19, 2013 - 12:05
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Duke University
Organizer: 
   The online matching problem has received significant attention in recent years because of its connections to allocation problems in internet advertising, crowd sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic event that comes after the allocation. These applications motivate us to introduce stochastic rewards in the online matching problem. In this talk, I will formally define this problem, point out its connections to previously studied allocation problems, give a deterministic algorithm that is close to optimal in its competitive ratio,  and describe some directions of future research in this line of work. (Based on joint work with Aranyak Mehta.)