Finding inputs for equal outputs in monotonically decreasing functions

Question

I have $n$ functions, $f_1,\dots,f_n$. Across these, I want to allocate a known amount $I$ so that $i_1 + i_2 + \dots + i_n = I$ and $f_1(i_1) ≈ f_2(i_2) ≈ \dots ≈ f_n(i_n)$ (equal up to a certain precision). The only information available about the functions is that they are monotonically decreasing.

Which methods are available to find $i_1, i_2, \dots, i_n$?

• D.W.: Can you clarify what "equal up to a certain precision" means? Is this relative error or absolute error? Do you require approximate equality between every pair, or only consecutive pairs?
• D.W.: What is the domain for $i_1,\dots,i_n$? Are they required to be non-negative integers? Arbitrary integers? Something else?
• D.W.: How are the functions specified? As a truth table? What is the best algorithm you know for this problem? What is the context where you encountered it or the motivation?
• codeR: Do the functions evaluate to almost equal values in pair-wise fashion or just in the specified order? Suppose you ensure $|f_k(i_k) - f_{k+1}(i_{k+1})| \le \epsilon$ then $f_1(i_1)$ can be equal to $f_n(i_n) + n\epsilon$.

Answer 1

You can do it in $O(n \log(1/\delta) \log(|I|))$ where $\delta$ is your desired precision and $|I|$ is the size of the domain of $I$ if discretized.

Suppose you arbitrarily choose $i_1 = x$. Then you compute $f_1(i_1)$ and from that you can compute $i_k$ for all 2ドル \leq k \leq n$ by using a binary search to find $|f_k(i_k) - x| \leq \delta$ for each $i_k$, which will take $\log(1/\delta)$ iterations as $f$ is monotonically decreasing.

Now, after that process is complete (which takes $O(n \log (1/\delta)$ iterations), you get a final $I$ value. If it is too high, you lower $x$, if it is too high you raise $x$ - again you do a binary search on the domain of $I$, which takes $\log(I)$ iterations of the above procedure to find a solution.

---

The above assumes $i_k$ is real. If it is an integer you'll have to raise your acceptable $\delta$ to whatever lets you always find a valid solution. If that isn't acceptable then the above algorithm doesn't work (and the problem is likely NP-hard in that scenario).