Online Stochastic Matching with Unequal Probabilities
Aranyak Mehta, Bo Waggoner, Morteza Zadimoghaddam · 2015
The online stochastic matching problem is a variant of online bipartite matching in which edges are labeled with probabilities. A match will “succeed ” with the probability along that edge; this models, for instance, the click of a user in search advertisement. The goal is to maximize the expected number of successful matches. This problem was introduced by Mehta and Panigrahi (FOCS 2012), who focused on the case where all probabilities in the graph are equal. They gave a 0.567-competitive algorithm for vanishing probabilities, relative to a natural benchmark, leaving the general case as an open question. This paper examines the general case where the prob-abilities may be unequal. We take a new algorithmic approach rather than generalizing that of Mehta and Pan-igrahi: Our algorithm maintains, at each time, the proba-bility that each offline vertex has succeeded thus far, and chooses assignments so as to maximize marginal contribu-tions to these probabilities. When the algorithm does not observe the realizations of the edges, this approach gives a 0.5-competitive algorithm, which achieves the known upper bound for such “non-adaptive ” algorithms. We then modify this approach to be “semi-adaptive: ” if the chosen target has already succeeded, choose the arrival’s “second choice ” instead (while still updating the proba-bilities non-adaptively). With one additional tweak to control the analysis, we show that this algorithm achieves a competitive ratio of 0.534 for the unequal, vanishing probabilities setting. A “fully-adaptive ” version of this algorithm turns out to be identical to an algorithm pro-posed, but not analyzed, in Mehta and Panigrahi (2012); we do not manage to analyze it either since it introduces too many dependencies between the stochastic processes. Our semi-adaptive algorithm thus can be seen as allow-ing analysis of competitive ratio while still capturing the power of adaptivity.