Online Resource Allocation with Concave, Diminishing-Returns Objectives

Online resource allocation problems are central challenges in economics and computer science, modeling situations in which \(n\) items arriving one at a time must each be immediately allocated among agents. In such problems, our objective is to maximize a monotone reward function \(f(x)\) over the allocation vector \(x = (x_{ij})_{i,j}\), which describes the amount of each item given to each agent. In settings where \(f\) is concave and has “diminishing returns” (monotone decreasing gradient), several lines of work over the past two decades have had great success designing constant-competitive algorithms, including the foundational work of Mehta et al. (2005) on the Adwords problem and many follow-ups. Notably, via a greedy algorithm \(\frac{1}{2}\)-competitive in such settings, these works have shown that one can often obtain a competitive ratio of \(1 - \frac{1}{e} \approx 0.632\) in a variety of settings when items are divisible (i.e., allowing fractional allocations). However, prior works have thus far used a variety of problem-specific techniques, leaving open the general question: Does a \((1 - \frac{1}{e})\)-competitive fractional algorithm always exist for online resource allocation problems with concave, diminishing-returns objectives?