Greedy Algorithms for Online Allocation Problems with Stochastic Input

Abstract:

We consider the general problem of allocating items to agents when items arrive online. Each agent specifies a positive real valuation for each item. When an item arrives, it must immediately be assigned to an agent and the decisions cannot be reversed. The goal of the algorithm is to maximize the sum of the values of the items received by the agents.

This problem has a long and rich history dating back to the seminal work of Karp, Vazirani and Vazirani who gave a randomized algorithm for the online bipartite matching problem with competitive ratio 1-1/e, and showed that it is optimal. More recently, Mehta, Saberi, Vazirani and Vazirani studied the problem of ad-allocation for search queries, for which they give an optimal
(1-1/e)-competitive algorithm under some mild assumptions. Interest from web-search companies sparked off a line of research on these problems trying to beat the factor of 1-1/e in stochastic input models. Here, instead of the arrival order of the items being chosen by an adversary, it is assumed that there is some underlying probability distribution according to which the arrival order is generated.

Recently, Devanur, Jain and Kleinberg gave an exceedingly simple analysis of the original algorithm for online bipartite matching using the so-called Randomized Primal-Dual framework. We observe that their proof can be interpreted as a proof of the competitiveness of a greedy algorithm for the same problem, when the input is stochastic. We use this framework to show
that natural greedy algorithms achieve a competitive ratio of 1-1/e for different variants of the online allocation problem with stochastic input. These variants include vertex-weighted bipartite matching and the ad-allocation problem. Then, we use this framework to give a simpler proof
that the original algorithm for online bipartite matching achieves a competitive ratio strictly better than 1-1/e when the input is stochastic.

Finally, we discuss several open problems and state some conjectures. We believe that the Randomized Primal-Dual framework is a powerful tool for analyzing greedy algorithms for online allocation problems with stochastic input, and can be used to develop new insights and solve some of the open problems in this area.