  We study a resource allocation problem over time, where a finite (random)
resource needs to be distributed among a set of users at each time instant.
Shortfalls in the resource allocated result in user dissatisfaction, which we
model as an increasing function of the long-term average shortfall for each
user. In many scenarios such as wireless multimedia streaming, renewable energy
grid, or supply chain logistics, a natural choice for this cost function turns
out to be concave, rather than usual convex cost functions. We consider
minimizing the (normalized) cumulative cost across users. Depending on whether
users' mean consumption rates are known or unknown, this problem can be reduced
to two different structured non-convex problems. The "known" case is a concave
minimization problem subject to a linear constraint. By exploiting a
well-chosen linearization of the cost functions, we solve this provably within
$\mathcal{O}\left(\frac{1}{m}\right)$ of the optimum, in $\mathcal{O}\left(m
\log{m}\right)$ time, where $m$ is the number of users in the system. In the
"unknown" case, we are faced with minimizing the sum of functions that are
concave on part of the domain and convex on the rest, subject to a linear
constraint. We present a provably exact algorithm when the cost functions and
prior distributions on mean consumption are the same across all users.
