Game TheoryModule description #40824 / Version 1
- 6 CP
- Oral exam
- Graded
- Summer semester
- English, German
| Module / Version | #40824 / #1 |
|---|---|
| Validity | Since SS 2017 |
| Available language(s) | German |
| Credit points | 6 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English, German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | TEL 7-3 |
|---|---|
| Contact person | Rabinovich, Roman |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | http://logic.las.tu-berlin.de/Teaching/ |
Learning outcomes
Knowledge about types of formal games, basic problems and methods to solve them. Knowledge about applications of formal games to economics, logics, automatic verification and synthesis.
Improved skills in working with mathematical proofs and in understanding mathematical notions, definitions and proofs.
Improved skills in working with mathematical proofs and in understanding mathematical notions, definitions and proofs.
Content
- Kinds of games
- Games in extensive and in strategic form
- Reachability and Safety games
- Parity games
- (positional) determinacy
- strategy improvement and progress measure algorithms
- special cases: bounded treewidth, DAG-width, Kelly-width, cliquewidth
- translation from parity games on digraphs to undirected graphs
- Muller, Rabin, Büchi and Streett-Rabin winning conditions
- alternating Turing machines
- non-determinacy of games
- Borel games
- graph searching games
- Cops-and-Räuber games and characterisations by graph decompositions
- Nash equilibria
- two-persons zero-sum games
- regret-minimisation
- iterative elimination of dominated strategies
- Games in extensive and in strategic form
- Reachability and Safety games
- Parity games
- (positional) determinacy
- strategy improvement and progress measure algorithms
- special cases: bounded treewidth, DAG-width, Kelly-width, cliquewidth
- translation from parity games on digraphs to undirected graphs
- Muller, Rabin, Büchi and Streett-Rabin winning conditions
- alternating Turing machines
- non-determinacy of games
- Borel games
- graph searching games
- Cops-and-Räuber games and characterisations by graph decompositions
- Nash equilibria
- two-persons zero-sum games
- regret-minimisation
- iterative elimination of dominated strategies
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Spieltheorie (Informatik) (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Spieltheorie (Informatik) (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
The workload of the module adds up to 180 hours. The module therefore comprises 6 credit points.
Description of teaching and learning methods
- Vorlesung
- Übung
- Selbständiges (oder in kleinen Gruppen) Bearbeiten der Hausaufgaben
- Übung
- Selbständiges (oder in kleinen Gruppen) Bearbeiten der Hausaufgaben
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Kenntnisse aus den Modulen "Berechenbarkeit und Komplexität" und "Logik"
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Type of portfolio examination | 100 points in total |
| Language | English, German |
| Duration/Extent | ca. 25-45 Minuten |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Wird noch bekanntgegeben.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
available – Ein Skript wird vorlesungsbegleitend erstellt.
Recommended literature
No recommended literature given
Assigned programs
This module version is used in the following programs:
| Program / program version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Natural Sciences in the Information Society StuPO 2018 | SS 2025 | Wahlpflichtbereich › Informatik › Weiterführende Module |
| WS 2025/26 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| SS 2026 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| WS 2026/27 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| Natural Sciences in the Information Society Natural Sciences in the Information Society (B. Sc.) - StuPO 2025 | WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
Miscellaneous
Not specified