70 communications of thE acm | jAnuARY 2009 | voL. 52 | no. 1review articlesfour areas of computation in which in-centives play a crucial role: resource al-location, knowledge integration, peer production and interaction, and secu-rity and privacy. Resource allocation Allocating scarce resources—from bread to bytes—is a fundamental pro-cess that permeates economics and, in-deed, society. Participants declare their perceived value for the resource and the market computes the best (for example, value-maximizing) allocation and the prices that participants should pay.One decentralized prescription for resource allocation is an auction. Clas-sical auctions emphasize simple rules for setting allocations and prices, which can be determined manually. Many of the largest marketplaces in the world, including financial exchanges, are at their core based on these centuries-old procedures. In one week of March 2008, the U.S. treasury sold, largely through manual means, more than $22 billion in three-month treasury bills.Modern computer systems can sup-port much richer and more flexible mechanisms. Governments use auc-tions to allocate property rights such as wireless spectrum (with worldwide pro-ceeds exceeding $100 billion by the end of 2001). Combinatorial auctions allow bidders to express values for bundles of goods—for example, in assigning a higher value to two adjacent properties than the sum of the values assigned to each.12 Generalized combinatorial auctions with rich and natural forms of expressiveness—volume discounts, side constraints, and bundling require-ments, among others—are used to de-termine billions of dollars of spending within the supply chain, even though the problem is NP-hard. For example, they are used to source truckload-trans-portation logistics for Procter & Gamble, Walmart, and Target.30Advertising is a business based on allocating attention, one of the scarcest and most valuable of resources. Media companies capture attention by provid-ing information or entertainment and coMpaNIeS aNd INdIvIduaLS are using computer networks to conduct increasing amounts of their daily business. Web search engines auctioned some $10 billion of ad space in 2007, accounting for almost half of all online advertising revenue. sales at Amazon.com were $4.13 billion in the first quarter of 2008, including a fast-growing revenue stream from selling Web services to other e-commerce companies. At eBay, sales reached $15.7 billion in the second quarter, with 84.5 million active users. This explosion of large-scale e-commerce poses new computational challenges that stem from the need to understand incentives. Because individuals and organizations that own and operate networked computers and systems are autonomous, they will generally act to maximize their own self-interest—a notion that is absent from traditional algorithm design. In this article, we provide an overview ofDoi:10.1145/1435417.1435435Economic and social sciences will drive Internet protocols and services into the future.By Joan fEiGEnBaum, DaViD c. PaRKEs, anD DaViD m. PEnnocKcomputational challenges in E-commercejAnuARY 2009 | voL. 52 | no. 1 | communications of thE acm 71typically sell a fraction of that attention to advertisers.Historically, advertising sales fea-tured straightforward allocation rules and manual negotiations. But now more aspects of advertising, including its sale, delivery, and measurement, are being automated. Web-search engines such as Google and Yahoo! have led the way, selling space beside particular search queries in continuous dynamic auctions worth billions of dollars an-nually.Auctions and exchanges for all types of online advertising—including ban-ner and video ads—are commonplace at present, and they are run by startups and Internet giants alike. Advertisers can buy not only space but also contex-tual events—such as clicks from a spe-cific user on a specific property at a spe-cific time—or, more generally, bundles of contextual events. An ecosystem of third-party agencies has grown to help marketers manage their increasingly complex ad campaigns.The rapid emergence of new modes for selling and delivering ads is fertile ground for research, both from eco-nomic and computational perspec-tives.25 Edelman et al.15 and Varian31 model how advertisers bid in search-ad auctions. Essentially, the advertis-ers raise their bids until they reach a point of indifference between staying where they are and swapping with the advertiser above them on the page. The authors show that this bidding strategy forms the basis of a symmetric Nash equilibrium and, in a nice example where theory aligns with practice, that real bidding behavior is largely consis-tent with the model.A number of questions drive re-search in ad auctions and exchanges. What mechanisms increase advertiser value or publisher revenue? What user and content attributes contribute to variation in advertiser value? How can bids for different contingencies (im-pressions, clicks, or conversions) be integrated and optimized over time? What constraints on supply and budget make sense? How should advertisers and publishers bid? How can publish-ers and advertisers incorporate learn-ing and optimization (while trying to balance exploration and exploitation)? How do practical constraints such as real-time delivery affect design? How is automation changing the advertis-ing industry? More information can be found in the Proceedings of the Work-shop on Ad Auctions series.33Knowledge integrationThe eliciting and aggregation of infor-mation from diverse and frequently self-interested sources is in gener-al called “knowledge integration,” with a particular case being “price discovery”—a side effect of market-based resource allocation. The balance point of supply and demand reveals the negotiated value of the resource.In some cases, the value revealed in prices can rival or eclipse the value of trade. For example, the price of an asset that pays $1 if a category-5 hur-ricane hits Florida in 2009 can be seen as a probabilistic forecast of this cata-strophic event. The value of an actual and more accurate forecast could run into the millions of dollars.A