THE BIDDING GAME

By Erica Klarreich

In July 1994 in the ballroom of the Omni Shoreham Hotel in Washington, D.C., a most unusual auction was in progress. No famous paintings, valuable coins, or antique furniture sat on the auction block. For sale was nothing but air: a slice of the electromagnetic spectrum for a new generation of cell phones, pagers, and other wireless communication devices. The U.S. government had never auctioned anything so valuable before, and no one knew just what was going to happen. The Federal Communications Commission (FCC) estimated that the airwave spectrum was worth about $10 billion, but telecommunications industry leaders scoffed at the idea that they would pay anywhere near that sum.

Once bidding launched, however, prices started rising tens of millions of dollars by the hour, to telecom executives' disbelief and horror. "It felt as if we were playing multi-million-dollar games of poker," recalls John McMillan, an auction theorist at Stanford University, who helped the FCC run the auction.

That first auction garnered $617 million for just 10 small licenses, and another held in December of that year raised more than $7 billion, breaking all records for the sale of public goods in America and leading the New York Times to hail it as "the greatest auction ever." By early 2001 the spectrum auctions had brought in $42 billion, with more licenses still to be sold.

But things could have turned out differently. To make sure the auctions would go smoothly the government invested a lot of effort in preparing the rules of the auctions, and it paid off.

Designing the auction rules was a problem of great complexity. The FCC had divided the spectrum into thousands of licenses. Should it auction them all at once or one at a time? Should it use an open bidding format or collect sealed bids? Could it choose rules that would ensure that the licenses went to firms that would use them quickly and efficiently? Could it avoid loopholes firms could exploit, as well as prevent companies from colluding with each other to keep prices low?

To attack these questions the FCC turned to experts in the mathematical field of game theory, which figures out which strategies work best in a competitive situation. Over the decades economists had used game theory to develop a detailed picture of how bidders would behave in different types of auctions. Now the theoretical picture was put to the test, and it passed with flying colors.

The U.S. spectrum auctions have been imitated globally to sell a wide range of goods and services, including electric power, timber, and even pollution reduction contracts. Most of these auctions have been great successes. A few, in which the designers failed to heed the lessons of game theory, have been dismal flops.

The founders of game theory could never have dreamed that by the end of 2001, auctions designed using the principles of game theory would have raised more than $100 billion worldwide. Game theory, which started out in the 1920s as basic research into strategies of such parlor games as poker, has become very big business indeed.

The Rules of the Game

More than 70 years ago mathematicians started realizing that analyzing simple parlor games could illuminate many situations in which people compete with one another and have to decide what strategy to adopt. The principles they discovered have shed light on subjects from how nations interact in a nuclear arms race to why some organisms cooperate with one another. And in one of its most striking successes, game theory has led to a revolution in the way economists understand auctions.

The renowned Hungarian mathematician John von Neumann, a lecturer at the University of Berlin at the time, launched the field in 1928. He was curious about how game players should choose their strategies: When, for instance, should a poker player bluff? He studied two-player "zero-sum" games, such as chess and tic-tac-toe, in which the players' interests are entirely at odds: in the simplest manifestation, one player's gain is the other player's loss. As any child knows, in tic-tac-toe both players can avoid losing; if they each follow their best strategies, they force the game to end in a draw. Von Neumann proved that in any two-player zero-sum game, not just in tic-tac-toe, there is a certain "right" outcome, in the sense that neither player can reasonably expect any better outcome unless the other player makes a mistake. This implies, for example, that if two chess players follow their best strategies, the game will always have the same outcome. Luckily for the excitement of the game, however, no one has ever figured out what that outcome is - a win for white, a win for black, or a draw?

Von Neumann and economist Oskar Morgenstern of Princeton University became convinced game theory would illuminate economic questions, and in 1944 they published a book, The Theory of Games and Economic Behavior, arguing that point. At the time, the prevailing approach to economics was to look at how each individual responds to the market as a whole, not how individuals interact with each other. Game theory, von Neumann and Morgenstern argued, would give economists a way to investigate how each player's actions influence those of the others.

Von Neumann and Morgenstern's book analyzed zero-sum games and cooperative games, in which players can form coalitions before the game starts. But many economic interactions don't fall into either of those categories; for instance, von Neumann and Morgenstern's cooperative framework doesn't apply to situations in which the players have valuable secrets to preserve. For that reason, although cooperative game theory was useful for studying certain economic questions, such as problems of supply and demand, it was less useful for such subjects as auctions.

In the late 1940s mathematician John Nash, then a young graduate student at Princeton, realized that in any finite game - not just a zero-sum game - there is always a way for players to choose their strategies so that none will wish they had done something else. In 1949 he wrote a two-page paper whose ideas would change forever how economics research is pursued. Nash came up with the notion of a "strategic equilibrium": a collection of strategies, one for each player, such that if all the players follow these strategies, no individual player has an incentive to switch to a different strategy. In the setting of two-player zero-sum games, Nash's equilibrium gives exactly the same solution as von Neumann's analysis. But Nash's concept goes far beyond this scenario: He proved that even non-zero-sum games and games with more than two players must have at least one equilibrium.

Consider, for example, a three-person "duel" in which Alex, Barbara, and Chris will fire simultaneous gunshots at each other once every minute. Alex and Barbara are sharp-shooters who hit their target 99 out of 100 times. Chris, however, only makes his shot 30 percent of the time. Surprisingly, if all the players follow their equilibrium strategies, Chris is the most likely to survive! Alex and Barbara's equilibrium strategy is to fire first at each other, since it is in their best interest to kill their most dangerous opponent first. The most likely outcome is that Alex and Barbara will kill each other on the first shot, and Chris will escape unharmed.

In some games the Nash equilibrium predicts an even more counterintuitive outcome. Imagine, for example, that you belong to a criminal gang, and you and one of your accomplices have been caught. The police don't have enough evidence to convict you, and if you both stay silent then the best they can do is convict you on a lesser charge with a one-year prison sentence. The police offer you a deal: If you squeal on your accomplice, they'll let you off with a half-year sentence, while your hapless accomplice will get 10 years. But you know that in the next cell over, the police are making the same offer to your accomplice, and if you both rat on each other then you'll each spend seven years inside.

In this famous "Prisoner’s Dilemma" game you're better off if both of you stay silent than if both of you squeal. But that's not what will happen: Staying faithful to each other is not a Nash equilibrium, since you can improve your lot by squealing. The only Nash equilibrium is for both of you to squeal. In fact, squealing is what is known as a dominant strategy: It is the best thing for each of you to do, no matter what the other player does. Assuming you are both motivated by pure self-interest, you are inexorably driven toward seven-year sentences, while by cooperating you could have gotten one-year sentences.

Nash's equilibrium concept gives economists a precise mathematical approach to analyzing how people will behave in competitive situations. But, perhaps because of its very simplicity, for a couple of decades after Nash wrote about the equilibrium, most economists didn't realize just what a powerful tool he had handed them. Even Nash's dissertation advisor thought Nash's theorem was an elegant result, but not a particularly useful one.

Part of the reason many economists didn't immediately see the value of Nash's equilibrium concept was that in Nash's formulation, each player knows ahead of time what payoffs the other players will earn from the different possible outcomes. But in many economic interactions this is not the case. In an auction, for instance, a bidder generally doesn't know how much the other bidders value the item being sold, making it harder to guess their strategies.

In 1967 game theorist John Harsanyi of the University of California, Berkeley, developed a method to do Nash equilibrium analyses even when players have incomplete information about each other's values. Twenty-seven years later Nash and Harsanyi shared the Nobel Memorial Prize in Economics with another game theorist Reinhard Selten, of the University of Bonn in Germany.

With these ideas in hand, more and more economists started feeling that game theory might have some important things to say about their field. Auctions, whose precise rules make them akin to games, seemed like a natural testing ground for the theory. Researchers interested in auctions began to roll up their sleeves.

Which Auction Is Best?

When economists began to turn the power of game theory on auctions, they started noticing that one economist, William Vickrey of Columbia University in New York, had already used game theory to analyze auctions several years before Harsanyi developed his theory. Vickrey's brilliant study of auction strategies was ahead of its time: Written in 1961 when economists were only starting to get a sense of game theory's importance, it was relegated to an obscure journal and overlooked for years. Today, however, it is seen as the pioneering paper in the field of auction theory.

Vickrey, who earned the Nobel Memorial Prize in Economics in 1996 partly for his work on auction theory, studied what economists call "private value" auctions, in which each bidder's value for the item for sale is independent of the values of the other bidders. For instance, if a Rembrandt painting is being auctioned and you want to buy it simply because you like it, then knowing how much your rivals value it won't affect how much you value it yourself. Vickrey compared three of the most common auctions (English, Dutch, and sealed first-price auctions) and designed a fourth with some surprising properties.

An English auction is the familiar "going, going, gone" auction of such art houses as Sotheby's and Christie's, in which the price goes up until only one bidder remains. In a Dutch auction the price starts out high and drops until someone is willing to pay that price. In a first-price auction, participants submit sealed bids and the highest bidder wins, paying her bid. To these auctions Vickrey added what became known as the second-price auction, in which participants submit sealed bids and the highest bidder wins, but pays only as much as the second-highest bid.

Why would anyone use such an arbitrary-sounding rule? Although Vickrey's auction seems the least natural of the four, it is the one with the simplest optimal bidding strategy: Just bid the amount at which you value the object.

Suppose, for instance, you're willing to pay up to $100 for an antique doll. What will happen if you bid less than $100, say $90? If the highest rival bid is $80, you'll win and pay $80; but the same thing would have happened if you had bid $100. If the highest rival bid is $120, you'll lose; and again the same thing would have happened if you had bid $100. But if the highest rival bid is $95, you'll lose the auction, whereas if you had bid $100 you would have won the doll for $95. So bidding $90 never improves your situation, and sometimes makes you lose an auction you would have liked to win. In a similar way bidding more than $100 never improves your situation, and sometimes makes you win an auction you would have liked to lose. In a second-price auction, honesty is the best policy.

You might wonder, though, why a seller would ever use a second-price auction. Why should she let the winner pay the second-highest bid when she could make the winner pay the highest bid? Astonishingly, Vickrey proved that in a wide class of situations, the seller can expect the same amount of money regardless of which of the four auctions she uses. In 1981, game theorist Roger Myerson of the University of Chicago extended Vickrey's result to show that all auctions bring in the same expected revenue, provided they award the item to the bidder who values it most, and provided the bidder who values it least doesn’t pay or receive any money, as would happen if there were a fee or reward simply for entering the auction.

It's easy to see that an English auction produces the same revenue as a second-price auction: An English auction ends precisely when the second-highest bidder drops out (although in some English auctions bidders must raise the high bid by some definite increment, in which case the winner pays marginally more than the second-highest bid). The Dutch auction and the first-price auction are also equivalent to each other, since in a Dutch auction, the prize goes to the bidder willing to bid highest, and she pays what she bids.

But why doesn't a first-price auction bring in more money than a second-price auction? The reason is that in a first-price auction, it doesn't pay to bid honestly. If you bid $90 for the antique doll, and the second-highest bid is $80, then you'll win the doll for $90. If you had bid $100, you would have won but paid more. So in a first-price auction the best strategy is to bid less than your value for the item - what auction theorists call "shading" your bid.

Vickrey figured out how much bidders should shade their bids by looking for the Nash equilibrium strategy. This best strategy varies depending on the circumstances of the auction - for instance, the more bidders in the auction, the less each bidder should shade his bid, since there is less room between the highest bidder's value and the second-highest bidder's value. But Vickrey found that no matter what the number of bidders, the shaded bids mean the seller takes home only as much money as in a second-price auction.

Vickrey and Myerson's work would seem to be the end of the story. All auctions bring in the same revenue, and the second-price auction has the easiest strategy. So it seems that auctioneers should just always use second-price auctions.

But it's not that simple. Vickrey's work laid the foundations of auction theory, but it didn't answer all the questions. His work didn't cover auctions in which the bidder who values the item most doesn't necessarily win it - for instance, auctions that give preference to disadvantaged bidders (such as small businesses bidding against huge corporations), or auctions in which the seller sets a reserve price below which no one will win the item at all. What's more, Vickrey assumed bidders have private values - knowing how their rivals value the item wouldn’t change how they value it themselves. But in most auctions, bidders' values influence each other in subtle ways. Even in an art auction, in which many collectors are motivated purely by how much they like the work, some bidders may be dealers. If they find out, for instance, that a savvy dealer values the item highly, they are more likely to value it highly themselves.

Understanding situations in which bidders care about the market value of an object, not just how much they like it, gave economists plenty to do in the next few decades after Vickrey's work. The result would turn out to shed a crucial light on a wide range of auction environments, from government sales of oil drilling leases to airwave spectrum auctions.

The Winner's Curse

In 1971 three employees of the petroleum giant ARCO (Edward Capen, Robert Clapp, and William Campbell) noticed something odd. Oil companies bidding for offshore drilling rights in the U.S. government's first-price auctions seemed to be suffering unexpectedly low rates of return on their investments, often finding much less oil underground than they had hoped. Why did the oil companies - which on average are pretty good at guessing how much oil lies buried in a tract - seem so often to pay more than the tract turned out to be worth?

As an analogy, imagine that a jar of nickels is being sold in a sealed first-price auction. The jar holds $10 in nickels, but none of the bidders know that; all they can see is how big the jar is. The players independently estimate how much the jar is worth. Maybe Alice guesses right, while Bob and Charlie guess the jar holds $8 and $12, respectively. Diane and Ethel are farther off, putting the value at $6 and $14, respectively.

If all the bidders bid what they think the jar is worth, Ethel will win, but she’ll pay $14 for $10 in nickels - what economists call the "winner's curse." Even if the jar is sold in a second-price auction, she will still overpay. Although on average the bidders are correct about how much money is in the jar, the winner is far from correct; she is the one who has overestimated the value the most. In 1983 economists Max Bazerman and William Samuelson, then at Boston University, performed an experiment in which M.B.A. students bid on a nickel jar in a first-price auction; on average the winner paid 25 percent more than the jar was actually worth.

To protect themselves from the winner's curse bidders must follow an odd logic. In any auction presumably some people will overestimate the value of the item. If everyone bids what they think the item is worth, the person with the highest overestimate will win and pay too much for the item. So the safe strategy for each bidder is to assume she has overestimated, and lower her bid somewhat. If she really has overestimated, this strategy will bring her bid more in line with the actual value of the item. If she has not really overestimated, lowering her bid may hurt her chances of winning the auction; but it's worth taking this risk to avoid the winner's curse. This reasoning applies not just to bidders for jars of nickels but also to oil companies bidding for drilling rights, baseball managers bidding for players' contracts, dealers bidding for paintings, and bidders in any situation where the item has some intrinsic value about which the bidders are uncertain -  what economists call "common value" settings.

In the late 1960s economist Robert Wilson of Stanford University decided that game theory was the way to understand common value auctions, and he convinced many of his students and colleagues to think the same. Wilson used the Nash equilibrium to figure out just how much bidders should subtract from their value estimate to provide a good safety net against the winner's curse. Again, the optimal strategy depends partly on the number of bidders. But in this case the more bidders in the auction, the more each bidder should lower her bid, because if there are many bidders, the distribution of their value estimates is probably very spread out, with the most optimistic bidder greatly overestimating the value of the item.

In common value settings the four standard auctions are not all created equal. In 1982 auction theorists Paul Milgrom (a former student of Wilson) of Stanford University and Robert Weber of Northwestern University showed that an open English auction usually raises the most revenue - the reason roughly being that because each bidder can see how high the others are going, she will be less afraid she has overestimated and will bid more aggressively.

Bidding Across the Spectrum

By the early 1990s economists had used game theory to analyze bidding strategies for a wide range of situations, including hundred-million-dollar oil lease auctions. But the idea of using game theory to design the rules of the auction itself remained very much theoretical science. In 1993 that suddenly changed.

In August of that year the U.S. Congress told the Federal Communications Commission to experiment with auctioning spectrum licenses for wireless communications services. The FCC's previous method of distributing licenses - just giving them away - had long been a bone of contention.

In the early days of spectrum licensing, the FCC had decided which firms should get licenses by holding hearings. But by the early 1980s so many firms were applying for licenses that the system ground to a halt. In 1982 the FCC decided to start awarding licenses by lottery, figuring that telecommunications companies could sort things out afterwards by selling each other licenses. But the FCC didn't put any restrictions on who could participate in the lotteries, with embarrassing and outrageous consequences: One year, for instance, a group of dentists won a license to run cellular phones on Cape Cod, then promptly sold it to Southwestern Bell for $41 million. Even worse, it took telecommunications companies years to shuffle and reshuffle the licenses into the right hands, which is one of the reasons that Europe got cell phone service so much sooner than the United States.

Congress wanted an easy method to assign the licenses directly to the companies that would use them best. And having witnessed the sums of money companies were paying one another for the licenses, it wanted a share of the loot. Auctions, which tend to award the prize to the bidder who values it most and to extract a lot of money along the way, seemed like the way to go.

In October 1993 the FCC invited the telecommunications industry to submit proposals for how to structure the auction, publishing a preliminary report that contained footnotes to many of the important papers of auction theory. Telecom companies, most of which knew little or nothing about auction theory, started scooping up the authors of the papers as consultants. Auction theorists were suddenly a hot commodity.

The FCC had more than 2,500 licenses to disperse. Traditionally, when many items are up for auction, auctioneers sell them one at a time. But spectrum licenses, unlike rare coins or paintings, are not independent of each other: One company might want a northern California license only if it can also get a southern California license, for instance. If the licenses were auctioned one at a time, with the northern California license coming up first, a company that wanted both wouldn't know how high to value the northern license, since it wouldn't know what its chances were of getting the southern license later. This would create the risk that some licenses would fail to be won by the bidders who needed them most. And because bidders would have such incomplete information about the value of the licenses, they would bid cautiously to avoid the winner's curse. On the advice of game theorists the FCC decided to auction the licenses in one fell swoop, in spite of the challenges of running such a complicated auction.

The FCC also had to decide which auction type to use: sealed or open bids, first price or second? Milgrom and Weber's research suggested that an open English auction would raise the most revenue, since it would allow bidders to gather the most information and make them bid most confidently. The FCC decided to follow that advice, with a slight twist: In each round of the auction the bidders placed bids secretly in enclosed booths; the FCC then announced the new high price without saying who had bid it. Masking the bidders' identities in this way lessened their ability to engage in retaliatory bidding against each other or in collusion to keep prices down.

The final design, based on proposals by Milgrom, Wilson, and auction theorist Preston McAfee of the University of Texas, Austin, was a spectacular success. Not only did it raise more money than anyone anticipated but it also succeeded in Congress's primary goal: to award the licenses to companies that would use them efficiently. Within two years of the first spectrum auctions, wireless phones based on the new technology were on the market.

Future Directions

Sometimes the main contribution of game theory to auction design is not some deep theorem but simply the idea that it is vital for auction designers and bidders to put themselves into the minds of their opponents. In recent years several disastrous auctions have shown that when an auction is poorly designed, bidders will exploit the rules in ways the auction's creators didn't anticipate.

For instance, in 2000, Turkey auctioned two telecom licenses one after another, with the stipulation that the selling price of the first license would be the reserve price for the second license - the minimum price they would accept for it. One company bid an enormous price for the first license, figuring that no one would be willing to pay that much for the second license, which did in fact go unsold. The company thus gained a monopoly, making its license very valuable indeed.

Sometimes bidders find sneaky ways to encode messages in their bids. In 1999 Germany sold 10 blocks of spectrum in an English auction with just two powerhouse bidders: Mannesman and T-Mobile. The auction rules stated that bidders placing new bids always had to raise the current high bid by at least 10 percent. In the first round Mannesman bid 18.18 million Deutsch marks per unit on blocks 1-5 and 20 million on blocks 6-10. T-Mobile noticed, as did many observers, that adding 10 percent to 18.18 million brings it almost exactly to 20 million. T-Mobile read Mannesman's bid to mean, "If you raise our bid on blocks 1-5 to 20 million and leave blocks 6-10 for us, we won’t get into a bidding war with you." T-Mobile did just that, and the two companies happily divided the spoils.

Figuring out how to prevent such abuses is keeping auction theorists busy. And many other, more specific questions about auction design remain unanswered. Some auction theorists, such as Lawrence Ausubel of the University of Maryland, College Park, are trying to understand how to structure auctions in which many identical items are being sold, to prevent bidders from keeping prices low simply by reducing their demand. Others, such as Paul Klemperer of Oxford University, who helped design the hugely successful British spectrum auction of 2000, are tackling the question of designing auctions with few potential bidders, with the aim of attracting as many competitors into the bidding as possible. A disastrous spectrum auction in November 2000 in Switzerland, in which exactly four strong bidders were bidding for four licenses in an open English auction, highlighted the importance of this problem. Not surprisingly, the bidders got the licenses for a steal, paying less than one-thirtieth the price companies had paid for similar licenses in Britain and Germany just months earlier.

The United States electromagnetic spectrum auctions have given theorists something new to mull over: package bidding. Designing auction rules so that a company can place a single bid for a package consisting of both the northern and southern California licenses would eliminate the chance of the firm getting stuck with one and not the other. This would allow bidders to form more efficient bundles of licenses and make them bid more confidently (and hopefully, higher). But running an auction with package bidding is immensely complicated. If the buyers are all bidding on different packages, how does the auctioneer even decide which are the highest bids in each round? These are thorny issues, but auction theorists are starting to make headway. Milgrom and Ausubel have been working with the FCC to develop package auction designs, and the FCC plans to run a package auction in the near future.

With the advent of online auction services such as eBay, auctions have made their way not only into multi-billion-dollar government sales but also into the daily lives of ordinary people. Observations of these auctions are generating fresh questions. Why, for instance, do many eBay bidders wait until the final seconds of an auction before bidding?

Problems such as these are giving auction theorists a wealth of fascinating new puzzles to sharpen their insight. They will be able to draw upon the wealth of basic research into game theory and its application to auctions. The founders of game theory would surely have approved. Figuring out ingenious strategies and counter-strategies is, after all, the name of the game.