Faculdade de Ciências e Tecnologia

Computational Game Theory

Code

11564

Academic unit

Faculdade de Ciências e Tecnologia

Department

Departamento de Informática

Credits

6.0

Teacher in charge

João Alexandre Carvalho Pinheiro Leite

Weekly hours

Total hours

Teaching language

Português

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.

Prerequisites

JAVA programming.

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.

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.

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.

Practical Evaluation Component

The practical evaluation component consists of assessing a project, consisting of a set of implementations, accompained by a report, and their usage in a set of games.

Frequency is obtained by anyone who has a mark of 10 points or greater in the practical assessment component.

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.

Courses

Computer Science and Engineering