(From Bram Cohen and Nick Mathewson.)
The players are three reclusive artists. Their real names are Anaïs, Benoît,
and Camille, but they sign their works as “A,” “B,” and “C” respectively in
order to cultivate an aura of mystery. Every week, each artist paints a new
work in one of two styles: X and Y.
The art world despises uniformity: if all three artists paint in the same
style, their paintings don’t sell, and they get no points. If one of them
paints in a style different from the others, the different artist is
avant-garde and receives a point.
Because the artists are reclusive, the players can’t communicate with each
other. All they learn from one week to another is what style the other players
used in the previous week. (They learn this when gallery manager passes them
the latest gossip from the art world.)
What is the ideal strategy? Clearly, it’s bad when all three paint in the same
style. If the players could communicate, they could agree to take turns being
avant-garde, so that one week A wins, the next week B wins, the next week C
wins, and so on. Also, if they could communicate, A and B could conspire to
shut out C by always using opposite styles. (If A and B always differ, C will
always match one of them, and the other will win.) But since the players can’t
communicate except through their plays, how can they arrange to coordinate in
twos or threes?
If somebody ran an iterated tournament of this game in the style of Axelrod’s
Prisoners’ Dilemma challenge, what program would you submit? (Remember that
your program would often be playing against instances of itself, without
Variation: what happens when the artists are so reclusive that they won’t even
speak to their gallery manager? In this variation, they only learn whether they
won the last week or not (by checking for their check in the mail).
The painting is Picasso’s Three Musicians.