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?