Solution/Hardness of the following (integer) budgeted problem?

Question

I have no idea how to solve the following INTEGER problem or prove its hardness. Thanks for any help/comment/open discussion!

Assume there are $N$ startups. For each startup $i$, you can invest $x_i\in \{0,1,...,C_i\}$ dollars where $C_i$ is the maximal investment that it accepts, and you will get a reward as $f_i(x_i)$. The reward function $f_i(x_i)$ has the following properties for all $i$:

(1) $f_i(.)$ is non-decreasing and $f_i(0)=0$

(2) $f_i(.)$ is not necessarily "convex" or "concave"

(3) $0 \leq x\leq x'\leq C_i$, $f_i(x)x' \geq f_i(x')x$

(4) the function $g_i(x) = f_i(x+1) - f_i(x)$ is not necessarily non-decreasing or non-increasing.

Your total budget is $C$. By selecting an INTEGER vector $(x_1,...,x_N)$, you want to maximize the total rewards $\sum_{i=1}^Nf_i(x_i)$ subject to (1) $x_i\in \{0,1,...,C_i\}$ for any $i$ and (2)$\sum_{i=1}^N x_i \leq C$.

Answer 1

Solving this exactly this ends up being $\mathsf{NP}$-hard.

The reduction I have doesn't pay much attention to the representation of the $f_i$'s. That said, the values of $f_i$ I end up giving can be computed efficiently, so this reduction works for any "black box" use of the $f_i$'s.

I'll give the reduction in two parts. Composing the two pieces gives the whole argument.

1. Firstly I claim that condition (iii) doesn't help very much, even when combined with condition (i). In particular, there is a reduction from the problem with (iii) ignored to the original version of the problem: Suppose there is an instance with $f_i$'s that are non-decreasing but otherwise arbitrary. Then we can make a new instance (whose data is denoted with primes (')) which has

   • $f_i'(0) \gets 0$,
   • for $x \ge 1$, $f_i'(x) \gets f_i(x-1) + A$ for an unspecified large constant $A$, and
   • $C_i' \gets C_i + 1$ and $C' \gets C + N$.

   Note that if a given $f_i$ is initially non-decreasing, then so is the new $f_i'$, while the rest of condition (i) holds for $f_i'$.

   To satisfy condition (iii), it suffices to make $A$ large enough. This follows from thinking geometrically about what condition (iii) imposes on the $f_i$s. In particular, for any particular $x$, let $\ell$ be the line through the origin and $(x,f_i(x))$. The condition (iii) says that every point $x' \ge x$ must have $(x',f_i(x'))$ below $\ell$, and every point $x' \le x$ must have $(x',f_i(x'))$ above $\ell$. Thinking of increasing $A$ as pulling the origin down while fixing the rest of $f_i$, it's clear that this condition limits toward the empty constraint as $A$ increases, since the lines $\ell$ become arbitrarily steep.

   We also need to ensure this reduction is actually a reduction. We can accomplish this also by making $A$ large enough. In particular, it's easy to see that if $A$ is sufficiently large, then any optimal solution of the new instance must invest at least one unit into each startup (ie $x_i' \ge 1$ for any $x'$ optimal in the new instance). Once we have this, identifying each solution $x$ to the original instance with the solution $x'$ of the new instance defined by $x'_i \gets x_i + 1$ gives a correspondence between optimal solutions.

2. Now, if we ignore condition (iii), we can easily reduce from knapsack by making each $C_i$ the weight of item $i$, $C$ the capacity of the knapsack, and each $f_i$ "all-or-nothing" ($f_i(C_i) = C_i$ and $f_i(x) = 0$ otherwise). Then maximizing $\sum_i f_i(x_i)$ boils down to picking items that go into the knapsack. This is (in my opinion) easy to check and not the interesting part of this answer, so I won't belabor the details.

Answer 2

The representation of $f_i$ matters. If $f_i$ is given as the list of values $f_i(0),\ldots,f_i(C_i)$, then the problem is in $P$.

Let $D(k,b)$ to be the maximum value of $\sum_{i=1}^k f_{i}(x_i)$ under the constraint $\sum_{i=1}^k x_i = b$. The answer you looking for is $\max \{ D(N,b) | b\leq C\}$.

One can write a recurrence for $D(k,b)$ use idea similar to the knapsack problem. It's not difficult to get $O(NC^2)$ time.