COMP323

Introduction to Computational Game Theory

Aims

to introduce the student to the notion of a game, its solutions concepts, and other basic notions and tools of game theory, and the main applications for which they are appropriate, including electricity trading markets;

to formalize the notion of strategic thinking and rational choice by using the tools of game theory, and to provide insights into using game theory in modeling applications;

to draw the connections between game theory, computer science, and economics, especially emphasizing the computational issues;

to introduce contemporary topics in the intersection of game theory, computer science, and economics;

Syllabus

1

  1. Introduction: Making rational choices: what is a game?, strategy, preferences, payoffs; basic solution concepts; non-cooperative versus cooperative games; Basic computational issues: finding equilibria and learning in games; typical application areas for game theory (e.g. Google''s sponsored search, eBay auctions, electricity trading markets). (4 lectures)
  2. Games with Perfect Information: strategic games (prisoner''s dilemma, matching pennies); Nash equilibria: theory and illustrations (Cournot''s and Bertrand''s models of oligopoly, auctions); information about linear programming; mixed strategy equilibrium; zero-sum games; basic computational issues. (9 lectures)
  3. Extensive Games with Perfect Information: repeated games (prisoner''s dilemma); subgame perfect Nash equilibrium; computational issues. (3 lectures)
  4. Mechanism Design: basics; social choice; Vickrey and VCG mechanisms (shortest paths); combinatorial auctions; profit maximization; applications in Computer Science. (5 lectures)
  5. Modern Applications of Game Theory: Google''s sponsored search; eBay auctions; market equilibria; price of anarchy; prediction markets; reputation systems; electricity trading markets.. (9 lectures)

Recommended Texts

1. M. J. Osborne, An Introduction to Game Theory. Oxford University Press, 2004. ISBN: 9780195128956.

2. N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory. Cambridge University Press, 2007. ISBN: 9780521872829.

Further reading:

3. M. J. Osborne and A. Rubinstein, A Course in Game Theory. MIT Press, 1994. ISBN: 9780262150415.

4. A. Dixit and S. Skeath, Games of Strategy, Second Edition. W W Norton & Co Inc, 2004. ISBN: 9780393924992.

Learning Outcomes

Given a real world situation a student should be able to identify its key strategic aspects and based on these be able to connect them to appropriate game theoretic concepts;

A student will understand the key connections and interactions between game theory, computer science and economics;

A student will understand the impact of game theory on its contemporary applications, and be able to identify the key such application areas;

Learning Strategy

Lectures

Tutorials

Students will be expected to attend three hours of formal lectures in a typical week. In addition, for one hour per fortnight, students will work, under guidance, in practical sessions.  Students will be expected to devote six to seven hour of unsupervised time per week to  private study. This will include time for reflection and consideration of lecture material, background reading, and the completion of practical exercises and continuous assessment tasks. Continuous assessment will be used to test the extent to which students have understood the concepts introduced in the lectures and are able to connect them to real world situations. A written examination at the end of the module will assess the academic achievement of students.