# Assigning items as evenly as possible

Lets say I have a finite set of items like the following:

{$a_1, a_2, ... , a_n$}

And I have a finite list of sets of these items. For example:

[{$a_1$}, {$a_1, a_2$}, {$a_1, a_2, a_3$}, {$a_1, a_3$}, {$a_2$}, {$a_2$}, {$a_2$}, {$a_3$}]

I then take one item from each set. For example, in the above case, I could do:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_1$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

In this case, the totals are:

$a_1$: 3
$a_2$: 4
$a_3$: 1

And the minimum is 1.

But lets say I want to maximise the minimum. I could instead select the items like:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_3$ <- {$a_1, a_3$} (changed)
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2
$a_2$: 4
$a_3$: 2

And the minimum is 2.

Lets say also I allow the items to be assigned in a weighted way. Like the following:

$a_1$ <- {$a_1$}
$a_1$ <- {$a_1, a_2$} (changed)
$a_3$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1: 0.5, a_3: 0.5$ <- {$a_1, a_2, a_3$} (changed)
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2.5
$a_2$: 3
$a_3$: 2.5

And the minimum is 2.5.

We can't evenly assign the items in these sets because three of them only contain {$a_2$}.

So what's a fast algorithm for doing the above, i.e. finding the maximum "minimum"? I need something exact, not an approximation.

This can be solved by standard linear programming algorithms. A set of weighted choices is described by variables $y_{ij}$, where $y_{ij}=w$ if we choose $a_i$ from the $j$th set with weight $w$. To set this up, we use an additional variable $m$ which will represent the minimum number of times any variable is selected. We then have four kinds of constraints:

• for each $i$, $j$: $0 \le y_{ij} \le 1$ if $a_i$ is in the $j$th set;
• for each $i$, $j$: $y_{ij} = 0$ if $a_i$ is not in the $j$th set;
• for each $j$: $\sum_i y_{ij}=1$ [choosing a total of 1 element from the $j$th set];
• for each $i$: $m \le \sum_j y_{ij}$ [$m$ is at most the number of chosen $a_i$'s].

We choose the $y_{ij}$'s to maximize $m$; the constraints and the objective function are linear. (In the non-weighted case, we additionally require $y_{ij}$ to be integral; this makes the problem harder but integer linear programming packages are readily available.)

This formulation has the following geometric interpretation. Identify $a_i$ with the $i$-th standard basis vector in $\mathbf{R}^n$. For each set, say $\{a_{i_0},\ldots,a_{i_k}\}$, the collection of possible weighted choices from this set is the $k$-simplex with the given $a_{i_j}$'s as vertices. The Minkowski sum of all these simplices is the convex polyhedron which contains precisely the possible vectors $(x_1,\ldots,x_n)$ of totals for the elements $a_1,\ldots,a_n$. The linear programming formulation above seeks a point in this polyhedron which is as far from as possible from the nearest coordinate hyperplane.

• I think I get this, but could you go into further detail about how how I can use my evaluation function? Isn't it non-linear? Jul 4 '13 at 8:09
• For each a_i, the number of occurrences of a_i is linear in the y_ij's. You're trying to maximize the min of these, which as you say is nonlinear, but it's not too bad -- it's the min of a finite number of linear functions. So you introduce the auxiliary variable m, and impose the (linear) constraints that m is at most the number of occurrences of each of the a_i's. When you maximize m, m is forced to be the min you were looking for.