Computational Game Theory

Level of course

Quarter

Q2 in 2010/2011

Hours per week

Lectures (2+2h/week)

Name of lecturer(s)

Peter Bro Miltersen

Compulsory program

Three compulsory assignments of a theoretical nature

Objectives of the course

The participants will after the course have insight into into two-player zero-sum games in strategic and extensive form, into finitely presented games with infinite strategy spaces, in particular Shapley's stochastic games and Everett's recursive games, into solution concepts for such games, into algorithms for finding solutions, and into normative applications of these algorithms.

Prerequisites

Optimization, Combinatorial Search

Learning outcomes and competences

The participants must at the end of the course be able to:

define and describe basic elements of game theory; types of games, solution concepts and their properties, with a focus on the two-player zero-sum case.
describe and prove basic mathematical properties of the solution concepts.
describe and analyze known algorithms for computing the solutions.
discuss

Types of games: Two-player zero-sum games in strategic form. Two-player zero-sum games in extensive form, with and without perfect information. Deterministic graphical games. Stochastic and recursive games, discounted and undiscounted. One-player stochastic games (Markov decision processes). General sum games (to put zero-sum games into perspective). Solution concepts: Pure and mixed strategies, behavior strategies, stationary strategies. Minimax concept. Dominance. The Nash equilibrium concept and refinements. Algorithms Linear programming for solving game in strategic form. Sequence form method for solving games in extensive form, with variants for equilibrium refinements. The randomized alpha-beta algorithm for solving perfect information games. The retrograde analysis algorithm for solving deterministic graphical games. Value iteration and strategy iteration algorithms for solving stochastic and recursive games. Random facet algorithm for solving stochastic games with perfect information. Algorithms for solving stochastic games based on non-linear mathmematical programming and semi-algerbraic geometry. .

Literature

Notes

Course homepage

http://www.cs.au.dk/~bromille/CGT10/

Type of course/teaching methods

Lectures and exercises

Assessment methods

Oral exam without preparation
7-scale, internal examiner

Credits

5 ECTS

Language

Danish or English

Provider

Department of Computer Science

Course enrolment

http://www.brics.dk/~mis/enrollment.html

Special comments on this course

Schedule for this course

bromille@cs.au.dk