Courses Offered

COMP3352 Algorithmic Game Theory

COMP3352 Algorithmic Game Theory

2019-20
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 1T,P
CLO 2T,P
CLO 3T,P
CLO 4T,P

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:

Mechanism Design Mapped to CLOs
Economic Theory for Mechanism Design1, 2
Algorithmic Mechanism Design1, 2, 3
Case Studies2, 3, 4
Price of Anarchy Mapped to CLOs
Concept of Price of Anarchy1, 2
Analysis of Price of Anarchy3, 4
Case Studies2, 3, 4
Equilibria Mapped to CLOs
Equilibria Concepts1, 2
Algorithms for Computing Equilibria1, 3
Complexity of Equilibria1, 4

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

Teaching Plan

Please refer to the corresponding Moodle course.

Moodle Course(s)

Don't have an account yet? Register Now!

Sign in to your account

Don't have an account yet? Register Now!

Sign in to your account