economics.c Evaluating the quality of a mechanism is nontrivial: it requires being able to predict how multiple strategic agents will act in each other’s presence. Game theory provides tools for making such predictions.d (An article about computer science and game theory appeared in the August 2008 issue of Communications. 34)

The standard approach to mechanism design is simply to ensure it is never beneficial for an agent to lie about her preferences. A result known as the revelation principle suggests that this approach is, from the point of view of strategic behavior, without loss of optimality. A mechanism under which it is never beneficial to lie is called truthful. Unfortunately, it turns out that in general voting settings, no good truthful mechanisms exist, by a result known as the Gibbard-Satterthwaite impossibility theorem. 15, 33

For settings such as auctions and exchanges, where payments can be made, there are much more positive results. For one, if our goal is to allocate the resources efficiently, there are rules for specifying how much agents should pay that make the mechanism as a whole truthful.

A simple example of such a payment rule is the second-price sealed-bid auction for a single item. In this auction, the bidder with the highest bid wins, but only pays the second-highest bid. As a result, the winning bidder’s bid does not affect the price she pays; so the only effect that misreporting her valuation for the item can possibly have is that she does not win, which would make her worse off. Similarly, the only effect that misreporting can possibly have for a losing bidder is that she ends up winning at a price that is too high for her, which would make her worse off. So, a bidder is always best off reporting her true valuation for the item—that is, the second-price sealed-bid auction is truthful. This scheme can be generalized to combinatorial auctions and exchanges (and other settings), resulting in the class of Vickrey-Clarke-Groves (VCG) mechanisms. 7, 16, 36

 

c In 2007, Hurwicz, Maskin, and Myerson received the Nobel Prize in Economics for their fundamental work on mechanism design.

d Game theory has led to two other Nobel Prizes in Economics: Nash, Selten, and Harsanyi received one in 1994, and Aumann and Schelling in 2005.

The issues studied in mechanism design interact with the computational issues I discussed before in subtle ways. For example, suppose we want to run a combinatorial auction using a VCG mechanism. Technically, this means we should always solve the winner determination problem to optimality, that is, find the most efficient allocation—which we know is NP-hard. If we do not always succeed at finding the most efficient allocation, then the resulting mechanism will, in general, not be truthful. A significant amount of research has addressed the problem of designing polynomial-time approximation algorithms that, in combination with the right payment rule, are truthful. 21 More generally, the problem of designing efficient algorithms that can be made truthful is the main topic of algorithmic mechanism design. 24 This line of research has also been extended to distributed settings without a trusted center. 13

We can use computers not only to run existing mechanisms, but also to design new mechanisms from scratch. That is, for a given setting, we let an algorithm search through the space of all possible truthful mechanisms for an optimal one. 9 This approach is called automated mechanism design. Finding an optimal mechanism is computationally much harder than running an existing mechanism, and as a result automated mechanism design has so far been successful only on small instances. Nevertheless, some real instances are in fact small, and even for larger instances, solving a simplified version can give some helpful intuition. Automated mechanism design can also be used to solve some small instances of a general mechanism design problem; then, a human mechanism designer can try to identify a pattern in these small solutions, conjecture the general solution, and prove it analytically. In this way, automated mechanism design can contribute to microeconomic theory. This methodology has recently been used to design mechanisms for redistributing an auction’s revenue to the bidders in a truthful way (for example, Guo and Conitzer17), and the methodology is starting to be adopted more widely.

It is not always the mechanism de-
signer or the party running the mecha-
nism that faces hard computational
problems. Under some mechanisms, it
is computationally hard for the agents
to find the strategically optimal action
to take. This is not the case for truthful
mechanisms, where strategically opti-
mal behavior simply means telling the
truth. However, no reasonable voting
rule is truthful in sufficiently general
settings (by the Gibbard-Satterthwaite
theorem mentioned above). It has been
shown that in a variety of voting set-
tings, it is NP-hard to find the strategi-
cally optimal vote(s) to cast, even if the
other agents’ votes are already known
(for example, Bartholdi, 2 Conitzer, 11
and Hemaspaandra18). This is a case
where computational hardness can
be desirable: it can be argued that if a
voter cannot find a way of misreporting
her preferences that benefits her, then
she will presumably tell the truth. For
now, the impact of this type of result is
limited by the fact that NP-hardness is
a worst-case measure, and it may well
be the case that it is easy to find an ef-
fective way of misreporting one’s pref-
erences most of the time.