Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values [-10,10]
, the only value that may repeat for a given person (i.e., within a given column) is 0
. All the other ranking values must be used exactly once in each column. Therefore, the sum of the data in every column is 0, because -10 cancels out 10, -9 cancels out 9, etc. Additionally, every column has 20 values which are nonzero and 80 values which are zero. Any number of duplicates across any given row are possible.
The goal is to determine, for each row, which person (i.e., which column) "wins" that object. The goal is to dole out the objects to the people such that the sum of that person's rankings for the objects they won is equal (or as close to equal as possible) for all five people.
As a trivial example, if we only had 5 rows instead of 100, and ranking values [-2,2]
:
Person | A | B | C | D | E Obj1 | -2 | -1 | -1 | 0 | 1 Obj2 | 0 | 0 | 1 | 2 | 2 Obj3 | -1 | -2 | 2 | 1 | -1 Obj4 | 2 | 2 | -2 | -1 | 0 Obj5 | 1 | 1 | 0 | -2 | -2
Obviously there aren't enough rows here to allow for duplicates, but that's not important.
Additionally, as a constraint, each person must end up with the same number of objects. So in our example, each person would get one of the five objects, and the sum of the rankings assigned to each person would be as close to equal as possible. We can assume that the number of objects will be divisible evenly into the number of people, so with 5 people it'd be 5, 10, or 15 objects, and so on.
Just from "eyeballing" the solution to this problem, I would assign Obj1 to E, Obj2 to C, Obj3 to D, Obj4 to B, and Obj5 to A. This may not be the best solution, but it gives a score total of 1 to everyone except B, who gets a score of 2. In our case, there's no way to give a score of 1 to everyone, nor a score of 2 to everyone, because Obj1 doesn't have any 2s and Obj4 doesn't have any 1s. This is a possibility we have to anticipate.
Also, in my original formulation of the problem as a 100x5, there are going to be quite a few rows where the values are [0,0,0,0,0]
-- zeroes all the way across. For these, assigning them randomly or arbitrarily to people is acceptable.
I think this is a linear programming problem, but I can't quite wrap my head around how to set it up so that I can solve it in e.g. GNU Octave's glpk plugin. How can I determine what my objective function is? How do I know my constraints? I'm pretty sure it's a maximization problem, but it's currently formulated in a way that I can't just enter the matrix as-is as constraints into an LP solver.