Online matching or Is it ad allocation?

The online ad allocation (OAA) problem is the following: "Suppose there are n bidders with known daily budgets B_1, B_2, ..., B_n. There are m queries, that come online. When each query j arrives, bidders i = 1 ,.., n submit bids u_{ij} . The algorithm has to allocate the query to one of the bidders, without knowing the future bids. If query j is allocated to bidder i, then the algorithm collects revenue u_{ij }; however, the total revenue collected from bidder i cannot exceed B_i." Replace bidders and queries by nodes, bids by weights, and you have an online bipartite matching (OPM) problem variant. So, when is OPM an OAA, really? In other words, when is OPM a real applied problem, and when is it pseudo?

In any case, this is a meaty problem and here are three examples of what we know in theortical CS community:

• Aranyak Mehta together with his coauthors (1,2), showed a tight 1-1/e bound for the problem in the worst case, and that when the input is a random permutation, even greedy algorithm achieves 1-1/e approximation (which is nice since algorithms for this problem in "practice" can be interpreted to be of this genre). These papers provide great clarity and sophisticated analyses, TCS-style.
  
• Nikhil Devanur and his coauthors (1) show that under the random permuation model, there is an algorithm that gets 1-\eps of the optimal. This work has nice insights mixing primal-dual thinking with PAC learning, insights that are getting refined as they get applied to other problems.
• Nitish Korula and his coauthors (1) study a variant where the constraint is on the number of allocations (not on the budget) per advertiser and show an online 1-1/e algorithm (under a free disposal assumption). Nitish's followup work shows that such primal-dual algorithms have other desirable properties including fairness, an issue I suspect will get explored more in the future.

Taken together, the triptych of these results show TCS researchers know how to dig deep and get important insights.