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