37 views

Skip to first unread message

Jun 27, 2024, 3:30:10 AMJun 27

to hle...@googlegroups.com

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.

Jun 27, 2024, 5:04:56 AMJun 27

to hle...@googlegroups.com

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

> 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

> 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.

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

Jun 27, 2024, 5:18:33 AMJun 27

to hle...@googlegroups.com

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.

16000€, that is, these are internal expenses of Production A and internal

income of the IT department, and so on.

Jun 27, 2024, 5:27:43 AMJun 27

to hle...@googlegroups.com

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" ?

Production A: 100000 €

Production B: 90000 €

IT: -50000 €

Human Resources: -120000 €

ProdA ProdB IT HR

IT 16000 4000 8000 12000

Salary 10000 30000 40000 20000

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" ?

Jun 27, 2024, 5:30:39 AMJun 27

to hle...@googlegroups.com

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

Jun 27, 2024, 5:32:15 AMJun 27

to hle...@googlegroups.com

On Thu, 27 Jun 2024, Simon Michael wrote:

I have invented those absolute numbers to make up an example. However,

eventually only the relative numbers are used.

Jun 27, 2024, 6:24:49 AMJun 27

to hle...@googlegroups.com

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.
> just trying to follow the train of thought.)

Even for me.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu