Computational Game Theory

Objectives

The aims of the course are:

  • To introduce the student to the notion of game, its various solution concepts, and other basic notions and tools of game theory, as well as the main application areas in which they apply;
  • To formalise the notion of strategic thinking and rational choice using the tools of game theory, and to provide insights into adopting game theory in modelling applications.
  • To establish the links between game theory, computer science and economics, with an emphasis on the computation aspects.
  • To introduce contemporary topics in the intersection of game theory, computer science and economics.

General characterization

Code

11564

Credits

6.0

Responsible teacher

João Alexandre Carvalho Pinheiro Leite

Hours

Weekly - 4

Total - 52

Teaching language

Português

Prerequisites

JAVA programming.

Bibliography

Yoav Shoham and Kevin Leyton-Brown , Essentials of Game Theory: A Concise Multidisciplinary Introduction, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2008.

Yoav Shoham and Kevin Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009.

Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, 2007.

Teaching method

Available soon

Evaluation method

This course has two forms of assessment: by midterms and by final exam. Both forms include a theoretical-practical assessment component (70%) and a practical assessment component (30%).

Any questions regarding the interpretation of the following rules should be placed in a timely manner to the lecturer.

Sumative Evaluation Component

The summative evaluation component consists of assessing the participation of students in the lab classes, marked on an integer scale of 0-20 points, including a) attendance, b) participation, dedication and results obtained in the various activities of the lab classes, c) answer to quizes.

Frequency is obtained by anyone who has a mark of 10 points or greater in the summative assessment component. It is a necessary (but not sufficient) requirement to obtain at least 10 values in the summative assessment component – hence to obtain frequency - to be present in at least 8 lab classes.

Theoretical-Practical Assessment Component

The Theoretical-Practical assessment component can be obtained by performing two tests (assessment by midterms) or the final exam (assessment by final exam).

Test and exam dates will be posted on CLIP.

Approval and Calculation of Final Mark

Are approved in the course those who obtain frequency and a mark equal or higher than 9.5 in the theoretical-practical assessment component.

The final mark is given by the weighted average of the theoretical-practical assessment component (70%) and the practical assessment component (30%), rounded to the nearest integer.

Mark Improvement

The improvement mark is calculated as described above, and the student can choose to improve the theoretical-practical component and / or the practical component (this last one only for students of previous editions), everything being governed by the same rules and deadlines of the current edition. The final mark is always calculated taking into account the theoretical-practical and practical components.

Subject matter

Game Theory

Utility Theory, Games in Normal-Form, Pareto optimality, Best response and Nash equilibrium, Mixed Strategies, Maxmin and Minmax, Correlated Equilibrium, Perfect-Information Extensive-Form Games, Subgame Perfection, Backward Induction, Imperfect-Information Extensive-Form Games, Perfect Recall, Repeated Games, Infinitely Repeated Games, Bayesian Games.

Mechanism Design

Social Choice, Voting, Voting Paradoxes, Arrow''''''''''''''''''''''''''''''''s Theorem, Muller-Satterthwaite Theorem, Mechanisms with money, VCG mechanism, Auctions, Mechanisms without Money.

Programs

Programs where the course is taught: