Sergey Nikolenko
Main pageBooks';
print '
Research papers';
print '
Talks and posters';
print '
Students';
print '
Popular science';
print '
Other stuff';
print '
Research';
print '
CS and crypto';
print '
Bioinformatics';
print '
Machine learning';
print '
Algebraic geometry';
print '
Algebra';
print '
Bayesian networks';
print '
Earth sciences';
print '
Teaching';
print '
2014';
print '
ML, KFU';
print '
Game Theory, HSE';
print '
Mech. Design, HSE';
print '
ML, CSClub Kazan';
print '
Game theory, HSE';
print '
Math. logic, AU';
print '
Machine learning, STC';
print '
Machine learning, AU';
print '
2013';
print '
Discrete math, HSE';
print '
Machine learning, STC';
print '
Math. logic, AU';
print '
Cryptography, AU';
print '
2012';
print '
Machine learning, STC';
print '
Math. logic, AU';
print '
Machine learning II, AU';
print '
Machine learning, AU';
print '
Machine learning, EMC';
print '
2011';
print '
Cryptography, AU';
print '
Math. logic, AU';
print '
Machine learning, AU';
print '
2010';
print '
Math. logic, AU';
print '
Machine learning, AU';
print '
Cryptography, AU';
print '
2009';
print '
Crypto in CS Club';
print '
Statistics';
print '
Machine learning, AU';
print '
Cryptography';
print '
2008';
print '
Speech recognition';
print '
MD for CS Club';
print '
ML for CS Club';
print '
Mechanism design';
print '
2007';
print '
Machine Learning';
print '
Probabilistic learning';
print '
External links';
print '
Google Scholar profile';
print '
DBLP profile';
print '
LiveJournal account
nikolenko (in Russian)
Teaching activities
Mechanism design
In the spring of 2008 I'm teaching the "Mechanism design" course. Inspired by Anton Likhodedov, the course is being prepared with his help and financial support.The course materials (all slides and lecture notes are in Russian):
- 1. Introduction. Game theory, fun examples, basic definitions and concepts of game theory and mechanism design.
- Slides ()
- Lecture notes by A. Yakushev and M. Churakov ()
- 2. Analyzing two common auction models. The revelation principle. The revenue equivalence theorem and its corollaries.
- Slides ()
- Lecture notes by P. Raikov and K. Egorov ()
- 3. Efficient and optimal mechanisms. Vickrey–Clarke–Groves mechanism. Arrow–d'Aspremont–Gerard–Varet mechanism.
- Slides ()
- Lecture notes by I. Lagunov and E. Mandrikov ()
- 4. Worst-case mechanism design. Suboptimal mechanisms and benchmarks. Deterministic Optimal Price auction. Random Sampling Optimal Price auction and its optimality analysis.
- Slides ()
- Lecture notes by Ju. Beliaeva and E. Kurbatskiy ()
- 5. Lower bounds on worst-case optimality. Online auctions. Reduction to expert learning and Kalai algorithm.
- Slides ()
- Lecture notes by O. Kanzheleva ()
- 6. Impossibility results. The Arrow impossibility theorem and the Gibbard-Satterthwaite theorem. Hurwicz impossibility theorem (without proof). The Myerson-Satterthwaite impossibility theorem for bilateral trade and its generalization by Williams.
- Slides ()
- Lecture notes by V. Kulev and M. Dvorkin ()
- 7. Combinatorial auctions. Combinatorial VCG. Single-minded buyers model. O(\sqrt{M})-optimal auction (LOS) and its detailed optimality analysis.
- Slides ()
- Lecture notes by D. Kulagin, G. Rybakov, and A. Suslov ()
- 8. Auctions with interdependent values. Affiliated random variables. Three auction models with interdependent values. Revenue comparisons between the three models.
- Slides ()
- Lecture notes by I. Akishev ()
- 9. The linkage principle. Its application to discerning public information. Possible asymmetries in the buyers. Counterexamples: how revenue rankings and public information does not extend to the asymmetric case. Asymmetric equilibria.
- Slides ()
- 10. VCG is infeasible. But feasible suboptimal algorithms are irrelevant: any suboptimal auction is unreasonable and degenerate. In general, life is very tough unless P=NP.
- Slides ()
- Lecture notes by A. Mordvincev, D. Trofimov, and R. Naumov ()
- 11. Nisan & Ronen's second chance mechanisms. How to provide incentives for truthfulness if an optimal solution is infeasible.
- Slides ()
- Lecture notes by I. Gunich and A. Zakonov ()
- 12. Robert's theorem. The only truthfully implementable social functions for unrestricted quasilinear preferences are affine maximizers.
- Slides ()
- Lecture notes by I. Varvaljuk, A. Irinev and V. Kashirin ()
- 13. Applying mechanism design to real-time online scheduling. Algorithm TD1. A truthful mechanism for online scheduling.
- Slides ()
- Lecture notes by A. Klebanov ()
- 14. (Talk by I. Gnilomedov). AdWords: how auctions help price keywords in an optimal way. Generalized Second Price, VCG, English auction, and Laddering auction.
- Slides ()