occur online, computational considerations in mechanism design are taking
on a growing significance. Distributed
algorithmic mechanism design, or
just algorithmic mechanism design, is
emerging as a field in its own right.
“Mechanism design is one of the
major intellectual interfaces between
computer science and economics, as
well as one of the most vibrant areas of
economics,” says Christos Papadimitriou, a computer scientist at the University of California, Berkeley.
for your consideration
Broadly speaking, there are two main
strands in the literature. The first involves bringing computational considerations to the economics mechanism
design literature. The second involves
bringing incentive considerations to
the computer science literature.
As an example of the first issue,
consider the recent spectrum auction
by the Federal Communications Commission mentioned earlier. In this auction, the right to use spectrum in various locations was sold to mobile phone
companies and other potential users.
The valuation that a buyer places on
spectrum in a particular location may
depend strongly on whether or not it
wins spectrum in other locations.
In theory, each buyer could assign a
different value to each possible subset
of the geographic locations being sold.
How does one design an auction that
will yield reasonable outcomes in such
a “combinatorial auction”? In such
auctions, it turns out that the so-called
“winner determination problem” is,
in general, NP-complete. However,
researchers working in algorithmic
mechanism design have discovered
various approximation algorithms and
special cases that allow for reasonably
good solutions in practical examples.
As an example of the second issue,
consider the famous “stable marriage
problem” in which one wants to design
an algorithm to match up men and
women. Each man has a ranking over
the women, and each woman has a
ranking over the men. A stable assignment is one such that no couple would
prefer to leave their current mates to
form a new couple. Although this particular description may sound somewhat frivolous, there are much more
serious examples, such as matching
a good starting
point for studying
distributed algorithmic
mechanism design
is a simple auction.
up hospitals and residents or organ
donors and recipients.
It turns out that stable assignments
always exist, and there are a number of
algorithms that compute them. However, these algorithms assume that the
participants are truthfully revealing
their rankings. Do they actually have
the appropriate incentives to do so?
It turns out that some algorithms provide such incentives to men, and some
provide such incentives to women, but
there is no algorithm that provides incentives for both sides of the market to
be truthful.
Ideas from economics can shed
light on many computer science problems that arise from user interactions,
such as computer viruses and spam,
says Preston McAfee, a researcher at
Yahoo! Research in Burbank, CA. “I
think there’s a growing recognition
that problems of bad behavior are incentive problems in the realm of game
theory, rather than technological problems in the realm of traditional computer science,” he says.
Understanding the effect of incentives on how algorithms perform is
“the latest and most momentous twist”
on the question of computation’s limits, Papadimitriou says.
“With classical algorithms, you get
your inputs and then compute away,
and the answer comes out,” he says.
“In this new context, you have to get
your inputs by peering into the souls of
selfish agents trying to promote themselves.”
a simple auction
A good starting point for studying distributed algorithmic mechanism design is a simple auction. A seller has
one item to sell and n buyers have values
v1, … , vn for this item. The seller may
have a reserve price r, which is the minimum price at which he is willing to sell
the item. Typically there will also be a
bid increment, the minimum amount
by which a bid may be changed.
The goal is to design an online auction that will achieve some desired
goals. There are many types of auctions
that could be used. They include:
English auction. The seller starts at
r and progressively raises the price by
the bid increment until all but one of
the buyers drops out. This is the most
common form of auction.
Dutch auction. The seller starts at
a high price and progressively lowers
the price by the bid increment until
a buyer shouts out “buy.” This sort of
auction is used to sell flowers in the
Netherlands.
First-price sealed bid. The buyers
write down a bid and seal it in an envelope. The envelopes are opened and
the item is awarded to the highest bidder at the price he or she bid. This form
is commonly used for construction
contracts.
Second-price sealed bid. The buyers
write down a bid and seal it in an envelope. The envelopes are opened and
the item is awarded to the highest bidder at the second-highest price. This
auction was used by stamp collectors
in the 19th century to sell stamps by
mail.
It turns out there are some relationships among these auctions. For example, with fully rational players, the
outcome of the English auction is the
same, up to the bid increment, as the
outcome of the second-price sealed
bid auction. This is, perhaps, not so
surprising upon reflection, as the English auction ends up awarding the item
to the bidder who is willing to go the
highest, but he or she only has to pay
the bid of the second highest bidder
plus a possible bid increment.
To make the argument slightly
more precise observe that the payoff to
a bidder with value v1 is v1 – b2 where b2
is the bid of the second-highest bidder.
There are three cases to consider:
˲ v1 > b2. In this case bidder 1 wants
to win. But the bidder can do so by reporting b1 = v1.
˲ v1 < b2. In this case bidder 1 wants
to lose. But the bidder can so by reporting b1 = v1.