Algorithmic Mechanism Design: an Introduction
Guido Proietti, University of L’Aquila
Abstract: In traditional theoretical computer science (TCS), computational agents are
typically assumed either to follow the prescribed algorithm, or to play as
adversaries. In game theory (GT), instead, agents are neither obedient nor
adversarial, but rather strategic: Although one cannot assume that they will
follow the prescribed algorithm, one can assume that they will respond to
incentives.
The traditional GT
field of Mechanism Design (MD) addresses the problem of motivating the selfish
agents to behave as the system wishes, when a given collective task has to be
performed. This can be done by corresponding incentives to the agents, in such
a way that their utility (i.e., their preference over the possible output
configurations) is maximized when they behave correctly. These incentives are
prospected to the agents associated with various output scenario. Based on this
trade-off, each agent makes a rational choice by maximizing her personal
utility. However, behind the scene of this economic process, there are TCS
issues (i.e., computational hardness of the underlying problem of selecting the
output, time complexity for computing an (approximate) output and a set of
corresponding incentives, etc.) that cannot be ignored. This is especially true
with the emergence of large-scale non-cooperative systems, like the Internet.
In this introductory
lecture, we will focus exactly on the computational aspects of MD, which is
known today as Algorithmic Mechanism Design. More precisely, we will present
two categories of so-called truthful mechanisms, namely VCG-mechanisms and
one-parameter mechanisms, and we will see their application to the most
prominent (and polynomially solvable) network
optimization problems: the Shortest-Path
problem, the Minimum Spanning Tree problem, and the Shortest-Paths Tree problem. Finally, we will also see an interesting
dichotomy of these two mechanisms w.r.t. a classic (computationally hard)
combinatorial auction problem.
Schedule:
1. (Tuesday January 14, 2014, 11-13): Reviews of basics
of game theory. The implementation problem. An example: second-price auction.
Mechanism design. Strategy-proof mechanisms. Utilitarian problems. VCG
mechanisms. Clarke payments.
Slides: click here
2. (Friday January 17, 2014, 11-13): Computational aspects
of mechanisms. VCG-mechanism for the private-edge Shortest-Path problem.
Trivial implementation and efficient O(m + n log n) time implementation.
Slides: click
here
3. (Tuesday January 21, 2014, 11-13): VCG-mechanism for
the private-edge Minimum Spanning Tree problem. Trivial implementation and
efficient O(m α(m,n)) time implementation.
Slides: click
here
4. (Thursday
January 23, 2014, 16-18): Non-utilitarian,
one-parameter problems. One-parameter mechanisms. One-parameter mechanism for
the private-edge Shortest-Paths
Tree problem. Trivial implementation and efficient O(m + n log n)
time implementation.
Slides: click
here
5. (Friday January 24, 2014, 11-13): Approximate one-parameter mechanisms: the single-minded
combinatorial auction problem.
Slides: click
here