Sergey Nikolenko

Main page

Books
Research papers
Talks and posters
Students
Popular science
Other stuff

   Research
CS and crypto
Bioinformatics
Machine learning
Algebraic geometry
Algebra
Bayesian networks
Earth sciences

   Teaching
 2014
ML, KFU
Game Theory, HSE
Mech. Design, HSE
ML, CSClub Kazan
Game theory, HSE
Math. logic, AU
Machine learning, STC
Machine learning, AU
 2013
Discrete math, HSE
Machine learning, STC
Math. logic, AU
Cryptography, AU
 2012
Machine learning, STC
Math. logic, AU
Machine learning II, AU
Machine learning, AU
Machine learning, EMC
 2011
Cryptography, AU
Math. logic, AU
Machine learning, AU
 2010
Math. logic, AU
Machine learning, AU
Cryptography, AU
 2009
Crypto in CS Club
Statistics
Machine learning, AU
Cryptography
 2008
Speech recognition
MD for CS Club
ML for CS Club
Mechanism design
 2007
Machine Learning
Probabilistic learning

  External links
Google Scholar profile
DBLP profile
LiveJournal account
nikolenko (in Russian)

Teaching activities

Mechanism design

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 (.pdf, 895kb)

Lecture notes by A. Yakushev and M. Churakov (.pdf, 274kb)

2. Analyzing two common auction models. The revelation principle. The revenue equivalence theorem and its corollaries.

Slides (.pdf, 1041kb)

Lecture notes by P. Raikov and K. Egorov (.pdf, 252kb)

3. Efficient and optimal mechanisms. Vickrey–Clarke–Groves mechanism. Arrow–d'Aspremont–Gerard–Varet mechanism.

Slides (.pdf, 741kb)

Lecture notes by I. Lagunov and E. Mandrikov (.pdf, 223kb)

4. Worst-case mechanism design. Suboptimal mechanisms and benchmarks. Deterministic Optimal Price auction. Random Sampling Optimal Price auction and its optimality analysis.

Slides (.pdf, 693kb)

Lecture notes by Ju. Beliaeva and E. Kurbatskiy (.pdf, 278kb)

5. Lower bounds on worst-case optimality. Online auctions. Reduction to expert learning and Kalai algorithm.

Slides (.pdf, 592kb)

Lecture notes by O. Kanzheleva (.pdf, 114kb)

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 (.pdf, 817kb)

Lecture notes by V. Kulev and M. Dvorkin (.pdf, 251kb)

7. Combinatorial auctions. Combinatorial VCG. Single-minded buyers model. O(\sqrt{M})-optimal auction (LOS) and its detailed optimality analysis.

Slides (.pdf, 545kb)

Lecture notes by D. Kulagin, G. Rybakov, and A. Suslov (.pdf, 239kb)

8. Auctions with interdependent values. Affiliated random variables. Three auction models with interdependent values. Revenue comparisons between the three models.

Slides (.pdf, 708kb)

Lecture notes by I. Akishev (.pdf, 240kb)

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 (.pdf, 495kb)

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 (.pdf, 697kb)

Lecture notes by A. Mordvincev, D. Trofimov, and R. Naumov (.pdf, 253kb)

11. Nisan & Ronen's second chance mechanisms. How to provide incentives for truthfulness if an optimal solution is infeasible.

Slides (.pdf, 474kb)

Lecture notes by I. Gunich and A. Zakonov (.pdf, 171kb)

12. Robert's theorem. The only truthfully implementable social functions for unrestricted quasilinear preferences are affine maximizers.

Slides (.pdf, 495kb)

Lecture notes by I. Varvaljuk, A. Irinev and V. Kashirin (.pdf, 241kb)

13. Applying mechanism design to real-time online scheduling. Algorithm TD₁. A truthful mechanism for online scheduling.

Slides (.pdf, 473kb)

Lecture notes by A. Klebanov (.pdf, 179kb)

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 (.pdf, 5496kb)