Priority based distribution of items

Question

I have maximum $1000$ items to be distributed among $3$ students Each student has a priority of $40$%, $30$% and $30$% respectively.

I am distributing $100$ items initially in the first round

In the second round $500$ items

In the third round $400$ items

I need to keep the priorities $40$%, $30$% and $30$% in each round

Even if there is a round in which I distribute $1$ item I need to keep the priorities $40$%, $30$% and $40$%: how to achieve this ?

Answer 1

Fix a rota that repeats every 10 items and meets your 40-30-30 rule - for example $ABCABCABCA$.

First $5$ items are distributed as $ABCAB$ so $A$ and $B$ have $2$ items and $C$ has $1$.

Next $8$ items are distributed as $CABCAABC$ so now $A$ has $5$ items, $B$ and $C$ have $4$.

After $20$ items are distributed $A$ has $8$, $B$ and $C$ have $6$, and this is exactly a 40-30-30 split. An exact 40-30-30 split is only possible when the total number of items distributed is a mulitple of 10.

Answer 2

Here are two very useful techniques that both work even if your priorities are not nice round percentages.

For example, they would work just as easily if the priorities were $56.2%, 31.7% and 12.1%!

Model 1. Uniform Random sampling

1. Generate a (uniform) random number $x$, from the interval [0,1).

2. Then if

   • $0.0 \leq x < 0.4$, then distribute item to 1st student,
   • $0.4 \leq x < 0.7$, then distribute item to 2nd student,
   • $0.7 \leq x < 1.0$, then distribute item to 3rd student.
3. Go to step 1 until finished.

Note that this method is independent of which round it is, and also independent of how many items have already been distributed.

Model 2. Quasirandom (Equidistribution) Sampling

In the following method, $\{ x \}$ indicates the fractional part of $x$. For example, $\{ 3.1415 \} = 0.1415$.

Also let $\phi = \frac{1+\sqrt{5}}{2} = 1.61803398875...$, the famous golden ratio.

1. Initially set $x=0$,
2. Update $x$ with the new value of $\{ x + \phi \} $.
3. Then if
   • $0.0 \leq x < 0.4$, then distribute item to 1st student,
   • $0.4 \leq x < 0.7$, then distribute item to 2nd student,
   • $0.7 \leq x < 1.0$, then distribute item to 3rd student.
4. Go to step 2, until finished

Note that, like the first method based on uniform random sampling method, this second method does not guarantee that after distributing 1000 items that the people have exactly 400,300 and 300 items each, respectively. However, this second method ensures that at any point in time, each person will have no more than 1 item different to the ideal situation.

Epilog

If the priorities were actually 56.2%, 31.7% and 12.1%, then the only part of either method that you would need to modify is the following:

• $0.000 \leq x < 0.562$, then distribute item to 1st student,
• $0.562 \leq x < 0.879$, then distribute item to 2nd student,
• $0.879 \leq x < 1.000$, then distribute item to 3rd student.