An example scenario

Let’s say you run a summer camp. At the start of the summer, 100 campers arrive and learn that you offer 5 unique courses. These courses can’t have more than 25 campers each. The campers all submit ballots expressing their preferences for the courses. How do we maximize course allocation satisfaction?

The general case

• V voters that each submit a ballot of preferences
• G groups, each with a maximum capacity (e.g. G₁^cap = 25)
• Maximize satisfaction (open to interpretation)

Algorithm sketches

A horrible algorithm

for group-x in groups:
    while group-x has remaining capacity:
        allocate any unallocated voter to group-x

Clearly this isn’t going to cut it. Preferences aren’t being taken into account at all. We’re just dumping voters into groups.

Linear optimization

convert each ballot into an allocation of points where
    all group preferences are in [0, 1]
    sum of group preferences = 1
system satisfaction = sum of voter satisfaction for all voters
linear optimization to maximize system satisfaction

As an illustration of the principle, consider an example with voter V₁ that prefers G₁ and voter V₂ that prefers G₂. Assigning the voters to their preferred groups optimizes the system satisfaction at 2, whereas switching them around produces a system satisfaction of 0. Okay, this is a step forward.

Possible problem case:

5 groups, each with a capacity of 1
voter 1:  0.4  0.2  0.2  0.2  0.0
voter 2:  0.7  0.2  0.0  0.0  0.1
voter 3:  0.0  0.7  0.2  0.0  0.1
voter 4:  0.0  0.0  0.7  0.2  0.1
voter 5:  0.2  0.0  0.0  0.7  0.1
system optimizes with voter 1 in group 5
voter 1 allocated to their least preferred group

This algorithm provides a measure of preference debt that we can use in the iterative versions of this problem. Also, I’m not sure how much of an issue tactical misrepresentation is here.

Additional problems

Consider the additional problem where voters vote once per day for new sets of courses. This can vary on fixed or variable set of voters, on a fixed or variable set of groups. Consider further the constraint where groups have both a minimum and a maximum capacity. Or perhaps where C has preferences for G and G has preferences for C.

I don’t quite have the solutions to any of this just yet, but it’s an interesting problem space. Someone has to have studied this already. Pointers in the right direction?