Computing a company's shareholders ownership percentage

Question

I have a graph that contains two types of nodes: Companies and Persons.

A Company node has a list of edges that represent Shareholders. A Shareholder has a percentage of shares and is either a Company or a Person. A Person node is always a leaf.

Here's an example:

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

The arrows could be reversed, depending on whether they represent shares 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 computed using a Transition Matrix and multiplying it by itself multiple times, like this.

Sadly, this is an estimate and requires quite a lot of iterations to get a very precise one. I suspect that there's a way to get a exact answer. I've looked at eigenvalues but I think my maths are failing me. In terms of matrices, I think I'm looking for the stable distribution of a transition matrix (or Markov Chain).

Perhaps I'm overcomplicating this? I feel like there should be a way to get this result without resolving to matrices and with a recursive algorithm. Especially considering that the graph contains a lot of leaves and that I am only interested in the shareholders of a single company (the "root" of the graph).

I will implement the final solution in Java. Third party libraries can be used.

Thanks!

Answer 1

I assume that the labeling of your matrix is more or less like so

   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 denotes Company A/B while uA/B stands for User A/B.

Let's denote this matrix as A. Then the expression (1, 0, 0, 0).A gives us the immediate "distribution of resources" after "investing" 1 "unit" into Company A. In this case the result is indeed (0, 0.5, 0.5, 0), i.e., Company B gets 50% and User A gets 50% as well. However, the resources attributed to Company B "propagate" further, so in order to find the "equilibrium" distribution, we need to calculate

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

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

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

In this particular case, the eigenvalues are 1, 1, 0.5, -0.5 so when n goes to infinity, only the eigenvalue 1 survive(s). Thus the limit of w^n is DiagonalMatrix[{1,1,0,0}]. The final result can be therefore written as

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

which yields

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 one "invests" 1 unit of resources into User A/B, the corresponding user "keeps everything" and nothing propagates further, i.e., an equilibrium has been already reached. The eigenvalue is then doubly degenerate since there are two Users (leaves).