Project 3: Fruit Salad

My mother-in-law likes to serve fruit salad for dessert. To avoid arguments she is very careful to give each bowl of fruit salad the same number of pieces of fruit. While she has great skill at balancing the total amount of fruit in each bowl, she has much less control over the types of fruit in each bowl. So the bowls vary in the amount of each kind of fruit they contain.

Once my mother-in-law fills all the bowls, she passes them around the table. The challenge for diners is to decide whether to keep the current bowl when it arrives, or whether to pass it on to the next person, in the hope that a future bowl will be better. Since each person likes certain kinds of fruit (and dislikes others) there is an incentive to hold out for the best combination. On the other hand, waiting too long may mean you miss out on a good combination and have to settle for whatever comes later. Once you select a bowl, you cannot change your mind -- the remaining bowls are simply passed around until everybody has a bowl.

One difficulty is that you don't know the starting distribution of fruit in the serving bowl. That depends on the quality and availability of the fruit in the market that day (my mother-in-law is very picky). Some kinds of fruit may be completely absent. The only way to determine the apparent distribution is by watching the passed fruit bowls and counting the pieces as the bowls pass by.

The fruit distribution is not uniform. Because the fruit salad is only lightly mixed (``Don't bruise the fruit!'' -- my mother-in-law) there is a tendency for the fruit to cluster. Bowls are created as follows: a type of fruit is chosen at random (with probability proportional to the amount of each fruit type remaining), and a number c between 1 and 3 is also chosen uniformly at random. c pieces of the chosen kind of fruit are added to the bowl. If there are fewer than c pieces of that kind of fruit remaining, or if the bowl needs fewer than c pieces to fill, then c is reduced accordingly. This process is repeated until the bowl is full, and then the next bowl is processed, and so on.

There are twelve kinds of fruit: Apples, Bananas, Cherries, Dates, Elderberries, Figs, Grapes, Honeydew, Ilama, Jackfruit, Kiwi and Lychee. Each diner has a ranking of the twelve fruits represented as a permutation of the twelve letters A through L. The ranking determines how much a diner likes each fruit: the highest ranked fruit scores 12 points per piece, while the lowest ranked fruit scores only 1 point per piece.

There are d diners seated in a circle, and bowls are passed clockwise around the table from the position of the server, who is not a diner. Etiquette demands that bowls cannot make multiple circuits. This constraint means that the last diner in the circle has no choice at all. The last diner gets the bowl that everybody else has passed on. The second to last diner will have one choice, the third to last diner will have two choices, and so on. My mother-in-law recognizes that this is not entirely fair to the last diners, so for second helpings the bowls are passed in the reverse direction. A diner's score is the total of the score for both the first and second helping. (The first and second helpings come from two copies of an identical collection of fruit.)

The players' performance will be judged not on a single round of the game, but on a collection of many games in which each player has an equal number of turns in each position. Each round will have a new distribution of fruit, and a new set of rankings for each player.