Find out whose turn it is to buy the croissants

A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The purpose of this question is to determine an algorithm for deciding whose turn it will be to bring croissants tomorrow.

Constraints, assumptions and objectives:

• Whose turn it is to bring croissants will be determined the previous afternoon.

• On any given day, some people are absent. The algorithm must pick someone who will be present on that day. Assume that all absences are known a day in advance, so the croissant buyer can be determined on the previous afternoon.

• Overall, most people are present on most days.

• In the interest of fairness, everyone should buy croissants as many times as the others. (Basically, assume that every team member has the same amount of money to spend on croissants.)

• It would be nice to have some element of randomness, or at least perceived randomness, in order to alleviate the boredom of a roster. This is not a hard constraint: it is more of an aesthetic judgement. However, the same person should not be picked twice in a row.

• The person who brings the croissants should know in advance. So if person P is to bring croissants on day D, then this fact should be determined on some previous day where person P is present. For example, if the croissant bringer is always determined the day before, then it should be one of the persons who are present the day before.

• The number of team members is small enough that storage and computing resources are effectively unlimited. For example the algorithm can rely on a complete history of who brought croissants when in the past. Up to a few minutes of computation on a fast PC every day would be ok.

This is a model of a real world problem, so you are free to challenge or refine the assumptions if you think that they model the scenario better.

Origin: Find out who's going to buy the croissants b

There are two categories of solutions to this sort of problem that I'm aware of: biased lotteries and filtered/generated random sequences.

First, let's dispense with easy but wrong solutions that keep no state. Any lottery-style solution that maintains no state will have the number of wins in a binomial distribution, which fails the "as many times" criterion. You can select a random sequence that picks all people equally (just going around the list does that; permutations provide randomness), but once people start going on vacation your sequence now has holes. Unless you keep track, you will again find yourself with binomial distributions instead of maintenance of equal effort.

Let's also commit to having actual randomness. You might want this so that, for instance, a person cannot schedule their vacation on the basis of a deterministic algorithm so that they are never present when it is their turn to buy croissants (until they use up all their vacation days, I suppose).

So, on to the two types of solutions.

-
To construct a biased lottery, first note that we can pick from pretty much any continuous distribution (with finite deviation) to generate numbers for our lottery. The loser can then be the person with the lowest number. Then the simplest bias is to keep track of whether each individual has bought more or less than their share. You can measure the bias in units of croissants. You can tune the degree of randomness by changing the width and shape of the distribution--this will also determine how far away any individual can get from "the same number of times". Gaussians are easy; they allow for reasonable surprise without having tails that are too long ("unfair"). So the basic shape of the solution is (in Scala code)

case class Employee(var bias: Double) {
  def eat         { bias -= 1 }
  def buy(n: Int) { bias += n }
  def roll        = bias + stdev * Random.nextGaussian
}

You can keep track of who bought last and give them a hefty bias bonus (e.g. 10*stdev) to keep people from buying twice in a row save in the edge case where vacation structure allowed everyone to have bought "last" time. (i.e. you buy, then go on vacation.) Same thing for not being present on the day they're selected. (If someone is absent every other day they eventually will come up as they burn through their bias bonus; I consider this a feature rather than a bug.)

So, you collect your list of present employees for the day, have them all roll for the lottery, pick the lowest, and update. You can choose whether to have the buying bonus be equal to the number of employees (good when the cost is negligible but the trip to get croissants is burdensome), the number of employees present (good if the trip is easy but the cost is burdensome), or something in between (to acknowledge both burdens). It's probably better to only have the "eat" penalty for people who are present, but you can do it either way if you feel that merely being on vacation doesn't give you a right pitch in less.

-
To construct a filtered random sequence, first you need to generate a random sequence. Shuffling a list of the employees is as good a way as any to start. Just go through the list, in order, from day to day. If someone can't buy because they're absent or can't be told or bought before, skip them. Now you have a problem: you're accumulating people who have been skipped. That's okay, though. When you get to the end of your sequence, append the list of skipped employees to the full list before shuffling. Now the probability of coming up is proportional to the number of times you've been skipped, which maintains the "same number of times" property.

If you use a standard shuffle, it's also particularly easy to quantify the randomness when there are no vacations. If you picked people completely at random, the knowledge of who was to bring next would contain $\log_2(N)$ bits of information if there were $N$ employees. Instead, however, only $N!$ instead of $N^N$ possible sequences are allowed, so the information is reduced by $\log_2\left[\left( {N!} \over {N^N} \right)^{1/N}\right] \approx -{1 \over {\log(2)}} + {\log_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$ bits (for large $N$; for $N=10$ it's $~1.14$).

Personally I favor the biased lottery solution as the control over the randomness is better. With filtered sequences, you can come up with more complex ways to generate sequences. For example, rather than taking a random permutation, perform local swaps out to a certain distance, or allow swapping of people out of the pool entirely (but they go onto the skipped-list)—but these things require more algorithmic effort. With the lottery, you just adjust the standard deviation.

StackExchange Computer Science Q#13420, answer score: 7