n news
Science | DOI: 10.1145/1378704.1378708
Designing the
Perfect auction
Distributed algorithmic mechanism design is a field at
the intersection of computer science and economics.
IN JANuARy, THE U.S. Federal
Communications Commission (FCC) launched one of
the biggest auctions in history, selling off what some in
the wireless industry have called the
“beachfront property” of the electromagnetic spectrum. Its auction of
the 700MHz frequencies, the largest
and most valuable slice of spectrum
to come available in years, brought in
more than $19 billion.
PHO TOGRAPH BY CHAD BAKER
With the auction, the FCC inaugurated the first use in a major spectrum auction of “package bidding,” in
which bidders are allowed to bid either
on individual state licenses or regional
packages of licenses. Although package bidding makes a lot of sense—for
example, some bidders might be interested in buying state A only if they can
be guaranteed to also get state B—until
now, the FCC had not offered an auction design that gave bidders enough
flexibility while keeping combinatorial and computational complexity in
check.
The auction is a high-profile example of distributed algorithmic
mechanism design, a field that combines economics and algorithm design. Economic mechanism design is
concerned with how to design a market or market-like institution so that
it will achieve a desired goal, such as
allocating goods efficiently, maximizing profit, or achieving an equitable
distribution. Mechanism design is, in
a sense, the inverse of game theory: in
game theory, one is given the rules of
a game and the goal is to predict the
outcome; in mechanism design, one
is given a set of desired outcomes and
the goal is to design a game that will
achieve them.
In 2007, Leo Hurwicz, Eric Maskin
and Roger Myerson were awarded the
Nobel Prize in Economics for their
work in economic mechanism design.
Their theoretical work underpins a
host of practical applications, including eBay’s auctions, the auctions used
by Google and Yahoo! to sell ad slots,
the matching system used to pair
medical residents and hospitals, the
California electric power exchange,
the rules governing trades on NASDAQ
and other financial markets, and, of
course, the FCC spectrum auctions.
As auctions have grown more complex and more economic transactions
