The boundaries separating computer science and other disciplines are blurring at an accelerating pace. As work in computers, biology, the physical and social sciences, and economics becomes more complex, so does the motivation for practitioners to seek help from each other.
Mechanism design, which emerged from economic game theory in the 1970s, is now shaking hands with information technology. Built on a formal mathematical base, mechanism design expresses ideas that are elegantly simple, yet tricky to apply in the real world: people in competition will act “rationally” to meet their own selfish goals; they have private information, and may act in ways that can’t be observed; and they may lie. The central goal in mechanism design is to devise a system by which those people will tend to act in ways that benefit the owner of the system, or society at large.
Information technologists are turning these concepts into such disparate applications as auction management, supply chain optimization, and the matching of organ donors and recipients. Meanwhile, mechanism design is enabling advances in information technology, from network design to distributed computing to operating systems.
The DARPA Network Challenge from the Defense Advanced Research Projects Agency (DARPA) offers one example, with a social networking twist. Last December, DARPA tethered 10 red weather balloons at undisclosed locations across the continental U.S. DARPA’s challenge: Be the first team to find all 10 balloons.
Success would depend on a competitor’s ability to assemble a large group of geographically dispersed volunteers. “We wanted to understand how you could rapidly mobilize a very large team to solve a hard problem, and how to do that in an adversarial environment,” says Peter Lee, a DARPA director. Also, DARPA wanted to learn how teams would use social networks and crowd-sourcing as this might aid in military intelligence gathering.
The DARPA experiment was not conceived specifically as an exercise in mechanism design, but many of the teams, including the winning one from Massachusetts Institute of Technology (MIT), profitably employed those principles, Lee says. For example, the MIT team found all 10 balloons in less than nine hours by devising a clever way to motivate a large number of volunteers through a recursive incentive scheme.
An obvious financial incentive would be to promise anyone who found and reported a balloon to the winning team a part of the $40,000 prize money. Some teams did just that. But the MIT team knew it not only had to motivate people to look for and report balloons, but also to find lots of additional people to help them locate the balloons.
The MIT team recruited an initial cadre of volunteers via email, then encouraged each volunteer to establish a personal chain of participants: A recruits B, who recruits C, who recruits D, and so on. The first person to report a balloon gets $2,000, and more payments propagate through the chain back from that person. D finds a balloon and gets $2,000, C gets $1,000, B gets $500, and A gets $250.
“There were people who actually made $1,000 for posting a tweet,” says Galen Pickard, a computer and cognitive scientist at MIT. “Everyone was incentivized to get the word out, and that’s mechanism design.” Pickard says 5,000 people signed up to assist the MIT team, and estimates that two million people received email, Twitter, or Face-book requests for help.
The MIT team located all 10 red balloons in less than nine hours by devising a clever way to motivate a large number of volunteers through a recursive incentive scheme.
The second-place team from Georgia Institute of Technology did almost as well, finding nine balloons in a largely more traditional way, via old media, including an article in The Wall Street Journal and an interview on National Public Radio. That put Georgia Tech near the top of the results in a Google search for “DARPA Red Balloon,” says Ethan Trewhitt, a research engineer at Georgia Tech. “The crowdsourcing thing was not as big a thing as the old media, which are machines built for this purpose,” he says.
Making Auctions Pay
Tuomas Sandholm, director of the Agent-Mediated Electronic Marketplaces Laboratory at Carnegie Mellon University, has taken the basic concepts of mechanism design and extended and implemented them in novel ways. For example, he has pioneered automated mechanism design, by which complex mechanisms are devised by computers, not humans.
Many real-world applications of mechanism design are complex indeed. For example, Procter & Gamble (P&G) seeks to optimize its supply chain by getting annual bids for trucking services across North America. P&G uses a mechanism design-based combinatorial auction, designed by Sandholm, in which participants can bid for individual items or packages of items, in combinations specified by them. “It’s a very complex optimization problem for both parties, with lots of constraints,” Sandholm says.
Likewise, Paul Milgrom, an economist at Stanford University, co-designed the simultaneous ascending auction used by the U.S. Federal Communications Commission in its sale of radio spectrum licenses in the mid-1990s. According to the National Academy of Sciences, “The auction broke all records for sale of public property and has been widely copied in other countries,” while the National Science Foundation (NSF) hailed it as a “victory for the field of game theory.”
Milgrom’s early work, in the 1980s, mostly dealt with situations in which there was a market-clearing or equilibrium price, and the auction would simply find it. But more recently he’s worked with combinatorial auctions, where there often is no such single price and the computation of efficient outcomes is generally NP-hard. Managing the resulting complexity demands the application of computer science techniques.
Milgrom says he’s working on dynamic resource allocation auctions in which, for example, a seller might have to decide to accept a bid now or wait for a better one tomorrow. More generally, it’s the challenge of efficiently allocating a given resource, such as communication bandwidth, repeatedly over time. Buyers, or users, learn more about the resource’s value by using it. “Some of the best work in this area has been done by computer scientists,” Milgrom says.
Milgrom’s work with mechanism design, stretching back some three decades, clearly is not at an end. Last year, a company he started, Auctionomics, won an NSF grant to develop auction software that allows bidders to specify budget constraints. “Multi-item auction design has been at the frontier of research in economics and computer science over the past 15 years,” NSF notes. “Yet no existing mechanism enables effective competition when bidders face serious budget constraints.”
Meanwhile, mechanism design is also being used to solve problems of network congestion. TCP/IP communication protocols are based on the assumption that when a computer sees congestion, it will temporarily delay sending data. “But when TCP competes for bandwidth with other ‘non-polite’ protocols, such as UDP, it ends up being squeezed away completely,” says Noam Nisan, a computer scientist at Hebrew University in Jerusalem.
Nisan says that all work on communication protocols today should consider the fact that computers are connected yet controlled by “different, selfish entities.” Mechanism design can provide a framework for optimizing those protocols, he says. For example, he cites recent research—namely, “Interdomain Routing and Games” by economist Hagay Levin and computer scientists Michael Schapira and Aviv Zohar from the Hebrew University of Jerusalem—that shows that the Border Gateway Protocol (BGP), which is used for Internet routing among competing domains, could, 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 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.
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.
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.”
Further Reading
Feigenbaum, J., Papadimitriou, C., Sami, R., Shenker, S.
A BGP-based mechanism for lowest-cost routing. Distributed Computing 18, 1, July 2005.
Nisan, N.
Algorithmic mechanism design, Google Tech Talks video, August 15, 2007, http://video.google.com/videoplay?docid=6121409064231775355#.
Royal Swedish Academy of Sciences, Prize Committee
Mechanism design theory. Oct. 15, 2007. http://nobelprize.org/nobel_prizes/economics/laureates/2007/ecoadv07.pdf
Sandholm, T.
Computing in mechanism design. The New Palgrave Dictionary of Economics (2nd ed.), Palgrave Macmillan, Basingstoke, U.K., 2008.
Varian, H.
Designing the perfect auction. Communications of the ACM 51, 8, August 2008.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment