9
$\begingroup$

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 by Florian Margaine. My reformulation here has slightly different requirements.

$\endgroup$
  • 1
    $\begingroup$ What exactly was the question? Can we assume that people are absent more or less the same amount? What is wrong with taking the person who has done this the least number of times, or simply a random person? $\endgroup$ – Pål GD Jul 24 '13 at 22:15
  • $\begingroup$ @PålGD Assuming that people are absent by about the same amount would be a simplification. Do it if you want, but if your algorithm works for part-timers, that's better. Taking the person who has done this the least number of times is one solution (though mind the requirement that they know one day in advance, it does make the solution not completely trivial). A random person can also work, but randomness introduces a deviation from fairness which you might want to bound. $\endgroup$ – Gilles Jul 24 '13 at 22:20
  • $\begingroup$ What? No salivating picture? You want us to slave away at our desk doing maths instead of slipping out to the bakery? $\endgroup$ – Caleb Jul 25 '13 at 7:13
  • $\begingroup$ @Gilles - FYI, running an experiment on P.SE with your version of this question. Now that both sites are a bit older, I'm curious to see how each community's answers shape up. $\endgroup$ – GlenH7 Jul 25 '13 at 18:54
7
$\begingroup$

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.

  1. 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.

  2. 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.

$\endgroup$
4
$\begingroup$

Let $\{P_1,...,P_n\}$ be the set of croissant's byers. Let ${v_i}^k-1$ be the amount spent by $P_i$ on croissant up to the day $k$ (it can be the number of times he buy croissant if they always spend the same money whatever the number of peoples present, which don't look clever enough for our croissants lover); the $-1$ is for initialisation and to avoid division by $0$.

For some parameter $l$, let $v^k=\sum_{i=1}^n ({v_i}^k)^l$.

At day $k$, they choose the next day's croissant's buyer by firing a random variable that outcome $i$ with probability $1-\frac{(v_i^k)^l}{v^k}$. If the chosen one is not here (today or the day after) they toss the coin again until they find a suited one (he does exists, because they are mostly here every day...).

And they lived happily until they find out that $P_1$, that coward, was there, only one day over two, and so, never buys any croissant!

After some reflection (and may be a bit of torture on $P_1$ so that he refund the croissant he eat without paying) they modifies a their algorithm.

They compute the average price of croissant they pay every day and call it $v$.

On the first day they compute a planning of buyers for the days to come. To do so they do as before with the random variable, and updating the $v_i^k$ by the price they should have paid on day $k$, i.e. adding $v$ each time they are planned to go to the baker. Because they are clever and they don't want to pay too much they also remember how much they really paid at day $k$ so that when they will update the planning no one is penalised.

They plan, until every $P_i$ has a date in the future where he should buy croissant.

If $P_i$ was planned to buy croissant on day $k+1$ but announces that he can't on day $k$ (or if he hasn't be warmed) he give his place to someone present that has no obligation the following day e.g. $P_j$ and he take the next turn of $P_j$.

The day when the first of the $P_i$ is not planned to buy croissant in the future, they prolong their planning (with the random variable computed with the $v_i^k$ updated to the real amount they have paid and the amount planned) until everyone is back on the line.

And when this goes forever, they live happy, sharing equally the price of croissant.

But $P_1$ is not happy. Indeed, he think that the chosen $l$ is too small and so the probability of paying twice in a row too big. Whatever ... The others let him choose $l$ as large as he wants. Because he is grumpy but not stupid, he chose $l=k$ that way as time pass even if the ratio between big payers and small players tend to not be seen the big $l$ tend to emphasize it.

Still $P_1$ is not so happy, he is there only half of the days (so half of the croissant) and has to pay as much as $P_2$ that is here every days. Unfair!

But because they are tired of grumpy $P_1$, they chase in away. But in the corner of their head they are still thinking of changing the $v_i^k$ in the difference between what they paid and what they eat (normalized to get positive values) but they are too lazy and too full of croissants.

Ps: Sorry for the bad English but I'm not native speaker and it's late ... please feel free to correct mistakes (and may be add so spices to the story ...)

$\endgroup$
2
$\begingroup$

Every iteration you have

  • A list of people who are present and available to buy
  • The previous buyer

If you pick a person at random among the people in the list and excluded the previous buyer, you achieve your objectives:

  1. The algorithm is "maximally" random as we use the minimum amount of information from the previous iteration and choose randomly.
  2. On average people pay for (N/(N-1)) croissants every time they participate in an extraction making the algorithm as fair as possible.
  3. I would suggest to eliminate the no-repeat rule to make this maximally random.

Other algorithms I've seen proposed are less random or less fair:

  1. "Deck shuffle" algorithms are not really random in the sense that the probability to have to pay is not constant (1/N in the first pick, 1/(N-1) in the second... 1 at the Nth pick -- if one hasn't been picked yet). Furthermore, if you are picked first, you have exactly zero chances to be picked for the next N times. The system is easily broken by coming in rarely until picked and then constantly.

  2. "Compensative" algorithms that try to actively make everyone get the same number of croissants instead of relying on the properties of random numbers fail to be random or fair (or both).

$\endgroup$
  • $\begingroup$ With $N$ people and $m$ employees present on average per day, the deviation in number of times will be approximately $\sqrt{N / m}$. Since solutions exist that never deviate more than $1$, this is a strange definition of "fair" (especially since it was specified to be "as many times"). $\endgroup$ – Rex Kerr Jul 25 '13 at 2:05
  • $\begingroup$ $N$ purchases, of course, not people. $\endgroup$ – Rex Kerr Jul 25 '13 at 13:05
  • $\begingroup$ @RexKerr why would you buy more croissants than employees? $\endgroup$ – Sklivvz Jul 25 '13 at 13:25
  • $\begingroup$ I'm confused. Where did I suggest one would? $\endgroup$ – Rex Kerr Jul 25 '13 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.