For Google Investors, a Crash Course in the Mathematics of Bidding
October 26, 2004
Sara Robinson
Anyone who so much as glanced at a newspaper or skimmed a news site during the month of August knows something of Google's much heralded initial public offering and the swirl of controversy surrounding it.
Some of the attention can be attributed to the high profile of the company and the scale of the sale; with by far the most popular Internet search engine and a lucrative advertising business, Google was expected to have a total valuation greater than that of General Motors. But the main reason for the hoopla was the company's unorthodox offering method: a sealed-bid public auction.
In a traditional IPO, usually held to raise cash to pump into the company's business, the investment firms underwriting the process set a share price lower than the expected market value. The firms then allocate shares to their most favored customers. Once the stock debuts on the exchange, the price rises and those customers rake in tidy sums; they return the favor by doing their business with the investment firms. It's a system that favors insiders, but the investment firms see it as just compensation for the time they spent researching the company and assigning a value to the stock. This compensation, of course, is paid for by all of the private shareholders in the company.
In the case of Google, which already had plenty of cash, the primary incentive for the IPO was to give some return to the venture capitalists and loyal employees who had played a part in the company's success. Seeking the best possible price for the early shareholders, the company's executives decided to buck tradition in favor of an IPO method they saw as more egalitarian: a modified "Dutch" auction.
The multi-unit Dutch auction, also called a uniform-price auction, works like this: After setting a price range to be used as a non-restrictive guideline for investors, the company accepts bids, each specifying a number of shares and a price the investor is willing to pay for them.
To set the stock price, the company allocates shares to bidders in descending price order until the available shares are exhausted. The price specified in the last bid filled---known as the "market-clearing price"---is the price that all winning bidders pay for their stock.
In theory, the market-clearing price approximates the real price the shares will command in the market, eliminating the post-IPO bounce and maximizing profits for early stockholders.
Google was not the first company to have an IPO auction, but it was by far the most prominent to do so, and it had the investment community in an uproar. Compounding the furor, Google, working at a momentary apex in the technology stock market, had set an optimistic price range. Even though the range was only a guideline, many investors told reporters that the company was overpriced and said that they did not intend to bid.
Adding to the confusion, Google founders Sergey Brin and Larry Page granted an interview to Playboy magazine just before filing for the IPO. In doing so, they may have violated SEC rules requiring that companies, to avoid improperly influencing their stock price, keep the press at arm's length in the period before a public offering. (Despite the Playboy interview, no researcher connected with Google, including those whose primary affiliation is academic, was permitted to speak to SIAM News, even about published research on Google's search methods.)
In the end, Google was forced to lower its price range substantially, but the stock price had a hefty bounce in the first day of public trading. The reasons for the price "pop," in an auction designed to avoid such effects, lie in the mathematics of bidding.
Honest Bidders
Because auctions have been around for thousands of years, the methods that have endured would seem to be those that work well. But what does it mean for an auction to work well?
Traditionally, the main criterion has been that participants' bids should reveal, either directly or indirectly, their true valuations of the items for sale, so that the goods can be allocated to the person who values them the most. That is, participants should not be able to gain anything by bidding strategically.
For auctions of a single item, one standard method is the English auction, the "going, going, gone" system of auction houses like Sotheby's or Christie's, in which participants bid against one another and the item goes to the highest bidder. Another method is the traditional Dutch auction (not the type used by Google), which originated in the tulip markets of Holland. A Dutch auction of this type operates like an English auction in reverse, with the auctioneer lowering the price in increments until someone is willing to meet it. Both of these methods operate in the open.
A third method, often used by governments for contractors and suppliers, is the sealed-bid, first-price auction. Each participant submits a sealed valuation of the item, and the highest bid wins.
Of these three methods, only the English auction gives participants an incentive to bid truthfully. To see why this is so, imagine that you must submit a sealed bid for a painting that you love. You are willing to pay up to $1 million for the painting, which other bidders probably value far less. In this situation, you would want to bid not $1 million, but rather an amount just slightly higher than what others are likely to bid. In an English auction, by contrast, the price would be raised until the other bidders dropped out; you would end up paying one increment more than the next-highest bidder was willing to pay.
In a paper published in the early 1960s, William Vickrey presented a way to capture this efficiency with a sealed-bid auction. In a Vickrey auction, the highest bidder is still the winner, but he pays the amount of the second-highest bid for the item. Because the amount of a participant's bid determines only whether he wins, and not how much he will pay, he has an incentive to bid only as much as he is willing to pay.
Multi-item Auctions
A standard Vickrey auction is for a sealed-bid sale of a single item. In Google's case, the auction was for multiple equivalent items: shares of stock.
For sealed-bid, multi-item auctions, there are two classic choices: the discriminatory-price, or pay-as-bid auction, in which the highest bidders win and all bidders pay what they bid, and the uniform-price auction (Google's choice), sometimes called a Dutch auction because, in effect, the price is lowered until a consortium of buyers is willing to take the lot at that price.
In such auctions, the number of items a bidder is willing to buy hinges on the per-item price. Thus, a bid is actually a continuum of bids, expressed as a "demand function" describing how many items the bidder wants at each price. A winning bidder receives the sum of the amounts she requested at each price above the cutoff price. (Bids at the cutoff price are allocated proportionally.)
While these methods are natural extensions of their single-item auction counterparts, neither gives participants the incentive to bid truthfully. The first method has the same problem as a sealed-bid, first-price auction, in which the highest bidders could pay far more than their close competitors. In the uniform-price auction, a participant who believes that one of his bids is likely to determine the market-clearing price has an incentive to lower it so as to get a better deal overall.
A solution is a generalization of the Vickrey auction, known as the Vickrey-Clarke-Groves, or VCG auction, an extension in the early-1970s by Edward Clarke and Theodore Groves of a multi-item mechanism given in the 1961 Vickrey paper. In VCG auctions, as in single-item Vickrey auctions, participants have no incentive to bid strategically, again because their bids do not influence the price they pay. Although items are allocated so as to maximize the total of the winning bids, each winning bidder's payment is what economists call the "opportunity cost" of her participation in the auction: the maximizing total bid had she not participated, less the actual maximizing total bid with her bid subtracted out. Because the amount any winning bidder pays is independent of her bid, each participant has the incentive to bid truthfully.
Imagine, for example, three people bidding for a set of two armchairs, one red and one blue. The first bidder wants only the red chair and will pay up to $250 for it; the second wants only the blue chair, for $200. The third bidder is interested only in the set and will pay $350 for it. By the VCG allocation rule, the red chair goes to the first bidder and the blue to the second, corresponding to the maximizing total bid of $450. If either the first or the second bidder had not participated, the maximizing total bid would have been $350. The first bidder thus pays $350 - ($450 - $250) = $150, and the second pays $350 - ($450 - $200) = $100.
If Google had used a VCG auction, the top bidders would have won shares, but the price they paid would have been the sum of the amounts of the bids they displaced. A bidder who won k shares of stock, for instance, would have paid the amounts of the k highest losing bids for shares by other bidders.
Under the assumption that bids are small enough relative to the number of shares that individual bidders do not affect the price-an assumption that is reasonable for the Google auction, according to economist Paul Milgrom of Stanford University-the VCG auction becomes just a uniform-price auction.
Although the VCG mechanism has been around for decades, it has not been widely used in practice, in part, economists say, because it's difficult for bidders to grasp.
In a forthcoming paper in American Economic Review, University of Maryland economist Lawrence M. Ausubel describes an alternative mechanism he devised for auctioning multiple homogeneous goods. Ausubel's auction is an open version of the VCG auction, just as the English ascending-price auction is an open version of the single-item Vickrey auction. Both methods give the same allocation at the same prices, but the open, ascending-price format may be easier for participants to understand, Ausubel says, and gives them more information for formulating their bids.
The Ausubel auction works like this: Starting low, the auctioneer calls out prices, to which participants respond with the quantities of the item that they are willing to take at that price. At each price, the auctioneer determines whether the aggregate demand of a bidder's rivals is less than the supply. If it is, the difference between that aggregate demand and supply is said to be "clinched" by that bidder and is awarded to him at that price. The auctioneer continues, increasing the price until the overall demand is no greater than supply and the market has cleared.
Suppose, for example, that three people are bidding for 100 identical items. The auctioneer starts by calling out $5; at that price, each participant would take all 100 items, an aggregate demand of 300. Suppose now that the auctioneer raises the price in increments, until he gets to $20, at which point the first bidder wants 45 items, the second wants 50, and the third wants 55. The aggregate demand of the third bidder's rivals is 45 + 50 = 95, which is five less than the supply. Thus, the five units would be deemed clinched by the third bidder, at a price of $20 each. The auctioneer then continues to raise the price for the remaining 95 items until all the units have been clinched at varying prices and the market has cleared.
As with VCG, the price each bidder pays for his units is independent of his bid, giving him the incentive to reveal his true valuations for the items. And, as with an English auction, Ausubel's mechanism is dynamic and therefore more transparent to the bidders-an issue that becomes important when bidders' valuations are interdependent.
Public-goods Auctions and Google
In the auctions discussed thus far, each bidder can assign an intrinsic value to the item that is independent of how others value it. In many auctions, however, bidders' valuations are not independent; rather, bidders come up with bids based on what they believe the eventual market value of the items will be.
Such auctions are susceptible to a phenomenon known as the "winner's curse." Suppose that you bid on a house against a large group of other bidders, and win. Your valuation of the house must have been higher than anyone else's, which suggests that you overvalued the house and might have trouble selling it at that price. To counteract the curse, participants must lower their bids.
Even sealed-bid, Vickrey-style auctions are not immune from the winner's curse. Open auctions, like the English single-item auction or Ausubel's multi-item ascending-price auction, mitigate the effect somewhat by allowing participants to change their valuations based on others' bids.
A uniform-price auction like Google's is susceptible not only to a winner's curse, but also to a loser's curse. If, in the Google auction, most people who bid got shares, it follows that those who did not get shares may have undervalued them. Which curse dominates depends on the number of bidders relative to the number of shares, Milgrom says. In the case of many shares and few bidders, the winner's curse dominates; the reverse situation favors the loser's curse. Astute participants in the Google auction would have had to decide which effect was dominant and adjust their bids accordingly.
Another, separate question faced by prospective Google participants was whether they should participate at all. Would the auction method set a stock price above or below the market price?
Participants had two reasons to believe that the market-clearing price for the auction might be lower than the market price. First, many of the participating investment firms restricted the number of bids a bidder could place. If many bidders were forced to submit demand functions consisting of a single bid, successful bids were likely to be higher than the clearing price. In this case, successful bidders, seeing a bargain, could be expected to scramble for more shares as soon as they began trading on the market, thus raising the share price.
Second, as Milgrom points out, the prospectus gave Google the option of purposely setting the stock price lower than the market-clearing price in order to get a first-day pop in trading. In that case, as stated in the prospectus, shares would be allocated either proportionally among bidders or with a cap on the maximum number given to an individual bidder. Astute participants would have noticed this in the prospectus and factored it into their bids, Milgrom says, but it is not reasonable to expect so high a level of sophistication of all participants. In any case, such a calculation involved some guesswork, because Google did not announce its choice in advance.
The Google Outcome
On August 18, Google sent notices to the winning bidders, and on the morning of August 19 the stock began trading at $85 per share. By the end of the day, more than 22 million shares had changed hands, and the stock price had risen 18%, to close at $100.34. In press interviews, some participants revealed that they received only 75% of the shares they had requested. It appears that Google did decide, for whatever reason, to set the stock price below the market-clearing price.
If Google's goal was to maximize profits for employee stockholders, the outcome of the auction was mixed. The 18% pop was unnecessarily high, Ausubel points out, but still far lower than the pops of as much as 100% commonly seen in technology stock debuts. In one sense, however, the Google auction was an unequivocal success: How else could the investment community and the public be persuaded to take a crash course in the mathematics of auctions?
Sara Robinson is a freelance writer based in Los Angeles, California.
