Wednesday, November 25, 2009

Take Out Your Pencils 3

In my most recent Ec 10 lecture, I discussed Arrow's Impossibility Theorem. Here, from my favorite textbook, is a fun problem based on it:

A group of athletes are competing in a multi-day triathlon. They have a running race on day one, a swimming race on day two, and a biking race on day three. You know the order in which the eligible contestants finish each of the three components. From this information, you are asked to rank them in the overall competition. You are given the following conditions:

  • The ordering of athletes should be transitive: If athlete A is ranked above athlete B, and athlete B is ranked above athlete C, then athlete A must rank above athlete C.
  • If athlete A beats athlete B in all three races, athlete A should rank higher than athlete B.
  • The rank ordering of any two athletes should not depend on whether a third athlete drops out of the competition just before the final ranking.

According to Arrow’s theorem, there are only three ways to rank the athletes that satisfy these properties. What are they? Are these desirable? Why or why not? Can you think of a better ranking scheme? Which of the three properties above does your scheme not satisfy?

---
If you enjoy this kind of thing, click here for the previous installment in this series. And let me note, before anyone asks, that I will not post the answer, so instructors can use the problem as homework.