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$ &lt;- {$a_1$}
$a_2$ &lt;- {$a_1, a_2$}
$a_1$ &lt;- {$a_1, a_3$}
$a_2$ &lt;- {$a_2$}
$a_2$ &lt;- {$a_2$}
$a_2$ &lt;- {$a_2$}
$a_1$ &lt;- {$a_1, a_2, a_3$}
$a_3$ &lt;- {$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$ &lt;- {$a_1$}
$a_2$ &lt;- {$a_1, a_2$}
$a_3$ &lt;- {$a_1, a_3$} (changed)
$a_2$ &lt;- {$a_2$}
$a_2$ &lt;- {$a_2$}
$a_2$ &lt;- {$a_2$}
$a_1$ &lt;- {$a_1, a_2, a_3$}
$a_3$ &lt;- {$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$ &lt;- {$a_1$}
$a_1$ &lt;- {$a_1, a_2$} (changed)
$a_3$ &lt;- {$a_1, a_3$}
$a_2$ &lt;- {$a_2$}
$a_2$ &lt;- {$a_2$}
$a_2$ &lt;- {$a_2$}
$a_1: 0.5, a_3: 0.5$ &lt;- {$a_1, a_2, a_3$} (changed)
$a_3$ &lt;- {$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.