Algorithm for assigning users to "buckets" according to users' preferences and ranking

Question

Suppose there is a set of $n$ users which must each be assigned to one, and only one, of $k$ mutually exclusive "buckets". However, the number of users allocated to the $i$-th bucket must be no lower than $c^i_{min}$ and no higher than $c^i_{max}$. A valid allocation is assumed to exist, so that every user is assigned to one and only one bucket. In other words:

$$\sum_i c^i_{min} \leq n \leq \sum_i c^i_{max}.$$

Each of these users have a personal ranking of their favorite buckets among the $k$ available choices. Say $k = 3$, then perhaps user 1 would prefer to be allocated to bucket 1; but if bucket 1 is not available, then to bucket 2; but if bucket 2 is also not available, then to bucket 3. Now user 2 would rather be allocated to bucket 3; but if bucket 3 is not available, then to bucket 1; but if bucket 1 is also not available, then to bucket 2. This goes on on for every other user.

To encode these user preferences, we might have a function $f : \mathbb{Z}/n\mathbb{Z} \to \sigma_k$, where $\sigma_k$ is an element from the permutation group of the set $\{ 1, 2, \ldots, k \}$, that maps each of the $n$ users to a permutation that indicates their preferred assignment, such that the first element of the permutation indicates the user's preferred bucket, the second element indicates the user's next preferred bucket after the first, and so on.

Finally, not only are users' preferences ranked, but the users themselves are ranked. If users are numbered from 1 to $n$, then for the purpose of breaking ties, users with a lower index have priority for their choices over users with a higher index. Say there's only one slot for bucket $i$, i.e. $c^i_{min} = c^i_{max} = 1$, but both users 1 and 2 would rather be assigned to bucket $i$ over all other buckets. Then user 1 is assigned to bucket $i$ and user 2 is assigned to his next preferred bucket.

I'm looking for an algorithm that:

1. Is simple, because it must be executed manually by non-technical people, and as such must be described in plain language, using the least amount of mathematical and algorithmic notation, in an official document.
2. Generates a valid allocation: every user is allocated to one and only one bucket, and the number of users allocated to bucket $i$ is in the interval $[c^i_{min},c^i_{max}]$.
3. Respects the users' preference for a given bucket over another as much as possible, while ensuring that no lower ranked user (i.e. with a higher index) is assigned to a given bucket unless all higher ranked users which prefer this bucket are also assigned to it.

Points 1 and 2 are simple enough, but I'm aware point 3 needs work. I'm open to suggestions for a more rigorous statement of point 3, but what I'm especially interested in is in an algorithm that, given $n$, $k$ and $f$, produces an assignment meeting the three criteria above.

Answer 1

Assuming every user has a complete list of preferences (i.e. has raked every bucket) then there is a fairly simple algorithm. You go through the students in index order, so higher priority users get allocated earlier:

Allocate user $j$ to their most preferred bucket which is not already full.

The only difficult calculation is whether a bucket is full. A bucket is clearly full when it has had $c^i_{\max{}}$ users allocated to it. It is also full when it has had at least $c^i_{\min{}}$ users allocated to it and the number of unallocated users is equal to the number of users needed fill the necessary gaps across all the buckets.

Let's call $g(j)$ the gap to be filled after $j$ students have been allocated: we will have $g(0)=\sum_i c^i_{\min}$ and $g(j)$ will be weakly decreasing. We will also let $a_j^i$ be the number of users allocated to bucket $i$ after the $j$th student has been allocated, with $a^i_0 = 0$ and $a^i_j$ weakly increasing with $j$. None of the buckets start full unless $c^i_{\max} = 0$. So knowing $g(0)$ and $a^i_0$, the algorithm becomes once of allocating users in index order with:

• Allocate user $j$ to their most preferred bucket which is not already full.
• Suppose user $j$ is allocated to bucket $i$. Then
  • $a^i_j = a^i_{j-1} +1$; for other buckets $k\not = i$ you have $a^k_j = a^k_{j-1}$.
  • if $a^i_{j-1} \lt c^i_{\min}$ then $g(j)=g(j-1)-1$; otherwise $g(j)=g(j-1)$
  • if $a^i_{j} \ge c^i_{\max}$ then bucket $i$ is now full and can get no future users
  • if $g(j)=n-j$ and $a^k_{j} \ge c^k_{\min}$ then bucket $k$ is now full and can get no future users

To ease the calculations, note that once full, bucket $i$ will remain full, and that once $g(j)=n-j$, this condition will always be met in future and you have switched to a filling gaps part of the algorithm.

You could describe this to non-technical people as saying you give choice priority to preferred users and the algorithm runs in two stages: initially users get their highest available preferences among buckets with space below their maxima; and at the end users get their highest available preferences among buckets which need users to reach their minima.