Least surprise in tournaments

Now that we've seen how trying to combine plausible-sounding rules can surprise APL programmers, let's look at a more mundane example: a tournament to find out which of several teams is the strongest. We shall learn that it is hard to avoid surprising results, even in simple cases.

As an example, suppose we have three teams, each with three players. We shall imaginatively call them Team 1, Team 2, and Team 3. Suppose further that each player's strength is reliable--in other words, if player A ever beats player B, player A will always beat player B. Moreover, we will assume that players' strengths are transitive--in other words, if player A beats player B and player B beats player C, then player A will also beat player C. Finally, let's assume that no two players are exactly the same strength.

Under such circumstances, it should be easy to see that there is a unique strongest player, because our assumptions imply that when players compete against each other, the results define a total ordering of the players' strengths. No surprises so far.

Now assume that we have three teams of three players each, and we want to determine which team is strongest. The first problem is to define what it means for one team to be stronger than another.

Suppose we define the strength of a team by a round-robin tournament. Every player in one team plays every player in the other; then the team that won the most games is considered the stronger one. On the surface, this rule seems fair. If each team has three players, then there will be nine games; and because ties are impossible (because we assumed that no two players were exactly the same strength), one team will always win more games than the other. So we now have a way of determining which of our three teams is the strongest: Play each team against the other two and see what happens.

Let's make one more supposition: The relative strengths of Team 1's members are 8, 1, and 6; Team 2's members have strengths of 3, 5, and 7; and Team 3's members have strengths of 4, 9, and 2. Now let's play our tournament and see what happens.

Team 1's first player beats everyone on Team 2, and the second player loses to everyone on Team 2. The third player, with strength 6, beats two of Team 2's members and loses to the third. So Team 1 wins, 5 to 4.

Team 2's first player loses to two of Team 3's players; each of Team 2's other players wins two and loses one. So Team 2 beats Team 3, again by 5 to 4.

Finally, when Team 1 plays Team 3, Team 1's first player wins two games, the second player loses all three, and the third player wins two. So Team 3 beats Team 1 by 5 to 4.

Look what has happened! We started with players of well-defined relative strength. We put them together into teams and tried to determine the teams' relative strength by the most straightforward method possible. The result was that our teams' overall strength was not transitive. If that's not a surprise, I don't know what is.

The moral of the story is that just because we know how to compare one object with another, we do not necessarily know how to compare one collection of objects with another. We shall see some more examples of this phenomenon in the next few posts.

Posted by Andrew Koenig at 02:26 PM  Permalink