review articles
Doi: 10.1145/1435417.1435435
Economic and social sciences will drive
Internet protocols and services into the future.
By Joan fEiGEnBaum, DaViD c. PaRKEs, anD DaViD m. PEnnocK
four areas of computation in which incentives play a crucial role: resource allocation, knowledge integration, peer
production and interaction, and security and privacy.
Resource allocation
computational
Allocating scarce resources—from
bread to bytes—is a fundamental process that permeates economics and, indeed, society. Participants declare their
perceived value for the resource and the
challenges in market computes the best (for example,
value-maximizing) allocation and the
prices that participants should pay.
One decentralized prescription for
E-commerce resource allocation is an auction. Classical 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 support much richer and more flexible
mechanisms. Governments use auctions to allocate property rights such as
wireless spectrum (with worldwide proceeds 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. Generalized combinatorial
12
auctions with rich and natural forms
of expressiveness—volume discounts,
side constraints, and bundling requirements, among others—are used to determine 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.
30
Advertising is a business based on
allocating attention, one of the scarcest
and most valuable of resources. Media
companies capture attention by providing 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 of
