A favorite puzzle of mine: There are n people and k goods. The goods can be arbitrarily split (let's imagine they're different raw metals, for example). Your task is to split them among those n people so that everyone feels (s)he got a fair share (at least 1/n of the total value). The problem is, each person values different goods differently.
Bonus: If you split the goods so that everyone is happy, you can keep whatever is left as a reward. Maximize your reward assuming you value all goods equally.
The input: A n × k matrix V of positive rational numbers saying how each person values each good. The sum of each row is 1, meaning that each person gives the total value of 1 to all the goods combined. (This is a simplification that doesn't affect the problem, we can always normalize each person's valuations this way.)
The output: A k x n matrix S of non-negative rational numbers (or real, if you need) saying what share of each good each person gets. The matrix S must satisfy:
- The sum in each of its
krows must be <= 1 (meaning you cannot give away more of each good than you have). - The (matrix) product V S is a
n x nmatrix. Its value at(i,j)says how personivaluesj-th person's share. So, in order for a personito be happy the number at(i,i)must be >= 1/n. - The sum of all the values in S is the total amount of goods spent. You can keep the rest, so minimize this number.
