 2/2, C+Ex, 5 ECredits
 Annotation: An introduction to algorithmic game theory, a relatively new field whose objective is to study formal models of strategic environments and to design effective algorithms for them. This introductory course covers basic concepts and methods that are illustrated with several practical applications. To successfully pass the course, it is recommended to know basics from complexity theory.
 Throughout the winter term, I will keep posting lecture notes about topics covered so far.
 Literature:
 Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic game theory. Cambridge University Press, Cambridge, 2007.
 Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, Cambridge, 2016.
 Kevin LeytonBrown and Yoav Shoham. Essentials of game theory, volume 3 of Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, Williston, VT, 2008.
 Jiøí Matoušek and Bernd Gärtner. Understanding and Using Linear Programming. SpringerVerlag New York, Inc., 2006.
 Lecture notes: see the current run of the course.
 The lecture notes are still under construction. If you notice any mistake or place for improvement, please, let me know by email.

 First lecture (2.10.2019): We agreed on time of the lecture at the schedule of lectures and seminars of KAM and IÚUK.
 Second lecture (9.10.2019):
 Introduction, information about the credit and the exam,
 normalform games, Nash equilibria (pure and mixed), examples of normalform games,
 Nash's theorem and we started its proof using Brouwer's fixed point theorem.
 Third lecture (16.10.2018):
 Proof of Nash's theorem,
 Pareto optimality,
 the Minimax theorem and its proof using the duality in linear programming.
 Fourth lecture (23.10.2019):
 Best response condition,
 best response polyhedra,
 bruteforce algorithm to find all Nash equilibria,
 best response polytopes.
 Fifth lecture (29.10.2018):
 Lemke–Howson algorithm and a proof of its correctness,
 complexity classes FNP and PPAD,
 NASH being FNPcomplete implies NP = coNP (without proof),
 the ENDOFTHELINE problem,
 NASH is PPADcomplete (without proof).
 Sixth lecture (6.11.2019): The lecture was cancelled (and was replaced on Thursday November 28th 2019).
 Seventh lecture (13.11.2019):
 EpsilonNash equilibria,
 quasipolynomial time algorithm for finding epsilonNash equilibria,
 correlated equilibria and their properties (without proofs),
 linear program for finding correlated equilibria.
 Eighth lecture (20.11.2019): The lecture will be cancelled (Open Day).
 Ninth lecture (27.11.2019):
 Regret minimization, introduction of the formal model, external regret,
 large comparison classes cannot yield good bound on external regret,
 greedy algorithm and its cumulative loss,
 randomized greedy algorithm and its cumulative loss,
 polynomial weights algorithm and its cumulative loss.
 Tenth lecture (28.11.2019):
 Noregret dynamics,
 cumulative loss of noregret algorithms in zero sum games is (up to epsilon) at most the value of the game,
 proof of the Minimax theorem using regret minimization,
 coarse correlated equilibria,
 convergence to coarse correlated equilibria with noregret dynamics,
 internal regret and swap regret.
 Eleventh lecture (4.12.2019):
 blackbox reduction producing good bounds on swap regret using algorithms with good bounds on external regret,
 noswapregret dynamics and its convergence to correlated equilibria,
 mechanism design,
 singleitem auctions,
 firstprice auction, Vickrey auction,
 DSIC property, Vickrey auction is awesome,
 singleitem environments, sponsoredsearch auctions.
 Twelfth lecture (11.12.2019):
 Statement of Myerson's lemma,
 applications of Myerson's lemma (singleitem auctions and sponsoredsearch auctions),
 sketch of the proof of Myerson's lemma,
 Knapsack auctions,
 almost optimal greedy algorithm for Knapsack auctions (with a sketch of the proof of correctness).
 Thirteenth lecture (18.12.2019):
 Revenue maximization,
 Bayesian model and expected revenue,
 maximizing expected revenue = maximizing expected virtual social surplus,
 maximizing revenue in singleitem auctions and further extensions,
 revelation principle.
 Fourteenth lecture (8.1.2020):
 Recalling Bayesian model and maximization of expected revenue,
 Bulow–Klemperer Theorem,
 multiparameter environments and their examples,
 VCG mechanism.
