Sergey Nikolenko

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
userinfonikolenko (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 (.pdf, 806kb)
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 (.pdf, 1077kb)
3. Auctions. Direct mechanisms. Equilibrium strategies in the first-price and second-price auctions. The revelation principle.
Slides (.pdf, 1013kb)
4. The revenue equivalence theorem and its corollaries.
Slides (.pdf, 553kb)
5. Efficient and optimal mechanisms. Vickrey–Clarke–Groves mechanisms. Budget balancing and the Arrow–d'Aspremont–Gerard–Varet mechanism.
Slides (.pdf, 818kb)
6. Combinatorial auctions. Combinatorial VCG. Single-minded buyers model. O(\sqrt{M})-optimal auction (LOS) and its detailed optimality analysis.
Slides (.pdf, 544kb)
7. Impossibility results. Paradoxes of voting. The Arrow impossibility theorem. The Gibbard-Satterthwaite theorem.
Slides (.pdf, 910kb)
8. The Myerson-Satterthwaite impossibility theorem for bilateral trade and its generalization by Williams.
Slides (.pdf, 452kb)
9. Worst-case mechanism design. Suboptimal mechanisms and benchmarks. Deterministic Optimal Price auction. Random Sampling Optimal Price auction and its optimality analysis.
Slides (.pdf, 688kb)
10. Lower bounds on worst-case optimality. Online auctions. Reduction to expert learning and Kalai algorithm.
Slides (.pdf, 588kb)
11. Selling keywords: Overture (Yahoo), Google, and the laddered auction. Buying keywords: landscapes, budget optimization, and optimal uniform probabilistic bidding strategies.
Slides (.pdf, 771kb)
12. Applying mechanism design to real-time online scheduling. Algorithm TD1. A truthful mechanism for online scheduling.
Slides (.pdf, 485kb)