Online Matching with Stochastic Rewards
Venue
Symposium on Foundations of Computer Science (FOCS), IEEE (2012)
Publication Year
2012
Authors
Aranyak Mehta, Debmalya Panigrahi
BibTeX
Abstract
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
process which follows the allocation. To address such applications, we propose and
study the online matching problem with stochastic rewards (called the Online
Stochastic Matching problem) in this paper. Our problem also has close connections
to the existing literature on stochastic packing problems, in fact, our work
initiates the study of online stochastic packing problems. We give a deterministic
algorithm for the Online Stochastic Matching problem whose competitive ratio
converges to (approximately) 0.567 for uniform and vanishing probabilities. We also
give a randomized algorithm which outperforms the deterministic algorithm for
higher probabilities. Finally, we complement our algorithms by giving an upper
bound on the competitive ratio of any algorithm for this problem. This result shows
that the best achievable competitive ratio for the Online Stochastic Matching
problem is provably worse than that for the (non-stochastic) online matching
problem.
