Algorithmic Game Theory

Game theory is the formal study of interaction between “self-interested” entities (aka “agents”, or “decision makers”, or “players”), and strategic scenarios that arise in such settings. It began life in Economics in the 1940’s with the work of von Neumann and Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology and even to inspection regimes for arms control. Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification and model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics and computing have received extensive attention. These include electronic auctions, and more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet. Wherever game theory plays a quantitative role, algorithmic and computational questions related to “solving” games are also of central importance.

This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. In particular, some of the topics that are covered by this course are the following:

Combinatorial games: Basic arithmetic and solvability.
Game representations: Normal-form (a.k.a. strategic) and extensive-form Games.
Solution concepts for strategic and extensive-form games.
Algorithms and Complexity of constructing (exact/approximate) Solutions, with emphasis on bimatrix games.
The effect of incomplete information on extensive-form games.
Bargaining games.
Mechanism design.
Voting systems.

Course ID

CEID_NE509

Department

Division of Applications and Foundations of Computer Science

Level

Undergraduate

Professor

KONTOGIANNIS SPYRIDON

Semester

Spring

ECTS

5

Website Course Outline

SYLLABUS

Combinatorial Games: Definitions, solution methods for impartial combinatorial games (NIM-heaps arithmetic, MEX-rule). Extensive-Form Games: Game-tree representation, complete/incomplete information games, games with perfect recall. Strategic Games: Zero-sum games, mixed strategies, best response strategies, dominant strategies, Nash equilibria, correlated equilibria, approximate equilibria. Algorithms and complexity for computing one/all Nash equilibria (enumeration methods, upper-envelope method, Lemke-Howson, etc.) for bimatrix games. Definition and efficient computation of MAXMIN strategies. Negotiations: Modelling as repeated games, with payoff discounting. Axiomatic characterization and efficient computation of Nash bargaining solutions. Mechanisms: Design of truthful mechanisms. Gibbard-Shatterthwaite Theorem. Auction theory. Vickrey auctions. VCG mechanisms. Generalized second-price auctions. Congestion games: Modelling as potential games. Evaluation methods for Price of Anarchy/Stability. Network design games. Voting theory: Voting rules (majority, veto, Borda, dictatorship). Arrow’s Theorem.