with certain security enhancements, be made “incentive-compatible.” That is, users would no longer have any reason to deviate from BGP.

Nisan is a pioneer in the field of algorithmic mechanism design, by which systems find good approximations of optimal solutions in computationally hard problems, such as an auction where instead of a single point bid from each bidder, one gets an entire “graph” of bids and preferences. That approach introduces “an interesting twist,” Nisan says. “Many of the results that we got for free from economic theory stop working when there are approximations.”

Potential Pitfalls

To be sure, there are pitfalls in the application of mechanism design ideas. For example, Robert Kleinberg, a computer science professor at Cornell University, says mechanisms may be so complicated that users don’t understand them and hence won’t participate. It’s not sufficient to tell them, “don’t worry, I have proved a theorem that the best thing for you to do is such-and-such,” Kleinberg says.

A related issue is that the mechanism and the problem it is trying to solve may together be so complicated as to be computationally intractable. The computational ability of participants and their incentives are intertwined in complex ways. And the cost of information gathering in order to bid can distort results, because the choice of how much to invest in bid preparation is not a choice that is included in most theoretical models of behavior.

Sandholm says another potential pitfall is evaluating one event, such as

Procter & Gamble
uses a mechanism
design-based
combinatorial
auction in which
participants can bid
for individual items
or packages of items,
in combinations
specified by them.

one of P&G’s combinatorial auctions, in isolation, as much of economic theory assumes. But if an auction is repeated, buyers and bidders learn something about each other, and that knowledge can lead to behaviors that are both undesirable and not predicted by theory.

Similarly, notions of rationality may be mathematically pure in economics, but “actual human behavior is a lot more complicated and superficially ‘ irrational’ than the predictions made by theoretical models,” Kleinberg says.

And there’s that nasty bit about lying. Of the 200 red balloon sightings reported to the MIT team, 80% were false. DARPA’s Lee says teams detected false reports in some clever ways, with some teams even automating their detection. For example, clusters of reported balloon sightings that contained identical coordinates, to the third decimal, were

regarded as fake because real sightings from multiple people always have some slight variation. “So there is this general concept of being able to use relatively straightforward data-mining techniques to quickly derive the characteristics between good and bad information,” Lee says.

Finally, says MIT’s Pickard, the most elegant of ideas can have unintended consequences. “We spent four days winning the DARPA Network Challenge and about two months working out how to pay people,” he says. “Working with lawyers is a lot harder than making Web sites.”

Cybersecurity

How Top ISPs Could Reduce Spam

the zombie computers
responsible for sending more
than half of the world’s spam
reside on the networks of the
leading 50 Isps, and if these
Isps would shut down or block
these compromised computers,
it would drastically curtail the
delivery of spam, according to
a team of researchers led by
michael van eeten, a professor
of public administration at delft
university of technology in the
netherlands.

into a large network of remotely controlled machines known as a botnet.

“the top 50 Isps account for
over half of all [spam] sources
worldwide,” the researchers
note. “In light of the fact that
there are 30,000 [Autonomous
system numbers] and anywhere
between 4,000 and 100,000 Isps,
their paper, “the Role of Internet
service providers in Botnet
migration: An empirical Analysis
Based on spam data,” at the
Workshop on the economics of
Information security at harvard
university, and are now working
with the dutch government
to create metrics of Isps’
efforts to detect and shut down
compromised computers.