Algorithmic aspects of game theory
General data
Course ID: | 1000-2M02AA |
Erasmus code / ISCED: |
11.303
|
Course title: | Algorithmic aspects of game theory |
Name in Polish: | Algorytmiczne aspekty teorii gier |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science |
ECTS credit allocation (and other scores): |
6.00
|
Language: | English |
Type of course: | elective monographs |
Short description: |
Game theory was initiated by von Neumann and Morgenstern as a mathematical theory of rational behaviour. A game comprises description of possible moves and payoffs for each of the players. Typically, each player searches for a strategy maximizing her payoff. The rational behaviour of players is well described by the concept of Nash equilibrium. |
Full description: |
Game theory was initiated by von Neumann and Morgenstern as a mathematical theory of rational behaviour. A game comprises description of possible moves and payoffs for each of the players. Typically, each player searches for a strategy maximizing her payoff. The rational behaviour of players is well described by the concept of Nash equilibrium. Many real-life phenomena can be described by games. In computer science games can model,e.g., processes competing for shared resources, or a system interacting with environment. In economy, games model behaviour of market, and in sociology behaviour of social groups. The course will present the basic concepts of game theory including the Nash equilibrium, games with perfect or imperfect information (like chess or bridge, respectively), zero-sum games, social choice theory (e.g., voting), and auctions. We will give special attention to infinite games on graphs, which have been proposed for use in computer-aided verification, and are connected to automata theory. Computing the winning or optimal strategies in such games constitutes a challenging open problem in algorithmics. |
Bibliography: |
Guillermo Owen, Game theory, Emerald Group Publishing Limited; 3rd edition, 1995, Philip D. Straffin, Game Theory and Strategy, The Mathematical Association of America, 1996, E. Graedel, W. Thomas, and T. Wilke, Automata, Logics, and Infinite Games, Lecture Notes in Computer Science 2500, Springer 2002. N.Nisan, T.Roughgarden, E.Tardos, V.Vazirani eds., Algorithmic Game Theory, Cambridge U.Press, 2007. |
Learning outcomes: |
Knowledge Student 1. recognizes both extensive-form games and strategic games and understands the concepts of determinacy and equilibria proper to both cases, 2. learns the theorems about the determinacy of some relevant games (e.g. parity games), and the existence of a Nash equilibria, and understands the algorithmic consequences of these results, 3. learns algorithms applicable to extensive games, including infinite games and mean-payoff games; learns the problems related to computational complexity of such games, 4. learns algorithmic difficulty of finding the Nash equilibria, and the Lemke-Howson algorithm. Skills Student is able 1. to find a mathematical structure behind social games, and construct algorithms solving such games, 2. to adapt the learned techniques to solve infinite games with various winning conditions, 3. to model some informatics situation in terms of games, 4. to implement at least one method of finding the Nash equilibrium. Competence Student 1. understands the increasing role of games in modeling informatics scenarios, especially those related to distribution and interaction, like e.g. Internet and social networks, |
Assessment methods and assessment criteria: |
The exam consists of solving some number of problems within an indicated term (usually a few days). In the case of completing the course by a doctoral student, the student will prepare a short report proposing some original research problems related to the course and relevant literature. A chat with a lecturer about the report will be a part of the exam. |
Classes in period "Summer semester 2023/24" (in progress)
Time span: | 2024-02-19 - 2024-06-16 |
Navigate to timetable
MO TU WYK
CW
W TH CW
CW
FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Damian Niwiński | |
Group instructors: | Antonio Casares Santos, Kacper Kluk, Damian Niwiński | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Summer semester 2024/25" (future)
Time span: | 2025-02-17 - 2025-06-08 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Damian Niwiński | |
Group instructors: | Kacper Kluk, Damian Niwiński | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.