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 a | PLO b | PLO c | PLO d | PLO e | PLO f | PLO g | PLO h | PLO i | PLO j |
CLO 1 | T,P | | | | | | | | | |
CLO 2 | | T,P | | | | | | | | |
CLO 3 | | | T,P | | | | | | | |
CLO 4 | | | | | | | | | T,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 Design | 1, 2 |
Algorithmic Mechanism Design | 1, 2, 3 |
Case Studies | 2, 3, 4 |
Price of Anarchy |
Mapped to CLOs
|
Concept of Price of Anarchy | 1, 2 |
Analysis of Price of Anarchy | 3, 4 |
Case Studies | 2, 3, 4 |
Equilibria |
Mapped to CLOs
|
Equilibria Concepts | 1, 2 |
Algorithms for Computing Equilibria | 1, 3 |
Complexity of Equilibria | 1, 4 |
|
Assessment:
Continuous Assessment:
50% Written Examination:
50%
|
Teaching Plan |
Please refer to the corresponding Moodle course.
|
Moodle Course(s) |
|