1
$\begingroup$

I have following inputs:

  1. $X$, where each $x_j$ is float and $1 \le j \le n$
  2. $Y$, where each $y_j$ is int and $1 \le j \le n$
  3. $a$ is a float scalar

I want to allocate/split $a$ in $n$ parts towards each $x_j$ in $X$ where $1 \le j \le n$. The allocation from $a$ should be proportional to both $X$ and $Y$ (see example below to understand what I mean by proportional).
The inputs are $X, Y, a$ and output is $\{x_{1,a}$, $x_{2,a}$, .. $x_{n,a}\}$ which represent amount allocated from $a$ to $x_1$ ... $x_n$, i.e., $x_{1, a} + x_{2, a} ... + x_{n, a} = a$.
Also, $0 \le x_{j,a} \le x_j$.

Could someone propose optimal allocation algorithm in such a scenario.
The optimal/proportional allocation that I am trying to achieve is as follows:

$get\_optimal\_alloc(X, Y, a):$

  1. $Z = \frac{X}{Y}$
  2. $k = min(Y)$
  3. If $(a \le k \sum{(Z)})$:
    return $a(\frac{Z}{\sum{(Z)}})$
  4. else:
    $X[Y==k] = 0$ (i.e., X[i] = 0 for all i, where Y[i] = k)
    return $(k(Z) + get\_optimal\_alloc(X, Y, a - (k \sum{(Z)})))$

Example
I started a single fundraiser for two causes which require $1K and $20 in 1000 days and 2 days respectively (here $n=2$).
$X$ = [$1000, $20]
$Y$ = [1000 days, 2 days]

Now I randomly start receiving many donations of which first one is $a$ which I have to allocate to these causes as soon as I receive it (once allocation is made its final). I have to carry out allocation in such a way that I show progress for both the causes and also take into account the fact that one cause is due sooner. Filling the $20 cause first is not right because if there are many such small causes that keeps getting added to $X$ and if future $a$ are always smaller than these short-term causes, we will not show progress towards big goal. And ultimately as we approach end time for the big cause it would be too late to fill it.
So I was thinking in terms of allocating $a$ proportional to the rate of fill, i.e., $1000/1000 = $1 per day and $10 per day respectively. But doing so doesn’t seem straightforward.
Lets say I receive first donation $a_1$ = $33 and I allocate it in the ratio of 1:10 - this would overfill second cause.
Using above steps the allocation/output in this case should result in one recursive call to give following output:

$$[\\\$2, \\\$20] + [\\\$11, 0] = [\\\$13, \\\$20]$$

One can think of opposite scenario where near dated cause is high value than far dated cause.

$\endgroup$
5
  • 1
    $\begingroup$ Sorry, I don't understand the task. I don't know what it means to allocate an amount to update each x_i. I don't know what it means for an allocation to be proportional. What's the context where you encountered this task? Can you credit the original source? What's the motivation or context? What are the inputs to the algorithm, what outputs are you hoping it will produce, and what conditions must hold for the outputs to count as correct? $\endgroup$
    – D.W.
    Jan 9 at 4:03
  • $\begingroup$ @D.W. thanks for your response. I have added a real life example now. Please let me know if you have any questions. $\endgroup$
    – Gerry
    Jan 9 at 9:58
  • $\begingroup$ What is the definition of "optimal"? What objective function are you trying to maximize? I see that you want to find $x_{1,a},\dots,x_{n,a}$, but the only requirement on these values is that they must sum to $a$ and $x_{j,a} \le x_j$. It appears that $Y$ is irrelevant as there are no constraints that mention $Y$. An example is not a substitute for a clear specification of the problem, and in any case, I can't find the answers in the example, either. Can you formulate this mathematically? I don't understand what you mean by "each $a$". It appears there is only one $a$. $\endgroup$
    – D.W.
    Jan 9 at 21:40
  • $\begingroup$ @D.W. fixed the typo ~each~ $a$ and tried to define my "optimal" algo using $X$ and $Y$ meeting all the criteria. Thanks for helping me think through. Does this algo look optimal to you - both computationally and behaviourally for given use-case that is explained in the example? $\endgroup$
    – Gerry
    Jan 10 at 1:55
  • $\begingroup$ OK. Thanks for editing. Now what is your question? We are a question-and-answer site, so we require you to articulate a specific question in your post. I don't know whether the algorithm you propose is optimal. Presumably that will depend on what criteria for optimality you have (e.g., what objective function you are trying to maximize), which isn't specified in the question. $\endgroup$
    – D.W.
    Jan 10 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.