# Splitting goods among people so that everyone feels happy

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:

1. The sum in each of its `k` rows must be <= 1 (meaning you cannot give away more of each good than you have).
2. The (matrix) product V S is a `n x n` matrix. Its value at `(i,j)` says how person `i` values `j`-th person's share. So, in order for a person `i` to be happy the number at `(i,i)` must be >= 1/n.
3. The sum of all the values in S is the total amount of goods spent. You can keep the rest, so minimize this number.
-
Why not formulate this as a linear programming problem and use a std solver, or simplex algorithm to solve? Forbidding partititioning items (making you give whole items instead of fractional) makes this more interesting (and NP-complete, as opposed to the original P-complete problem). – gt6989b Sep 6 '12 at 21:40
does using excel solver count? superuser.com/questions/467577/… – Sean Cheshire Sep 7 '12 at 20:05