Course No.:S070105ZY002
Course Category:Professional Course
Period/Credits:40/2
Prerequisites:The general theory of Operations Research I, Combinatorial optimization.
Aims & Requirements:
This course is a professional course for Master and PhD from Operations Research, and is also a elective course for Ph.D. from Management Science. Algorithmic game theory is a cross-cutting area developed in the last decade, mainly related to operations research, theoretical computer science, management. The main content of this course is to discuss the basic concepts, models, algorithms and their theoretical analysis. Through this course, students can grasp these basic concepts, understand the basic model and the corresponding problem and solution algorithm, learn the basic skills of analyzing of the game algorithm, Lay the foundation for further research or application on the game algorithm.
Primary Coverage:
Section 1: Market balanced combination algorithm
Determination of the equilibrium price, the primal dual program, balanced flow, the linear Arrow-Debreu model.
Section 2: Mechanism design of Game Theory
Social choice,dominant strategy, incentive coordination.
Section3: Game Theory algorithms on Graphs
Game Theory models on Graphs, Nash equilibrium calculation on trees, Game Theory on Graphs and correlated equilibrium.
Section 4: Combinatorial auction algorithms
Dynamic model, static model, the auction rules, iterative auction, Walrasian balance.
Section 5: Selfish routing algorithm
Selfish routing, the shortest delay model, the minimum load model, cost of anarchy, cost of steady state.
Textbook:
Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, Cambridge University Press, 2007.
Author:Xiaodong Hu (Academy of Mathematics and Systems Science)
Date:June, 2010