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 person
j-th person's share. So, in order for a person
ito 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.