Tutorials

There will be a tutorial day at CWI on December 9, 2015. The three tutorials will be given by:

• Vincent Conitzer, Duke University, USA
• Tobias Harks, Maastricht University, The Netherlands
• Rahul Savani, University of Liverpool, UK

See below for more information.

Tutorial Program

The tutorials will be held in the Turing room (congress hall next to CWI).

Tutorial by Vincent Conitzer

Instructor: Vincent Conitzer, Department of Computer Science, Duke University, USA

Title: Some Game-Theoretic Aspects of Voting

Abstract: The Gibbard-Satterthwaite theorem and related results rule out the existence of appealing strategy-proof voting rules in sufficiently general settings. As a result, it is sometimes thought that approaching voting settings from a game theory or mechanism design viewpoint is futile. In this tutorial I hope to dispel this thought by discussing a variety of game-theoretic results in voting settings.

Tutorial by Rahul Savani

Instructor: Rahul Savani, Department of Computer Science, University of Liverpool, UK

Title: Polymatrix Games: Algorithms and Applications

Abstract: Polymatrix games are multi-player games that capture pairwise interactions between players. They are defined by an underlying interaction graph, where nodes represent players, and every edge corresponds to a two-player strategic-form game. This tutorial will introduce polymatrix games and their applications, such as to model Bayesian two-player games, to solve classification problems in machine learning, and within an iterative method to solve general multi-player games. Then the tutorial will cover basic algorithmic and computational complexity results for polymatrix games. In particular, the tutorial will cover in detail two algorithms for polymatrix games:

1. Lemke's algorithm, with is a complementary pivoting algorithm like Lemke-Howson algorithm for bimatrix games. It can be used to find an exact equilibrium of a polymatrix game.

2. A gradient-descent based algorithm that finds a constant approximate equilibrium of any polymatrix game. A similar technique also gives the current best algorithm for finding approximate equilibria in bimatrix games.

Tutorial by Tobias Harks

Instructor: Tobias Harks, Department of Discrete Mathematics, University of Augsburg, Germany

Title: Polymatroids in Congestion Games

Abstract: Up to day congestion games have been used as reference models for describing decentralized systems involving the selfish allocation of congestible resources and for decades they have been a focal point of research in algorithmic game theory, operations research and theoretical computer science.

In this tutorial, I will convey known and new results regarding the existence, efficiency and computability of equilibria for different variants of congestion games. In particular, we will discover that the theory of congestion games has deep connections with matroid- and polymatroid theory (coming from combinatorial optimization).