Whither to Compete

A guest post by Rakesh Vohra.

Fortnow's post on competitive ratio's has prompted a number to speculate on the `right' number of people who should engage in competitive analysis. I took Fortnow's post as an invitation to revisit the arguments in favor of doing this kind of analysis. As I see it there are four arguments:

1. The argument from beauty: Truth is beauty and beauty is truth. The first direction I buy, the second, except in the case of Grecian urns, requires a proof. In any case, I am prepared to accept the aesthetics (or wit, cunning) of competitive analysis as sufficient justification for engaging in competitive analysis. Perhaps competitive analysis is to CS what number theory is to Maths. There are, however, shared aesthetic standards (otherwise the criterion has no bite), so only some kinds of work can be justified in this way. My guess is that the analysis of problems that can be stated with a minimal of fuss, have an immediate appeal and seem simple in the first telling (pretty much what makes for a good number theory problem) meet this criteria. So, TSP, SAT, clique, coloring, max-cut are in. However, the stochastic, dynamic traveling dog and pony problem with piecewise linear costs is out.
2. The argument of fine distinctions: Not all NP-complete problems are alike. Some really are easier than others. Therefore one would like a device to make distinctions between them. The bounds from competitive ratios appear to do a nice job in this regard. Knowing that a problem can be approximated to within a log factor but not within a constant factor does tell us about its difficulty relative to others. Notice that order of magnitude of the ratio suffices for this purpose and not the best possible ratio.
3. The argument from ignorance: If we do not know what the distribution of problem instances looks like what choice do we have? The assumption of complete ignorance is an extreme one and can be justified in some but not all cases. If one adopts this justification for engaging in a competitive analysis one must first argue that the assumption of complete ignorance is reasonable to make. One can imagine natural situations where partial information is available. In these cases it seems reasonable to expect error bounds that incorporate such information. Bounds that are data dependent are not as pretty as ones that are independent of the data, but may be more useful.
4. The beneficial spin-off argument: This is the argument that Vazirani makes. Putting a man on the moon is a Quixotic task but we received non-stick frying pans as a by product. However, we might have had non-stick frying pans by focusing on non-stick frying pans and saved ourselves the trouble of putting a man on the moon. The point is that this argument does not rule out other ways of achieving the same benefits.

The arguments do not provide a universal defense of a competitive analysis but justifications to be used on a case by case basis. I think the question to be asked is this: if an exercise in competitive analysis cannot be defended on aesthetic grounds, reveals/verifies no new and novel distinction, inhabits an environment in which complete ignorance is an unreasonable assumption and has no identifiable beneficial spin-off, why is it being done?

Competitive analysis is now an export business. One of the areas it is being exported to is game theory. This raises a new problem not present in the clean optimization framework. That is, does the notion even make sense when what one is comparing are preferences rather than objective function values?