˲ v₁ = b₂. In this case, bidder 1 is indifferent about winning or losing, so the bidder may as well report b₁ = v₁.

In each case it is optimal for bidder 1 to report his or her true value, regardless of what the bidder thinks other bidders will do. This is known as a dominant strategy in game theory. If everyone reports their true value, the item ends up being awarded to the bidder with the highest value, which is the efficient outcome in the sense of maximizing the value of the assignment.

The auction used by eBay is basically a form of second-price auction; the bidder who programs his or her bidding agent with the highest value wins, but only has to pay the second highest bid.

Note that in both of the examples mentioned—the 19^th century stamp collectors and the eBay auction—the underlying motivation for adopting this auction form was communication costs. The stamp collectors did not want to mail bids back and forth and eBay buyers did not want to log on every time they wanted to change their bid.

combinatorial auctions

To continue with auctions, let us imagine a much more complex problem in which many items are to be sold. Let x represent an assignment of goods to bidders and let v_a(x) represent agent a’s valuation—the agent’s willingness to pay—for a given assignment. In principle, each agent may care not only about what he or she gets in the assignment, but also what everyone else gets. The seller does not know the bidders’ valuation functions.

The auction design goal is to assign the items to the agents in a way that maximizes the sum of the individual valuations of the assignment.

Perhaps surprisingly, this mechanism design problem can be solved in much the same way as the single item auction. We simply ask each person to report their valuation functions. Next, we find the assignment that maximizes the sum of the reported valuations. The payment that agent a makes is the difference between the maximal value to the other agents if agent a is present and the maximal value if agent a is removed from the calculation. Roughly speaking, each agent has to pay the

cost that his or her presence imposes on the other agents.

To see how this generalizes the previous simple auction, note that in the simple auction the price that the highest bidder has to pay is the cost he or she imposed on the other agents; if the highest bidder weren’t present, the second highest bidding agent would receive the item. This mechanism is known as the Vickrey-Clarke-Groves or VCG mechanism. It provides incentives to report true values for virtually any sort of problem. Of course, it also has flaws. For example, it does not typically generate the maximum amount of revenue for the seller.

search engine ad auctions

Google, MSN, and Yahoo! all use an auction to sell ad space on their search engines. Advertisers bid for positions on a search results page with the highest bidder receiving the most prominent position. The second highest bidder gets the second most prominent position and so on. Each advertiser pays a price per click based on the bid of the advertiser below him or her.

It turns out that there is no dominant strategy in this game when more than two positions being auctioned off. However, it is possible to find outcomes that are “stable” in the sense that no agent wants to change his or her bid, given the bids of the other advertisers.

Designing online auctions has been an evolutionary process, says Alvin Roth, an economist at Harvard University. “Google’s design came out of some earlier designs, and getting the right design has been an important part of its success,” he says. “It has helped create a market that didn’t exist before.”

Distributed algorithmic mechanism design offers an interesting theoretical framework for incorporating incentives into algorithmic design. It also offers exciting opportunities for interdisciplinary collaboration as well as being highly relevant to important practical problems, such as auctioning off the popular 700MHz frequencies.

 

hal R. Varian is the chief economist of Google.

Berkeley, CA-based science and technology writer Erica Klarreich provided additional reporting.

Information Technology
Video
Search,
Intel Style

Researchers at Intel labs in China and the U. S. are developing a video search technology that will enable users to search images in videos by person and object. Intel’s video search technology divides videos on a frame-by-frame basis and uses image and face-recognition software to identify and categorize faces, voices, objects, locations, and movements. Next, the videos are reassembled to facilitate video search.

With Intel’s video search technology, users will no longer have to fast forward through or watch an entire video, but can instantly cut to a particular scene or scenes. In addition to enabling users to instantly analyze videos, Intel’s objective is to create a visual computing platform in which people can interact with a personal computer in a life-like, 3D environment.