Course Information
COMP3352 Algorithmic Game Theory

COMP3352 Algorithmic Game Theory

2017-18
Instructor(s):Huang Z.Y.
(Class A) No. of credit(s):6
Recommended Learning Hours:
Lecture: 39.0
Pre-requisite(s):MATH1853 or MATH2101; and COMP2119
Co-requisite(s):  
Mutually exclusive with:  
Remarks:

Course Learning Outcomes

1. [Basic working knowledge]
Able to understand and apply basic concepts in game theory: pure Nash equilibria, mixed Nash equilibria, correlated equilibria, coarse correlated equilibria, incentive compatibility, etc.
2. [Problem modeling]
Able to model computational problems in the presence of strategic users by identifying the appropriate utility model and equilibrium concept.
3. [Problem solving]
Able to solve basic problems in algorithmic game theory: design mechanisms in single-parameter and multi-parameter settings, analyze the price of anarchy of a given game, design algorithm for finding an equilibrium of a given game.
4. [Self-learning]
Able to read classic papers in game theory from both economic and computer science literature.
Mapping from Course Learning Outcomes to Programme Learning Outcomes
 PLO aPLO bPLO cPLO dPLO ePLO fPLO gPLO hPLO iPLO j
CLO 1
CLO 2
CLO 3
CLO 4

T - Teach, P - Practice
For BEng(CompSc) Programme Learning Outcomes, please refer to here.

Syllabus

Calendar Entry:
Strategic behaviors of users are of increasing importance in today’s computational problems, from data analysis (where a user may strategically manipulate his data) to routing (where a user may strategically choose not to follow the path the algorithm specifies). This is an undergraduate advanced algorithm course that covers various topics at the interface of theoretical computer science and economics, seeking to provide the basic concepts and techniques, both economic and algorithmic ones, that would allow the students to design algorithms that can achieve the desirable outcomes in the presence of strategic behaviors of users. This course focuses on three topics: 1) mechanism design, which studies how to incentivize users to truthfully report their data for a given computational task; 2) price of anarchy, which quantifies the inefficiency caused by users’ strategic behaviors; and 3) algorithms and complexity theory for learning and computing equilibria. The course will also cover selected advance topics such as the use data of past user behaviors in auction design, and case studies of several important applications including online advertisement auctions and kidney exchange.

Detailed Description:

Assessment:
Continuous Assessment: 50%
Written Examination: 50%

Teaching Plan

Please refer to the corresponding Moodle course.

Moodle Course(s)

COMP3352A