Google Answers Logo
View Question
Q: Allocating contributions to variables to reach target ratios ( Answered 5 out of 5 stars,   1 Comment )
Subject: Allocating contributions to variables to reach target ratios
Category: Science > Math
Asked by: yumbrad-ga
List Price: $10.00
Posted: 12 Nov 2004 13:07 PST
Expires: 12 Dec 2004 13:07 PST
Question ID: 428135
I would like a formula that does the following:

10 variables a-j with defined initial values
10 target percentages mapped to a-j

I want to incrementally get and keep a-j at their target percentages
of the sum of a-j. The inital values of a-j are quite off from their
target percentages of the total, and each addition will be too small
to resolve the difference, though with enough additions the target
percentages will be reached. Say the sum is 150, and I want to
distribute 20 more among a-j, using the values of a-j and their target
percentages, which should receive how much of the 20? All could go to
a, or it could be distributed equally among them, etc... The solution
should be the one that converges on the target percents most rapidly,
and should keep spitting out the right way to distribute once the
target percentages are reached (which would be increment*a_target_pct
for a, increment*b_target_pct for b, etc..). Also, the answer
shouldn't be tied to having 10 variables, it should be easily applied
to other numbers of variables.

This wasn't as easy as I thought it would be, so please no sub-optimal
answers, I have one of those.  I'll give a nice tip if the answer
comes as pseudo code :)

Request for Question Clarification by mathtalk-ga on 12 Nov 2004 20:27 PST
Hi, yumbrad-ga:

Do the target percentages remain constant?  Or are they "a moving
target" along with the changing totals?

regards, mathtalk-ga

Clarification of Question by yumbrad-ga on 14 Nov 2004 16:35 PST
Good questions, I see how there are many valid solutions.. It can be
assumed that %'s are never zero. And in theory, the %'s could change.
With a given increment, the most preferable solution would be the one
that minimizes the maximum relative error among the variables after
allocating the addition among them. Relative in that the error for
each variable is (a_current - a_target)/a_target. If one solution
eliminated the error for one variable (the variable's value becomes
the correct target % of total of all variables), and left another 25%
off of it's target, a preferable solution would leave both variables
12.5% off of their respective targets, assuming that was possible.

Request for Question Clarification by mathtalk-ga on 14 Nov 2004 19:45 PST
Given this "maximum relative error" criterion, we can describe the
optimal strategy in advance of knowing what increments to the total
will become available.

However we should make the observation that nothing can be done
"directly" to improve excess allocations, even if these should be
considered the "maximum" among relative errors.  The variables which
are currently above their target percentages can only be mitigated by
incremental allocations to the remaining variables below their
targets, which by dilution has the ultimate effect of lowering those
overallocations to the assigned targets.

So the strategy I propose would prioritize allocations only among
those variables which are below their targets, but according to the
"maximum relative error" you've chosen.

regards, mathtalk-ga

Request for Question Clarification by mathtalk-ga on 17 Nov 2004 05:28 PST
Perhaps a brief example will help you to assess my proposed solution,
before I post it as an "Answer".

Consider allocations a_1 = 1, a_2 = 2, a_3 = 3 with target fractions
equal to one third for each.

Using the "maximum relative error" criterion we would add the first
unit of additional allocations to a_1, so that:

a'_1 = 2, a'_2 = 2, a'_3 = 3

Note that while initially a_2 was right at the target fraction of 1/3,
a'_2 actually moved downward from that point.  Here a'_1 and a'_2 are
both below the target ratios, ie. at 2/7 < 1/3.

The next two units of additional allocations would be equally divided
between these two, until we reach the target ratios:

a"_1 = 3, a"_2 = 3, a"_3 = 3

Ever after additional allocations would be be equally divided among all three.

My answer would consist of the general "recipe" (however many targets,
not necessarily equal ratios) and a more general example.

regards, mathtalk-ga

Clarification of Question by yumbrad-ga on 17 Nov 2004 10:18 PST
That is what I had in mind, I understand that dilution may take a
while to bring some out of whack overallocated variable down, I just
wanted to ensure that the variables that *could* be adjusted were done
so so as to minimize their maximum error. But about overallocated
variables.. Will your solution spit out zero allocation to an
overallocated variable if the increment cannot bring all variables to
their targets, but with the same initial values and a increment large
enough to bring all variables to their exact targets, allocate the
increment appropriately to do so? Actually, I suppose that's pretty
easy, it's the optimizing error among variables being adjusted I'm not
sure I could easily figure out. Anyway, sounds like you understand
what I'm looking for, and anticipated the dilution limitation that I
didn't mention. I do in fact want to let dilution take its course, as
variables can only be incremented, not decremented.
Subject: Re: Allocating contributions to variables to reach target ratios
Answered By: mathtalk-ga on 17 Nov 2004 21:25 PST
Rated:5 out of 5 stars
Hi, yumbrad-ga:

Suppose a "portfolio" is defined by initial nonnegative allocations
a_1,...,a_n to n asset classes, some or all of which can be zero. 
Each asset class has a corresponding "relative participation" target
r_i > 0.  The goal is to increment these allocations using funds that
become available in some piecemeal fashion in an "optimal" way.

The construction below is optimal in two senses.  First, it minimizes
the maximum relative "deficiency" of allocations with respect to their
respective participation targets at each step along the way to
reaching the exact targets.  Second, it minimizes the overall amount
of additional allocations used to reach the exact targets.

*  *  *  *  *  *  *  *  *  *  *  *

For each asset class i, define the normalized allocation z_i =
a_i/r_i.  [Note: We can arrange without loss of generality that SUM
r_i = 1, but this would not simplify the following account enough to
be worth insisting upon.  It would make a step in the proof of
optimality easier, so we may return to this point at a later time.]

The set {z_i : i = 1,..,n } contains s distinct values:

  t_1 < t_2 < ... < t_s

where s is at least 1 and at most n.

Let I_1 U I_2 U ... U I_s be the natural partition of asset classes
{1,..,n} such that I_k = { i : z_i = t_k }, ie. indexes that
correspond to the same normalized allocation.

Although the additional allocations are expected to become available
in unpredictable fashion, their scheduling can be conceptually divided
into s phases.  In all but the last of these phases, there is a limit
to the overall amount of additional allocation possible before one
advance to the next phase.

In the first phase we only add to allocations for asset classes in
I_1, and these allocations are made proportionally to their relative
participation targets r_i.  At the end of the first phase all of the
normalized allocations z_i from I_1 will have risen to equal those
from I_2, ie. from t_1 to t_2.

In the second phase allocations are added across I_1 U I_2, and again
these increments are assigned proportionally to the respective r_i
targets.  At the end of the second phase the normalized allocations
will haver risen from t_2 to t_3, ie. so as to match those already
attained in I_3.

Continuing in this fashion, phase s begins when all the normalized
allocations have been raised to a common value t_s.  The targets are
exactly attained at this point, and any further incremental
allocations are made proportionally to all asset classes according to
relative participation targets r_i.  As a result the relative
participation targets are preserved.

*  *  *  *  *  *  *  *  *  *  *  *

The earlier example can now be made more complicated.  Suppose that
for the three initial allocations a_1 = 1, a_2 = 2, a_3 = 3 we set
unequal targets:

  r_1 = 1/2, r_2 = 1/3, r_3 = 1/6

The normalized allocations are then:

  z_1 = 2, z_2 = 6, z_3 = 18

In this case the normalized allocations are all distinct, and thus we
have three phases.  In the first phase allocations are added to a_1
until the revised normalized allocation reaches 6:

  a'_1/r_1 = 6  ==>  a'_1 = 3

We must increase a_1 = 1 to a'_1 = 3, an incremental allocation of 2.

In the next phase both of the first two asset classes will receive
extra allocations, and for every r_1 = 1/2 that is added to a'_1 = 3,
we'll add r_2 = 1/3 to a'_2 = a_2 = 2.  This continues until the
normalized allocations for both (which rise together, remaining equal)
become z_3 = 18.  Therefore:

  a"_1/r_1 = 18  ==>  a"_1 = 9

and because we've incremented a'_1 by 9 - 3 = 6 = 12*(1/2), we must
also increment a'_2 = a_2 = 2 by 12*(1/3) = 4.  Thus a"_2 = 2 + 4 = 6.

We have reached the beginning of the third phase, and the
participation targets have been attained:

  a"_ 1 = 9, a"_2 = 6, a"_3 = 3

The total amount added is 12, which turns out to be the least amount
necessary to reach the prescribed participation targets.

*  *  *  *  *  *  *  *  *  *  *  *

We now give some additional formulas that arise in connection with
this schedule of allocation increases.  The overall amount added in
phase k, k < s, is:

  D_k = (z_{k+1} - z_k) * SUM r_i

where the sum is taken over S_k = I_1 U ... U I_k.

The specific amount added to asset class i during phase k is:

  (z_{k+1} - z_k) * r_i

if i belongs to S_k, and zero otherwise.

It can be shown that SUM D_k for k = 1,..,s-1 is the minimum overall
increment which allows all allocations to reach their prescribed
targets.  Details available on request.

regards, mathtalk-ga
yumbrad-ga rated this answer:5 out of 5 stars and gave an additional tip of: $2.00
Just what I had in mind. Some of that stirred memories from college
days but I'm sure it's quite fresh in your mind; it would have taken
me a long time...  Thanks!

Subject: Re: Allocating contributions to variables to reach target ratios
From: mathtalk-ga on 13 Nov 2004 13:49 PST
If some target percentages are allowed to be zero, then it's possible
for the target never to be reached.

Let's take a simple example with just two variables a_0 and a_1. 
Suppose we start with a_0 = 0 and a_1 = 1, and the target for a_1 is

No matter how much is added to a_0, the percentage for a_1 can never reach 0%.

The general problem is one of "control", and the optimal solution will
depend on the choice of a criterion for judging what approximation to
the target percentages (among those which are feasible) is best.

Assuming that no target percentage is zero for any nonzero starting
value of an a_j, then we can readily compute the minimum increase in
the total needed to achieve the exact targets.  This increase is
presumably attained over several intermediate increases, rather than
all at once.  Therefore the alternatives are informed by what would
make one set of intermediate percentages achieved preferable.

regards, mathtalk-ga

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy