company as none-binary tree

Question

Company's structure is depicted as none-binary tree where each node represents an employee. Root of the tree is CEO of the company and every node that has children is their supervisor.

When assigning salary there are three rules: You have a budget(is given) you cannot exceed, every employee has a k(is given) times bigger salary then the sum of salaries of his direct subordinates and every employee with the same supervisor has the same salary.

I just can't seem to figure out the formula for this, can you help me out? The solution should be applicable for every company no matter it's structure.

Answer 1

Let's try to formalize your problem. Say the companies structure is modelled as a graph $(V,E)$ and we search the salary function $s\colon V\to\mathbb R$. The three restrictions you provide then translate to

1. You have a budget $b\in\mathbb R$ that needs to be distributed: $\sum_{v\in V} s(v) = b$.
2. Every employee has a $k$ times bigger salary then the sum of salaries of his direct subordinates: $s(w) = k\cdot\sum_{v\in\mathrm{children}(w)} s(v)$.
3. Every employee with the same supervisor has the same salary: $s(v_1) = s(v_2)$ if $v_1,v_2\in\mathrm{children}(w)$ for some $w\in V$.

The important thing to note now is that restriction 1. is just normalisation and does not affect the relation between salaries of different employees. On the other hand restrictions 2. and 3. will determine this relationship uniquely, but don't provide concrete values for $s$.

Therefore let $x=s(v_0)$ where $v_0$ is the root node (CEO) of $V$. Using 2. and 3. we now get \begin{equation} x = s(v_0) = k\cdot\sum_{v\in\mathrm{children}(v_0)} s(v) = k\cdot\left|\mathrm{children(v_0)}\right|\cdot s(w) \end{equation} and thus \begin{equation} s(w) = \frac{x}{k\cdot \left|\mathrm{children}(v_0)\right|} \end{equation} for all children $w$ of $v_0$. Further iteration will yield $s(v)$ for all $v\in V$ in terms of $x$. The value $x$ can then be computed using 1.