Inf-AGT
Algorithmische Spieltheorie
Algorithmic Game Theory
Dr. Lasse Kliemann
6
30 h lectures, 80 h self study, 40 h exercise preparation, 30 h exercise sessions
Englisch
<p>
Algorithmic Game Theory plays at the intersection of Game Theory and Computer Science. On the one hand, we consider algorithmic questions from Game Theory, such as the computation of equilibria. On the other hand, we consider a game theoretic analysis of questions arising in Computer Science, such as how a computer system will perform when utilized by multiple non-cooperative users.
</p>
<p>
This module will enable the student
to understand current research literature in Algorithmic Game Theory
and thus to write a Bachelor's or Master's thesis in this field.
</p>
<ul>
<li>
Pure and mixed Nash equilibria, existence results
</li>
<li>
Computation of Nash equilibria in general strategic-form games, complexity theory
</li>
<li>
Congestion games: structural properties, computation of equilibria, quantitative analysis of the inefficiency of equilibria (price of anarchy)
</li>
<li>
Network formation: modelling, existence and computation of equilibria, price of anarchy
</li>
<li>
Infinitely many players: variational inequalities, potential function, price of anarchy in point-to-point and multicast routing
</li>
<li>
Extended equilibrium concepts
</li>
</ul>
<p>
(Mathematics for Computer Scientists A and B)
or (Analysis I, II and Linear Algebra I).
Basic skills in Probability Theory, Complexity Theory, and Graph Theory are helpful
but not required.
The necessary basics will be taught on demand in this course.
</p>
<p>
Oral exam.
Exams can be taken as usual at the end of the current lecture period
and at the beginning of the next lecture period.
</p>
<p>
Regular, active participation in exercise sessions is required
in order to be admitted for an exam.
Good performance in the exercise sessions will be taken into account
for the final grade.
</p>
<p>
Comprehensive lecture notes are provided.
The relevant chapters should be read as a preparation for each lecture.
The lectures provide a high-level overview how everything is interconnected;
and most mathematical proofs are presented step by step in full detail.
Written notes made during lectures are recorded electronically
and provided for download.
</p>
<p>
In the exercise sessions, students are requested to present solutions.
Solutions are also provided in beforehand via the lecture notes.
Students may use these example solutions for the presentation.
</p>
<p>
Students are invited to ask questions and to engage in discussions
during the exercise sessions and also during the lectures.
</p>
<p>
This is an optional compulsory module (Wahlpflichtmodul)
for BSc Computer Science.
It is also suitable for MSc Computer Science in the field
"Vertiefende theoretische Grundlagen".
</p>
<ul>
<li>
Lecture Notes, provided at the <a href="http://www.informatik.uni-kiel.de/~discopt/teaching/sommer14/agt.html">website of the module</a>.
</li>
<li>
<em>Algorithmic Game Theory</em>
by Nisan, Roughgarden, Tardos, Vazirani. <a href="http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf">Freely available as PDF</a>.
</li>
<li>
<em>A Course in Game Theory</em>
by Osborne und Rubinstein. <a href="http://books.osborne.economics.utoronto.ca/">Freely available as PDF</a>
(after registration).
</li>
<li>
<em>Multiagent Systems</em>
by Shoham und Leyton-Brown. <a href="http://www.masfoundations.org/download.html">Freely available as PDF</a>.
</li>
<li>
<em>Theory Of Games And Economic Behavior</em>
by von Neumann and Morgenstern. <a href="http://archive.org/details/theoryofgamesand030098mbp">Freely available as PDF</a>.
</li>
<li>
<em>Essentials of Game Theory: A Concise Multidisciplinary Introduction</em>
by Leyton-Brown und Shoham. <a href="http://www.morganclaypool.com/doi/abs/10.2200/S00108ED1V01Y200802AIM003">For $5 available as PDF</a>.
</li>
</ul>
<p>
The language of this module is English.
It can also be held in German,
provided that all of the participants agree.
The lecture notes will always be in English only.
</p>
Bachelorstudiengang Informatik (bis SS15)
Informatik als Nebenfach
Bachelorstudiengang Informatik (ab WS15/16)
Masterstudiengang Informatik (Education)
Masterstudiengang Informatik (Education)
Wahlpflichtmodule Algorithmik (BSc Inf.)
Nebenfach Informatik für Mathematik-Studierende (Inf. als NF)
Wahlpflichtmodule Informatik (BSc Inf. (15))
Wahlpflicht Informatik (MEd Inf)
Wahlpflicht Praktische Informatik (MEd Inf)
2V 2Ü 0P 0S
1
jedes Jahr
SS13
Dr. Lasse Kliemann
SS14
Dr. Lasse Kliemann