CSCE 496/896: Computational Game Theory and Its Applications

Course Description:

We Don't Live In A Vacuum! We interact with other agents in our environment to make rational decisions. For example, selecting the quickest or easiest route to go from your apartment to campus, selecting the best amount to bid in an eBay auction, determining whether to fold in a 2-player poker game or selecting a winning move in a Rock-paper-scissors game. In all of these examples, we must interact with other agents when making decisions. In particular, our best strategy depends on the behavior of other agents in the environment (e.g., the chosen route depends on the number of others are using those routes, play rock if my opponent plays scissors). How do we make rational decisions when facing other strategic agents in a given environment? What is the best strategy? Game theory helps us to answer these questions.

Game theory is a mathematical tool that allows us to reason about the strategic interaction of self-interest and rational agents in a given environment. The construct provides a set of frameworks that characterizes the rational outcomes in such an environment of strategic agents. While the area of game theory is originated from the economic literature, computer scientists have made significant contributions to this area from the modeling and computational perspectives in the last decades (which led to computational game theory). Moreover, numerous applications of game theory have deployed in the real world (e.g., allocating policing resources to checkpoints in the LAX airport, allocating patrollers to protect wild animals in Africa, and predicting the voting behavior of the senators in the U.S. for a bill).

In this special topic course on computational game theory, you will be first introduced to fundamental game-theoretic decision-making tools for modeling and understanding the strategic interaction of self-interested and strategic agents. Using these modeling tools, we will discuss their solution concepts and how they can be used to predict the decision-making behavior of agents. Having gained a solid understanding of decision-making tools and solution concepts, we will then discuss the computational aspects of computing these solution concepts. Finally, we will discuss some of the main applications of game theory to security and social science domains.

As such, the course will be divided into three parts: (1) Classical Game Theory and Fundamental, (2) Computational Game Theory, and (3) Computation Game Theory and Its Applications. The topics for each part are covered below (tentatively).

The class consists of lectures (by the instructor), textbook and paper readings, (student) presentations, homework, exams, and projects. We don't expect the students to have any background in game theory. Any necessary and required material will be covered in the course. However, it would be desirable if the students have some background in algorithms/probabilities and basic mathematical maturity.

Topics:

Part 1 - (Classical) Game Theory

- Rational Decision Making

- The Single-Person Decision Problem

- Actions, Outcomes, Preferences, and Utility Functions

- Decision Making under Uncertainty

- Risk, Nature, Random Outcomes

- Evaluating Random Outcomes

- Rational Decision Making with Uncertainty

- Static Games of Complete Information

- Basic Model

- Normal-Form Games with Pure Strategies

- Matrix Representation

- Solution Concepts

- Notable Games

- Rationality and Common Knowledge

- Dominance in Pure Strategies

- Iterated Elimination of Strictly Dominated Pure Strategies

- Beliefs, Best Response, and Rationalizability

- Nash Equilibrium

- Nash Equilibrium in Pure Strategies

- Nash Equilibirum and Applications

- Mixed Strategies

- Strategies, Beliefs, and Expected Payoffs

- Mixed-Strategy Nash Equilibrium

- Nash's Existence Theorem

- Other Notable Equilibrium Concept (Correlated Equilibrium and Coarse Correlated Equilibrium)

Part 2 - Modeling and Computation

- Succinct Representations of Games for large numbers of players

- Graphical Games

- Action-Graph Games

- Finding an Equilibrium

- Computing a Nash Equilibrium in a Two-Player Zero-Sum Games

- Computing a Nash Equilibrium in a General-Sum Games

- The Complexity of Computing a Nash Equilibrium

- Heuristic Approaches for Computing Nash Equilibrium

- Learning in Games

- Iterated Best Response

- Fictitious Play

- No-regret Algorithms

- Targeted Learning

- Finding other Solution Concepts (Correlated Equilibrium and Coarse Correlated Equilibrium)

Part 3 - Applications

- Application of Congestion Games

- Resource Allocation (Congestion Games)

- Road Congestion (Network Congestion Games)

- Application of Graphical Games

- Security Domain (e.g., Interdependent Security Games)

- Social Influence Domain (e.g., influence Games)

- Stackelberg Games and Their Applications

- Security against Terrorism

- Wildlife Protection

- Machine-in-the-Loops

(Optional) Advanced Topics: Dynamic Games of Complete Information, Static Games of Incomplete Information, Dynamic Games of Incomplete Information, Price of Anarchy