Contest Theory

The IOI this year took a radically different approach to contest programming than the IOIs in the past. The Canadian Host Scientific Committee decided that it would be a good idea for the IOI to less favor the teams who have individuals who train very hard on standard algorithmic and data structure problems. I will put off judging whether that was a good or a bad decision until later in this post.

There is one fundamental aspect of writing a contest which is up for major contention and I don't believe that people pay enough attention to it. This is the question that you have to answer before you write a single problem for your test. That question is who should win.

Who should win? It seems like a simple question. The person who is best at math should win a math contest, the person who is best at skiing should win an Olympic medal for skiing. But these answers don't really tell you who should win. If I were to run a contest and I said that the winner would be the person who is best at life, nobody would take me seriously. Why? Because there are a relatively small number of things that would be on this contest. We wouldn't be able to determine the best sports player by just playing football, or just football and soccer, or any other (proper) subset of the sports in the world. And even if we were to play every sport in the world, I'd have to give an arbitrary weighting to each one. How do I compare two people if they have different strengths? It's simply not possible.

This problem arises at a lower level too. Let's look at football. Who is the best football player? I could say let's have a competition where everyone plays football. But this won't work. Maybe one player is a very strong quarterback and another is a very strong wide receiver, but only one of them gets their favored role. Well okay, let's have them pick their positions. We still have an issue. How are we supposed to compare someone's performance as a quarterback to another person's performance as a wide receiver?

Perhaps the answer is to have a quarterback competition, solely to determine who is the best quarterback. That is certainly a possible solution, but sometimes this will make the field too small. Say we object to a spelling competition because there are words from a plethora of sources, which some people will be better at than others. So we use our technique and say okay, we will have a spelling competition consisting of only English words of Sanskrit origin. How many people are specialists of such words? There are probably a few, but not enough to make a competition.

So we need some sort of compromise. We have to accept the fact that there are different specialties within whatever activity for which we hold a competition and that these are in some ways not comparable, but at the same time compare them somehow and determine a winner. It is for this reason that it is not the job of the contest to determine the best, but rather it is the job of the contest to determine the winner.

Of course, if there is a single best competitor, that person should win the competition. If one person is better than everyone else at every position in a football team, he would win a football competition. If your method of determining the winner didn't do that, then you have some problems. But this can be resolved by essentially any performance based scheme that uses positive weights on every event.

But in practically every case, there isn't a single dominating competitor, but rather several top competitors who all do well in different areas. So which one of them should win? It's up to the contest organizers to decide.

And this decision is often very debatable. Perhaps the most prominent example for me personally is the US IMO team selection. There is little argument to be made against the choice to favor those who will bring home the highest IMO scores. The argument stems from the fact that the US team leadership has seemingly decided that the most important subjects to be good at are algebra and geometry, casting aside combinatorics and, to a lesser extent, number theory. It's painful to look at the TST to see three geometry problems, graded in difficulty, so that it is almost certain that geometry skill will matter in team selection, in stark contrast with the single combinatorics problem, difficult enough that only Evan solved it (although I like to think I might have if I hadn't spent nearly all of my time on a geometry problem), clearly not mattering for team selection. The IMO claims to be a contest about all four main subject areas, but the US strategy says loud and clear that this is not the case.

Who is at fault? It's difficult to say. Maybe no one. Maybe everyone. It could be that the lack of combinatorics problems did not stem from a belief that combinatorics does not correlate to IMO score. It could be simply that there was not a sufficient supply of appropriate and interesting problems last year, so the TST was forced to be mostly comprised of the other subjects. But I'm not convinced that this was the case.

So now we return to IOI. The Canadians looked at the IOI and decided that they did not like the choice of winner that was made in the past. They didn't want someone who simply coded problems from online judges for the past year to have an easy road to victory. They wanted someone who could think about a problem which didn't have a standard complete answer and could still perform well.

So they changed the contest.

Gennady still won, of course. IOI might be a case where a dominating force actually exists. Regardless, the IOI change hurt my personal placement, but I can understand where it came from. The Canadians did well to explicate their goals, their means to reach those goals, and why those were their goals in the first place. I agree that the IOI had been reaching a less optimal position by simply escalating the difficulty of algorithmic problems, but I also think that the Canadians went too far in the other direction.

Next time you're involved in running a competition. Ask your group the question, ``Who do we want to win?''