NEW Accepted papers and schedule can be found here
Implementation theory (or Mechanism Design) deals with the question whether a principal facing
a decision that depends on non-public information, held by one or several agents, can set up a game
that results in the desired decision in equilibrium. An implementation problem is characterized primarily
by a set of alternatives, preferences of agents over these alternatives (in particular restrictions
on preferences, e.g., when monetary transfers are allowed the standard assumption of quasi-linear
utility is a restriction), information and beliefs both the agents and the principal have about their
values over alternatives and others values over the alternatives. A solution approach starts with
making choices on the family of games that are allowed and the equilibrium concept to be used.
In this context, algorithmic mechanism design has focused mostly on models with private information,
revelation mechanisms with monetary transfers, and dominant strategy implementation. In
recent years this has been extended by other models. For example, Bayesian implementation has
been considered as an alternative to dominant strategy implementation, and full-information models
have been used to understand the design of adword auctions. Still the scope of models studied is
limited when compared with the scope of models that can be found in economic literature. For
example, economists would very often like to have full implementation, meaning that every equilibrium
implements the desired decision. On the other hand, they might be willing to consider less
demanding information structure, like a state of nature that is unknown to the principal, but known
to all agents. Other examples that got little attention in algorithmic mechanism design are robust
implementation, or implementation with evidence.
On the other hand, questions raised on implementation in quasi-linear settings by the algorithmic
mechanism design community have revived interest in these settings among economists, leading for
example to new results on classifying implementable rules in restricted domains.
The fact that algorithmic mechanism design started with dominant strategy implementation in
a private value model might be attributed to the interest in efficient combinatorial auctions in the
private values model, which can be implemented by VCG payments. But after many successes in
this specific area it feels like a good moment to have a look beyond this particular combination
of assumptions. This workshop intends to bring economists and computer scientists together to
exchange ideas on fruitful directions for (algorithmic) implementation theory.
The goal of the workshop is to inform
economists about structural insights that have been developed while tackling computationally motivated
problems in mechanism design, and computer scientists about the richness of the economic
agenda of implementation theory.
The workshop is part of the ACM Conference on Electronic Commerce (EC'11). EC'11 is
one of the leading conferences on the interface between Computer Science and Economics. The
conference offers on June 5 and 6 tutorials and workshops of general interest to economists and
computer scientists, and proceeds on June 7, 8 and 9 with strictly refereed technical papers. EC'11
is co-located with fifteen other computer science conferences as part of the 2011 ACM Federated
Computing Research Conference. For further information feel free to contact any of the organizers.