Das Herbstsemester 2020 findet in einer gemischten Form aus Online- und Präsenzunterricht statt.
Bitte lesen Sie die publizierten Informationen zu den einzelnen Lehrveranstaltungen genau.

252-1407-00L  Algorithmic Game Theory

SemesterHerbstsemester 2017
DozierendeP. Penna
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch



Katalogdaten

KurzbeschreibungGame theory provides a formal model to study the behavior and interaction of self-interested users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory.
LernzielLearning the basic concepts of game theory and mechanism design, acquiring the computational paradigm of self-interested agents, and using these concepts in the computational and algorithmic setting.
InhaltThe Internet is a typical example of a large-scale distributed computer system without central control, with users that are typically only interested in their own good. For instance, they are interested in getting high bandwidth for themselves, but don't care about others, and the same is true for computational load or download rates. Game theory provides a particularly well-suited model for the behavior and interaction of such selfish users and programs. Classic game theory dates back to the 1930s and typically does not consider algorithmic aspects at all. Only a few years back, algorithms and game theory have been considered together, in an attempt to reconcile selfish behavior of independent agents with the common good.

This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. Rather than giving an overview of such developments, the course aims to study selected important topics in depth.

Outline:
- Introduction to classic game-theoretic concepts.
- Existence of stable solutions (equilibria), algorithms for computing equilibria, computational complexity.
- Speed of convergence of natural game playing dynamics such as best-response dynamics or regret minimization.
- Techniques for bounding the quality-loss due to selfish behavior versus optimal outcomes under central control (a.k.a. the 'Price of Anarchy').
- Design and analysis of mechanisms that induce truthful behavior or near-optimal outcomes at equilibrium.
- Selected current research topics, such as Google's Sponsored Search Auction, the U.S. FCC Spectrum Auction, Kidney Exchange.
SkriptLecture notes will be usually posted on the website shortly after each lecture.
Literatur"Algorithmic Game Theory", edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press, 2008;

"Game Theory and Strategy", Philip D. Straffin, The Mathematical Association of America, 5th printing, 2004

Several copies of both books are available in the Computer Science library.
Voraussetzungen / BesonderesAudience: Although this is a Computer Science course, we encourage the participation from all students who are interested in this topic.

Requirements: You should enjoy precise mathematical reasoning. You need to have passed a course on algorithms and complexity. No knowledge of game theory is required.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
ECTS Kreditpunkte7 KP
PrüfendeP. Penna
FormSessionsprüfung
PrüfungsspracheEnglisch
RepetitionDie Leistungskontrolle wird nur in der Session nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich.
Prüfungsmodusschriftlich 180 Minuten
Zusatzinformation zum PrüfungsmodusThere will be 4 exercise sheets that will contribute with a weight of 30% towards the final grade. The total final grade will be a combination of your exercise grade (30%) and your exam grade (70%).
Hilfsmittel schriftlichno supporting material allowed
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.

Lernmaterialien

 
HauptlinkInformation
Es werden nur die öffentlichen Lernmaterialien aufgeführt.

Lehrveranstaltungen

NummerTitelUmfangDozierende
252-1407-00 VAlgorithmic Game Theory3 Std.
Mo09-12CAB G 51 »
P. Penna
252-1407-00 UAlgorithmic Game Theory2 Std.
Mo15-17CAB G 56 »
15-17CAB G 59 »
15-17IFW C 33 »
P. Penna
252-1407-00 AAlgorithmic Game Theory
Project Work, no fixed presence required.
1 Std.P. Penna

Gruppen

Keine Informationen zu Gruppen vorhanden.

Einschränkungen

Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

StudiengangBereichTyp
CAS in InformatikFokusfächer und WahlfächerWInformation
Data Science MasterWählbare KernfächerWInformation
Informatik DZFachwissenschaftliche Vertiefung mit pädagogischem FokusWInformation
Informatik LehrdiplomFachwiss. Vertiefung mit pädagogischem Fokus und weitere FachdidaktikWInformation
Informatik MasterWahlfächer der Vertiefung in Theoretical Computer ScienceWInformation
Informatik MasterWahlfächer der Vertiefung General StudiesWInformation
Mathematik BachelorAuswahl: Theoretische InformatikWInformation
Mathematik MasterAuswahl: Theoretische Informatik, diskrete MathematikWInformation
Rechnergestützte Wissenschaften DZWeitere FachdidaktikWInformation
Robotics, Systems and Control MasterKernfächerWInformation