Calculation of the shareholding of company shareholders

Question

I have a graph containing two types of nodes: companies and individuals.

Node has a list of ribs that represent shareholders. A shareholder has a percentage of shares and is either a Company or a Person. The face of a node is always a leaf.

Here is an example:

CompanyA has 50% of CompanyB shares UserA has 50% of CompanyA shares UserB has 50% of CompanyB shares CompanyB has 50% of CompanyA shares 

Arrows can be canceled, depending on whether they represent stocks or owners

Who in truth owns CompanyA and with what percentage. In this example, we should get that UserA owns 66.66% of CompanyA, and UserB owns 33.33% of CompanyB.

This can be calculated using the transition matrix and multiply it several times, like this .

Unfortunately, this is an estimate and requires quite a lot of iterations to get very accurate. I suspect there is a way to get an accurate answer. I looked at the eigenvalues, but I think my mathematicians are failing. Regarding matrices, I think I'm looking for a stable distribution of the transition matrix (or Markov chain).

Maybe I'm too offended? I feel that there must be a way to get this result without matrix resolution and using a recursive algorithm. Especially considering that the chart contains many leaves and that I am only interested in the shareholders of one company (the "root" of the chart).

I will implement the final solution in Java. Use of third-party libraries is possible.

Thanks!

Answer 1

I assume that marking your matrix is ​​more or less similar to

  cA cB uA uB cA 0 0.5 0.5 0 cB 0.5 0 0 0.5 uA 0 0 1 0 uB 0 0 0 1 

where cA / B stands for A / B, while uA / B stands for A / B user.

Denote this matrix by A Then the expression (1, 0, 0, 0).A gives us a direct "distribution of resources" after "investing" 1 "units" in company A. In this case, the result is valid (0, 0.5, 0.5, 0) , i.e. . Company B receives 50%, and user A receives 50%. However, the resources attributed to company B are “distributed” further, therefore, to find an “equilibrium” distribution, we need to calculate

 (1, 0, 0, 0).A^n 

in the limit n going to infinity. In terms of left eigenvectors, the original matrix A can be rewritten (assuming that it is diagonalizable) as A=Inverse[P].wP , where w is a diagonal matrix containing eigenvalues. Then we have

 A^n = (Inverse[P].wP)^n = Inverse[P].w^nP 

In this particular case, the eigenvalues ​​are 1, 1, 0.5, -0.5 , therefore, when n goes to infinity, only the eigenvalue 1 survives. Thus, the limit w^n is equal to DiagonalMatrix[{1,1,0,0}] . Therefore, the final result can be written as

 Inverse[P].DiagonalMatrix[{1,1,0,0}].P 

what gives

 0. 0. 0.666667 0.333333 0. 0. 0.333333 0.666667 0. 0. 1. 0. 0. 0. 0. 1. 

Finally, the eigenvectors corresponding to the eigenvalue 1 are (0, 0, 1, 0) and (0, 0, 0, 1) . The meaning of this is that if you "invest" 1 unit of resources in a user A / V, the corresponding user "holds everything" and nothing extends further, i.e. Equilibrium has already been reached. The eigenvalue then degenerates twice, since there are two Users (leaves).