This course focuses on benchmark design and prior-independent optimization. The learning outcomes include understanding the analysis of information-restricted algorithms, exploring Bayesian, prior-independent, and prior-free analyses, and learning about benchmark comparison and resolution. The course teaches skills such as designing optimal prior-independent mechanisms, heuristic benchmark optimization, and discussing main theorems. The teaching method involves lectures and discussions. The intended audience for this course includes researchers, practitioners, and students interested in algorithm design and optimization.
Overview
Syllabus
Intro
Analysis of Information Restricted Algorithms
Three Analyses for Information Restricted Algorithms
Outline
Bayesian, Prior-independent, and Prior-free Analyses
What makes a good benchmark? Question: What makes a good benchmark? benchmark comparison for two-server problem (Boyar, Irani, Larsen, 15)
Normalized Benchmarks
Benchmark Resolution
Discussion of Main Theorem
Prior-independent Mechanism Design
The Optimal Prior-independent Mechanisms Mechanism Design Setting
Heuristic Benchmark Optimization
Conclusions
Taught by
IEEE FOCS: Foundations of Computer Science
