Randomized algorithm improves online matching success rates above half
Online Matching with Arbitrary Stochastic Rewards
Data Structures and Algorithms
Summary
Matching online arrivals with offline resources can fail unpredictably, and past methods could only guarantee about half the matches would succeed. The authors present a randomized technique called Perturbed Greedy that improves this guarantee to about 59% for unweighted cases and 53% when resources have different values. This method mixes traditional greedy matching with carefully adjusted probabilistic choices to get better outcomes. Their result applies broadly to many different success probabilities and outperforms all deterministic approaches.
What this means in practice
- •For online marketplace managers: Improve allocation strategies for matching customers with limited-time offers that may fail due to uncertain availability.
- •For real-time job schedulers: Enhance assignment of tasks to resources when success probabilities are unknown and revealed only upon arrival.
Authors
Rajan Udwani
Abstract
Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.