Online matching with concave returns
Nikhil R. Devanur, Kamal Kishore Jain · 2012
We consider a significant generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable. The problem considers a sequence of items arriving online that have to be allocated to agents, with different agents bidding different amounts. The objective function is the sum, over each agent i, of a monotonically non-decreasing concave function Mi : R+ -> R+ of the total amount allocated to i. All variants of online matching problems (including the Adwords problem) studied in the literature consider the special case of budgeted linear functions, that is, functions of the form Mi(ui) = min {ui,Bi} for some constant Bi. The distinguishing feature of this paper is in allowing arbitrary concave returns. The main result of this paper is that for each concave function M, there exists a constant F(M) ≤ 1 such that: there exists an algorithm with competitive ratio of miniF(Mi), independent of the sequence of items. No algorithm has a competitive ratio larger than F(M) over all instances with Mi= M for all i.