Teaching

Die Vorlesung Theoretische Informatik 2 ist ein Pflichtmodul im 4. Semester des Bachelors IT-Systems Engineering am Hasso-Plattner-Institut der Universität Potsdam und setzt die Theoretische Informatik 1 fort und erweitert sie. Hier findet ihr alle Informationen für die Voraussetzungen, die Durchführung sowie die Leistungserfassung der Veranstaltung im Sommersemester 2026. Lehrmaterialien und aktuelle Ankündigungen werden im Moodle veröffentlicht.

Beschreibung

Unser Ziel ist es, die angefangene Algorithmik-Toolbox auszubauen. Gleichzeitig schulen wir dabei das Hantieren mit und schnelle Erfassen von neuen Modellen. Dazu schauen wir uns Algorithmen in diversen Gebieten an:

• Graphalgorithmen befassen sich mit effizienter Erkennung von Strukturen (z. B. kürzeste Wege) in Graphen.

Dabei sind wir darauf bedacht, eine Dualität aufzuzeigen: Auf der einen Seite fragen wir uns häufig, was ist der schnellste Algorithmus, den wir für ein Problem finden können? Auf der anderen Seite möchten wir wissen, ob es mathematisch beweisbar ist, dass es keinen schnelleren Algorithmus geben kann. Daher betrachten wir klassische Modelle und Beweistechniken aus der theoretischen Informatik.

• (Nicht-)deterministische endliche Automaten geben einen Einstieg in das Konzept des Nichtdeterminismus.
• Mittels Polynomialzeitreduktionen lernen wir das klassische P-NP-Problem kennen und können neue Probleme nach diesem Kriterium klassifizieren.

Voraussetzungen

Formal sind keine Voraussetzungen notwendig. Spaß an kniffeligen Aufgaben ist aber eine exzellente Grundlage! Ebenso ist es von Vorteil, mit den Inhalten aus Mathematik 1 und 2 (wie Aussagen-/Prädikatenlogik, Analysis, Landau-Notation, formales Beweisen) und Theoretische Informatik 1 vertraut zu sein.

Organisation

Die Verwaltung der Veranstaltung geschieht über das HPI Moodle. Dort könnt ihr euch mit eurem regulären HPI-Login einloggen und für die Veranstaltung eintragen. Die Registrierung im Moodle ist verpflichtend für alle Teilnehmenden, da darüber auch die Verwaltung der Übungsblätter und deren Bewertung läuft.

Wöchentliche Veranstaltungen

• Vorlesung: Dienstags, 11:00-12:30, hybrid in Hörsaal 1 und online (Zugangsdaten im Moodle)
• 7 Tutorien (Start in der zweiten Vorlesungswoche, Details zu den Terminen und Einwahl im Moodle)

Klausurzulassung

Die Endnote dieser Vorlesung wird durch eine Abschlussklausur ermittelt. Es werden zwei Prüfungstermine angeboten.
Erlaubtes Hilfsmittel in der Klausur ist ein beidseitig benutzbares DIN-A4-Blatt als Spickzettel.

Darüber hinaus werden wöchentlich Übungen ausgeteilt. Um zur Klausur zugelassen zu werden, benötigt man 50 % der insgesamt erreichbaren Übungspunkte.

Literatur

• Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. (Für Algorithmik)
• Jeff Erickson's Lecture Notes. (Großartige Sammlung von Material für Algorithmik)
• Kozen: Automata and Computability (Formale Sprachen)
• Neubert: Grundkurs Theoretische Informatik

Description 

Game theory is the mathematical study of strategic interactions, where multiple agents compete to achieve their goals. Since its beginnings in the 1950s, game theory has had a profound influence on economics, political science, and computer science. Its impact has been recognized by numerous Nobel Prizes and top awards in mathematics and computer science. 

In this course, we will take an algorithmic perspective on game theory. We will explore how the computational perspective gives rise to new problems and solutions within game theory and discuss how game theoretical questions contribute to the design of computer systems. In addition, the course will also provide an introduction to a variety of game-theoretic concepts. 

The course will consist of two parts. In part one, we will take the agents perspective and explore the question of how agents behave in a game. The concepts studied in this part will help us answer the following questions:  

• By how much does everyone’s commute time increase because every driver wants to minimize their own commute?
• How can we model and predict how influence spreads in a social network?
• What happens to games like chess when players approach perfect play?
• How can we compute the optimal strategy of an agent in a complex game?
• Under what circumstances should competing parties start to cooperate even though defecting leads to better payoffs in the short term? 

In part two, we will take the perspective of the mechanism (or game) designer and explore the question of how to design the rules of a game in which participants act strategically. The concepts studied in this part will help us answer the following questions:  

• How can we design mechanisms in which all participants are incentivized to tell the truth, even when they are trying to game the system?
• How does Google structure its auctions to maximize revenue despite strategic bidding? 
   

Content  

Part l (The Agent’s Perspective): How do Agents Behave in a Game? 

• Utility Theory and Preferences
• Normal-Form Games
  • Pure strategies
    • Best response dynamics & Nash equilibria (price of anarchy/stability)
    • Finding Nash equilibria: NP-hardness
      • Potential / congestion games
  • Mixed strategies
    • Nash’s theorem & indifference principle
    • Computing Nash equilibria: PPAD
    • Zero-Sum Games: Von Neumann’s minimax theorem
  • Correlated equilibria
• Extensive-Form Games
  • Nash equilibria
    • Backward induction & Zermelo’s theorem
  • Subgame perfect equilibria
    • Alpha-beta pruning & threats
  • Games with imperfect information
  • Iterated games
    • Automata strategies & Nash Folk theorem
• Network-Formation Games and Network Influence/Cascades Models  

Part II (The Designer’s Perspective): How to Design the Rules of a Game? 

• Mechanisms without Money
  • House allocation/kidney exchange: top trading cycles
• Mechanisms with Money
  • Mechanism design
    • First/second price sealed-bid auctions
    • Single-parameter environments: Myerson’s Lemma
    • Multi-parameter environments: VCG mechanisms
    • Online advertising markets/ sponsored search auctions
  • Algorithmic mechanism design: Knapsack auctions
• Prediction markets 

Goal 

The goal of this course is to equip students with a detailed overview of different areas of algorithmic game theory, enabling them to understand current research in parts of the field. Specifically, students will:  

• Get a detailed understanding of a wide array of concepts from game theory and mechanism design.
• Understand the various ways in which computer science has contributed to the study of game theory. For this, students will develop a proficiency in some specialized concepts from theoretical computer science - such as the complexity class PPAD - tailored to understand the algorithmic aspects of game theoretic problems.
• Understand how game theoretic concepts are used in the design of online systems such as ad auctions. 

Prerequisites 

No prior knowledge of game theory is required. However, students should possess solid mathematical and formal reasoning skills to fully engage with the course material. For instance, students should be familiar with the basics of complexity theory, like NP-hardness and reductions (on the level of TI1 and TI2). An interest in exploring new research topics and tackling theoretical challenges is encouraged. 

Exam 

Final Exam: There will be a written exam at the end of the course, which will constitute 100% of the course grade. Students must achieve an average of at least 50% on exercises to qualify for the final exam. However, exercise scores do not contribute to the final grade. 

Exercises: Exercises will be assigned on a (bi-)weekly basis. In addition to traditional problem-solving exercises, there will be reading exercises where you are expected to read parts of a research paper. In addition, there will be few programming exercises where you are asked to program an agent for a game, e.g., a version of the iterated Prisoner’s dilemma. We will let the strategies submitted by you compete against each other. 

Description 

Game theory is the mathematical study of strategic interactions, where agents, e.g., individuals, companies, AI agents, or nations, compete or cooperate to achieve their goals. This course introduces game theory from a computer science perspective, equipping students with formal tools to address a variety of questions pertaining to strategic decision-making, such as: 

• How to model strategic interactions and predict optimal behavior?
  • How do investors decide when to buy or sell stocks based on others’ actions?
• How can suboptimal outcomes arise when everyone plays optimally?
  • Why can building an additional road make everyone’s commute slower?
• How can suboptimal outcomes be overcome?
  • How do repeated interactions foster cooperation in business relationships?
  • How can communication improve coordination in multi-agent systems?
• How to design mechanisms that ensure good outcomes for strategic participants?
  • How does Google structure its ad auctions to maximize revenue despite strategic bidding?
• How can a group coordinate and share generated benefits fairly?
  • How should revenue be split among collaborators in a joint project?
  • What is a fair cost-sharing method for passengers sharing a ride?
• How can we make collective decisions as a group?
  • How should a city allocate public funds based on citizens’ preferences? 

Game theory has influenced economics, political science, and computer science, shaping the design of markets and coordination of multi-agent systems. Its impact is recognized by multiple Nobel Prizes and top awards in mathematics and computer science. 

Content 

The course explores a variety of questions around game theory: 

• How to model strategic interactions and predict optimal behavior?
  • Normal-Form Games
    • Definition + examples
    • Solution concepts: properties and computation
      • Domination, (Mixed) Nash equilibria
  • Extensive-Form Games
    • Definition + examples
    • Solution concepts: properties and computation
      • (Subgame) perfect equilibria, sequential equilibria
• How can suboptimal outcomes arise when everyone plays optimally?
  • Price of Anarchy/Stability
  • Routing games
• How can suboptimal outcomes be overcome?
  • Adding time: Repeated games
  • Adding communication: correlated equilibria and threats
• How to design mechanisms that ensure good outcomes for strategic participants?
  • Auctions
• How can a group coordinate and share generated benefits fairly?
  • Transferable utility cooperative games: core stability & Shapely value
• How can we make collective decisions as a group?
  • Social Choice: voting rules, axiomatic characterization, strategyproofness 

Goals 

The primary goal of this course is to equip students with a solid foundation in game theory, enabling them to formally model strategic interactions and analyze them using appropriate game-theoretic tools. Specifically, students will: 

• Obtain an understanding of fundamental game-theoretic models and solution concepts.
• Analyze how strategic behavior influences outcomes in multi-agent settings.
• Explore techniques for designing mechanisms and systems that account for strategic behavior. 

Prerequisites 

Students should possess basic mathematical knowledge and should have an interest in formal arguments. No specific advanced knowledge is needed, and all new concepts will be covered in the lecture. 

Workload 

There will be one 90-minute slot for the course each week, which will be filled by a mix of lectures and exercise sessions. 

Exam 

Final Exam: There will be a written exam at the end of the course, which will constitute 100% of the course grade. To participate in the final exam, students must achieve an average of at least 50% on the exercises. However, exercise scores do not contribute to the final course grade. 

Exercises: Exercises will be assigned on a (bi-)weekly basis and should be completed in groups. In addition to traditional problem-solving exercises, there will be programming exercises where you will be asked to program an agent for a game, e.g., a version of the iterated Prisoner’s dilemma. We will let the strategies submitted by you compete against each other. 

Beschreibung

Ziel dieses Kurses ist es, Methoden zur Bewältigung verschiedener (mentaler) Herausforderungen im universitären und beruflichen Kontext zu erlernen und die Resilienz der Teilnehmenden gegenüber diesen Herausforderungen zu stärken. Neben der Vermittlung theoretischer Grundlagen liegt der Fokus auf der Erarbeitung und Verinnerlichung praktischer, alltagstauglicher Techniken.

Hierzu kombiniert der Kurs inhaltliche Inputs mit persönlicher Reflexion sowie Diskussionen in (Klein-)Gruppen in denen verschiedene Facetten der behandelten Herausforderungen sowie mögliche Bewältigungsstrategien gemeinsam analysiert und diskutiert werden.

Der Kurs umfasst vier Sitzungen, die jeweils montags am 14.04,12.05, 23.06 und 07.07 von 15:15 bis 18:30 Uhr stattfinden, sowie einen ganztägigen Workshop am 28.06.

Die Kurssprache ist Deutsch.

Inhalte 

Nach einer einführenden Sitzung zu respektvoller Kommunikation und Diskussionsstrategien werden in den folgenden Sitzungen Techniken zur Identifikation und Bewältigung zentraler Herausforderungen im professionellen Kontext erarbeitet:  
 

• Stress und Informationsüberlastung
• Zeitknappheit
• Krisenbewältigung
• Umgang mit Dysfunktionale Gruppen    
• Umgang mit intrinsische und extrinsische Erwartungen
• Selbstbild  und Selbstwahrnehmung
• Optimismus und positive Einstellung 

Im Workshoptag werden wir uns mit Akzeptanz und Kommittentstrategien beschäftigen, die durch achtsamkeits- und akzeptanzbasierte Techniken zur Akzeptanz und Neubewertung von negativen Emotionen führen sollen.

Prüfung

Jede*r Teilnehmende übernimmt die Verantwortung für eines der oben genannten Themen. Dies umfasst:

• Die eigenständige inhaltliche Erarbeitung auf Basis bereitgestellter und selbst recherchierter Quellen.
• Die Erstellung eines maximal dreiseitigen Handouts.
• Die Gestaltung eines 40- bis 60-minütigen Kursbeitrags, bestehend aus einem maximal 30-minütigen inhaltlichen Input und einem interaktiven, moderierten Teil.
• Die Teilnahme an zwei Vorbesprechungen.

Jedes Thema wird von zwei Teilnehmenden gemeinsam bearbeitet, sodass eine enge Abstimmung erforderlich ist.

Zusätzlich ist nach jedem Termin eine kurze Reflektionsumfrage auszufüllen.  
 

This edition of the course has been recorded and is available at tele-TASK

Description 

This module deals with collective decision making, where a group of agents with preferences over alternatives seeks to select a compromise alternative that fairly reflects everyone’s preferences. We focus on three types of collective decision making scenarios: 

1. Voting: Selecting one or more candidates to represent a population of voters based on their preferences over candidates.
2. Resource Allocation: Fairly and efficiently distributing a set of items among agents.
3. Coalition Formation: Dividing agents into teams based on their preferences for different teams. 

The course takes a primarily theoretical approach to these problems, rooted in computational social choice, a field at the intersection of theoretical computer science and economics. We study collective decision making problems from four perspectives, which are all also relevant beyond computational social choice: 

1. Algorithmic: How efficiently can we find a winning alternative?
2. Axiomatic: Can we design an algorithm that satisfies a set of desirable normative properties?
3. Game-theoretic: Can agents strategically manipulate the algorithm/outcome?
4. Experimental: How do different algorithms behave in practice? 

Goals 

The primary objective of this course is to equip students with the skills and knowledge to independently read and understand current research papers in computational social choice. Specifically, students will: 

• Attain an advanced understanding of key concepts and results in various subfields of computational social choice (voting, fair allocation, and coalition formation) and gain insights into current research trends.
• Develop proficiency in the four discussed primary research methodologies employed in computational social choice: algorithmic, axiomatic, game-theoretical, and experimental analysis.
• Build the confidence and capability to independently read, comprehend, and critically engage with current research papers in the field. 

Prerequisites 

Students should possess solid mathematical and formal reasoning skills to fully engage with the course material. For instance, students should be familiar with algorithmic concepts like reductions, dynamic programming, and Integer Linear Programming. An interest in exploring new research topics and tackling theoretical challenges is encouraged. 

Exam 

Final Exam: The planned exam mode is a ~30-minute oral exam, which will constitute 100% of the course grade. An average grade of at least 50% in the exercises is required for students to participate in the final exam but does not contribute towards the course grade. 

Exercises: Exercises will be assigned on a (bi-)weekly basis and will consist of two types: (1) Traditional problem-solving exercise sheets and (2) Readings of (parts of) research papers, accompanied by comprehension questions. 

Content  

The course will consist of three parts: Voting, resource allocation, and coalition formation, where the first part is roughly as long as the other two combined. Covered topics include: 

Voting 

• Single Winner Voting & Rank Aggregation: voting rules, winner determination problem, axiomatic characterizations and impossibility results, manipulation, robustness, other computational problems around elections
• Multiwinner Voting & Participatory Budgeting: Voting rules, winner determination problem, proportionality axioms, transparency, real-world instances
• Applications: clustering, proof-of-stake blockchain, deliberation, LLMs / reinforcement learning from human feedback 

Resource Allocation 

• Divisible Goods: fairness axioms, Robertson-Webb model and query complexity, price of proportionality
• Indivisible Goods: fairness axioms, computing fair allocations 

Coalition Formation/ Cooperative Game Theory 

• Transferable utilities: stability concepts, Shapely value and its applications
• Non-transferable utilities: hedonic games and stable matching, stability concepts, computing stable outcomes