Speaker: Nikhil Devanur

Affiliation: Microsoft Research(Redmond)

Abstract: We consider a generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable for this problem. 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$, a monotonically non-decreasing concave function $M_i : \Real_+ \rightarrow \Real_+$ 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 $M_i( u_i) = \min \{u_i,B_i\}$ for some constant $B_i$. The distinguishing feature here 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) \leq 1$ such that - there exists an algorithm with competitive ratio of $\min_i\{ F(M_i) \}$, independent of the sequence of items. - No algorithm has a competitive ratio larger than $F(M)$ over all instances with $M_i= M$ for all $i$. Our algorithm is based on the primal-dual paradigm and makes use of convex programming duality. The upper bounds are obtained by formulating the task of finding the right counterexample as an optimization problem. This path takes us through the calculus of variations which deals with optimizing over continuous functions. The algorithm and the upper bound are related to each other via a set of differential equations, which points to a certain kind of duality between them.

Joint work with Kamal Jain