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 for CS Club
Fall of 2008. The «Mechanism design» course was substantially improved and redone for the Computer Science Club. I thank Anton Likhodedov for the help and financial support in preparing this course.The course materials (all slides and lecture notes are in Russian):
- 1. Introduction. Game theory. Dominant strategies. Different equilibrium concepts.
- Slides ()
- 2. Fun examples. Prisoner's dilemma, winner's curse, tragedy of commons, dollar auction, Braess paradox. Basic definitions of mechanism design. Social choice functions, mechanisms, Pareto optimality.
- Slides ()
- 3. Auctions. Direct mechanisms. Equilibrium strategies in the first-price and second-price auctions. The revelation principle.
- Slides ()
- 4. The revenue equivalence theorem and its corollaries.
- Slides ()
- 5. Efficient and optimal mechanisms. Vickrey–Clarke–Groves mechanisms. Budget balancing and the Arrow–d'Aspremont–Gerard–Varet mechanism.
- Slides ()
- 6. Combinatorial auctions. Combinatorial VCG. Single-minded buyers model. O(\sqrt{M})-optimal auction (LOS) and its detailed optimality analysis.
- Slides ()
- 7. Impossibility results. Paradoxes of voting. The Arrow impossibility theorem. The Gibbard-Satterthwaite theorem.
- Slides ()
- 8. The Myerson-Satterthwaite impossibility theorem for bilateral trade and its generalization by Williams.
- Slides ()
- 9. Worst-case mechanism design. Suboptimal mechanisms and benchmarks. Deterministic Optimal Price auction. Random Sampling Optimal Price auction and its optimality analysis.
- Slides ()
- 10. Lower bounds on worst-case optimality. Online auctions. Reduction to expert learning and Kalai algorithm.
- Slides ()
- 11. Selling keywords: Overture (Yahoo), Google, and the laddered auction. Buying keywords: landscapes, budget optimization, and optimal uniform probabilistic bidding strategies.
- Slides ()
- 12. Applying mechanism design to real-time online scheduling. Algorithm TD1. A truthful mechanism for online scheduling.
- Slides ()