Economic Allocation

[Henning Thielemann]

The following post is off-topic, but it is about finance, but not hledger,
but about a Haskell solution. Hopefully people find it useful.

A friend of mine explained the following problem to me. He called it
"allocation". He also had an adhoc solution. I wondered what mathematical
problem he actually solved and whether his solution is universally correct
and works always.

Think of a company with four departments with the following balances
(quarterly, monthly, weekly, daily, as you like):
Production A: 100000 €
Production B: 90000 €
IT: -50000 €
Human Resources: -120000 €

Looking only at these numbers it seems like Production A and B are the two
departments that keep the business running and IT and HR should be shut
down as quickly as possible, because they have only expenses but generate
no revenue.

Of course, that's not true. IT and HR provide resources for the two
Production departments, that are essential for their operation. At least,
this is the way it should be. :-) So let's look at the full picture. Each
department, including IT and HR, use resources provided by IT and HR. This
yields a matrix like this one:

ProdA ProdB IT HR
IT 16000 4000 8000 12000
Salary 10000 30000 40000 20000

Only the relative numbers are of interest, so each row is normalized to a
sum of 1:

ProdA ProdB IT HR
IT 0.4 0.1 0.2 0.3
Salary 0.1 0.3 0.4 0.2

Now the question is, given these numbers, what sums do the departments
really gross. The idea is, that IT and HR should be neutral, that is,
eventually their balance should be zero. To achieve this, my friend
implemented the following iterative solution: He sets IT to balance zero,
but distributes its balance according to the IT expense distribution. I.e.
in the beginning we have IT balance -50000 €. It is distributed this way:

ProdA ProdB IT HR
-20000 -5000 -10000 -15000

and then added to the initial balance vector
80000 85000 -10000 -135000

As you can see, IT is not cancelled out, but it is closer to zero than
before. Additionally, HR now generates even more loss than before. So the
next step is to distribute HR's loss to all departments using the relative
Salary vector:

ProdA ProdB IT HR
-13500 -40500 -54000 -27000

and added to the last iterated balance vector:
66500 44500 -64000 -27000

I think you got it. The iteration now alternates between spreading IT and
HR losses and converges to:

10962 9038 0 0


My question was: What does this iteration actually compute, does it always
succeed, is it order-independent?

I found that the iteration is the method of successive displacement, also
known as Gauss-Seidel method, for the following mathematical problem:


Transpose the matrix of relative expenses and split it into the square
matrix K (for "costs") and the remaining matrix P (for "production").

/0.4 0.1\
/P\ = |0.1 0.3|
\K/ |0.2 0.4|
\0.3 0.2/

If you perform two iteration steps at once (Jacobi instead of
Gauss-Seidel), this is equivalent to multiplication with the block matrix:

/I P\
\ K/

What is result of performing the iteration infinitely often? We can
express the effective operation as matrix and give it the name:

/I Plim\
\ Klim/

It holds:

/I Plim\ . /I P\ = /I Plim\
\ Klim/ \ K/ \ Klim/

But even more, Klim shall vanish, that is:

/I Plim\ . /I P\ = /I Plim\
\ / \ K/ \ /

This yields four matrix equations, one for each block of the right-hand
side. But only one equation is non-trivial:

P + Plim·K = Plim

This leads us to the solution:

P = Plim·(I-K)
Plim = P·(I-K)^-1

This means, given the start vector (x0|y0)^T of balances, we get:

xlim = x0 + Plim·y0
= x0 + P·(I-K)^-1·y0
ylim = 0

That's the explicit solution.



My question to you is: Is this a known problem in economic science and
what is its name? Is "allocation" an established term?


Here is a demonstration of the iterative and explicit solver in Haskell
using LAPACK:
https://hackage.haskell.org/package/lapack-0.5.2/docs/src/Numeric.LAPACK.Example.EconomicAllocation.html

Attached is a LibreOffice Spreadsheet ODS demonstrating the iterative and
direct solver.

[Simon Michael]

G'day Henning,

> Of course, that's not true. IT and HR provide resources for the two
> Production departments, that are essential for their operation. At least,
> this is the way it should be. :-) So let's look at the full picture. Each
> department, including IT and HR, use resources provided by IT and HR. This
> yields a matrix like this one:
>
> ProdA ProdB IT HR
> IT 16000 4000 8000 12000
> Salary 10000 30000 40000 20000

This was too big a jump for me, I didn't understand these numbers exactly.

> My question to you is: Is this a known problem in economic science and
> what is its name? Is "allocation" an established term?
>
>
> Here is a demonstration of the iterative and explicit solver in Haskell
> using LAPACK:
> https://hackage.haskell.org/package/lapack-0.5.2/docs/src/Numeric.LAPACK.Example.EconomicAllocation.html
>
> Attached is a LibreOffice Spreadsheet ODS demonstrating the iterative and
> direct solver.

Interesting post, thanks!

The first thing that comes to mind is, if you don't get much response here, the APL/J/K folks would know (eg in their matrix rooms, I assume they have mail lists also).

Best

[Henning Thielemann]

On Thu, 27 Jun 2024, Simon Michael wrote:

> G'day Henning,
>
>> Of course, that's not true. IT and HR provide resources for the two
>> Production departments, that are essential for their operation. At least,
>> this is the way it should be. :-) So let's look at the full picture. Each
>> department, including IT and HR, use resources provided by IT and HR. This
>> yields a matrix like this one:
>>
>> ProdA ProdB IT HR
>> IT 16000 4000 8000 12000
>> Salary 10000 30000 40000 20000
>
> This was too big a jump for me, I didn't understand these numbers exactly.

It means, that Production A department has expenses on IT equipment at
16000€, that is, these are internal expenses of Production A and internal
income of the IT department, and so on.

[Simon Michael]

I didn't see the relationship of table 1:

Production A: 100000 €
Production B: 90000 €
IT: -50000 €
Human Resources: -120000 €

with table 2:

ProdA ProdB IT HR
IT 16000 4000 8000 12000
Salary 10000 30000 40000 20000

But maybe they're just separate examples.

Is table 2 saying "16000 of the total IT cost supported ProdA, 4000 supported ProdB, 8000 was internal for IT's own needs, 12000 supported HR" ?

[Simon Michael]

(I realise these mundane details are not what you're interested in, I'm just trying to follow the train of thought.)

[Henning Thielemann]

On Thu, 27 Jun 2024, Simon Michael wrote:

exactly

I have invented those absolute numbers to make up an example. However,
eventually only the relative numbers are used.

[Henning Thielemann]

On Thu, 27 Jun 2024, Simon Michael wrote:

> (I realise these mundane details are not what you're interested in, I'm
> just trying to follow the train of thought.)

I am happy about anything I can do to make the problem comprehensible.
Even for me.