Algorithmic Game Theory and Economics

Lecturer

Dr Yun Kuen Cheung, Australian National University

Synopsis

In the 21st century, the internet has become the primary platform for human economic activities. With millions of transactions occurring every hour, these activities are increasingly automated through the use of algorithms. To effectively design and analyse these algorithms, it is crucial to develop a mathematical understanding of human decision-making processes within economic systems. This understanding forms the foundation of game and market theories, which was established by renowned mathematicians such as John von Neumann and John Nash.

This advanced course covers the mathematical foundations of games and markets, their applications in modeling real-world scenarios, and the analyses of their outcomes.

Course overview

Week 1: Foundation of Game Theory

• normal-form games and Nash equilibrium
• existence and computation of Nash equilibrium
• zero-sum games and linear duality

Week 2: Foundation of Market Theory

• Arrow-Debreu markets, Fisher markets and competitive equilibrium
• existence of competitive equilibrium
• welfare theorems
• homogeneous Fisher markets and convex duality

Week 3: Applications of Game and Market Theories

• game/market models of applications, including online auctions, peer-to-peer networks, blockchain and cryptography
• evolutionary and machine learning algorithms in games/markets

Week 4: Stability and Effciency Analyses

• stability of games/markets and its equivalence to optimisation
• cycles, instability and chaos of games
• efficiency of games/markets and price-of-anarchy analysis

Researchers in this interdisciplinary area have came from diverse backgrounds, including mathematics, computer science, economics, physics and engineering. Students with backgrounds in these disciplines will discover fascinating applications that align with their skill sets throughout this course.

Prerequisites

Knowledge in the following subjects is essential:

• calculus and mathematical analysis
• linear algebra
• probability theory (discrete and continuous random variables, expected values)

Knowledge in one or more of the following subjects will be helpful: algorithm design and analysis, dynamical system, machine learning, microeconomics, optimization, stochastic process..

Assessment

• 3 assignments, on Tuesdays of Week 2-4 (30%)
• Test 1, at the end of Week 2 (20%)
• Test 2, at the end of Week 4 (20%)
• Take home project (30%)

(may be subject to change)

Attendance requirements

Participation in all lectures and tutorials is expected.

For those completing the subject for their own knowledge/interest, evidence of at least 80% attendance at lectures and tutorials is required to receive a certificate of attendance.

Resources/pre-reading

1) Parts II and III in Lecture Notes of Game Theory by Prof. Thomas S. Ferguson
https://www.math.ucla.edu/~tom/math167.html

2) Lectures 1-5, 11-15 in Topics in Algorithmic Game Theory, by Prof. Constantinos Daskalakis
https://people.csail.mit.edu/costis/6896sp10/

Not sure if you should sign up for this course?

Take this QUIZ to self-evaluate and get a measure of the key foundational knowledge required.