About

Game theory is a great mathematical modeling tool for multi-agent decision-making. In game theory, we have players or decision-makers that we assume to be rational agents. it means that they want to maximize their profit or minimize their loss. it seems that game theory is another kind of optimization problem but there is an important difference between them. In most optimization problems, we have a single agent that wants to maximize his profit with consideration of constraints. but in game theory, we are facing multi-agents and decisions of agents, that affect each other. it means that they can’t just find an optimal solution by considering the constraint, they must consider the effect of other agents in their strategy too. and another difference is information structure. With rich information, players could make better decisions and choose better strategies.

The power of game Theory to model a wide variety of situations such as Simultaneous games, Sequential games, Cooperative games, Non-cooperative games, Static games, Dynamic games, Stochastic games, etc., made it applicable to different fields of science like Engineering, Politics, Economics and Computer Science.

In this course, we will introduce the basic definitions of game theory like “Equilibrium” and then focus on real problems that are solved with the game theory approach.

Prerequisite: Basic Engineering Mathematics, MATLAB

Instructor

Dr Amirhosein Nikoofard

Dr. Amirhossein Nikoofard

Assistant Professor
Department of Electrical Engineering, Control Systems
Member of APAC research group
K. N. Toosi University of Science and Technology

Course Outline

  • Introduction and examples
    • Elements of a game: players, objectives, information structure, actions, and policies
    • Classes of games: cooperative/non-cooperative, static/dynamic, zero/non-zero-sum, open-/closed-loop, complete/incomplete information
  • Zero-sum games
    • Zero-sum matrix games
    • Mixed policies
    • Minimax theorem
    • Extensive form of the game.
  • Non-zero-sum games
    • Two-player games
    • Nash equilibria for bimatrix games
    • N-player games
  • Dynamic games
    • Dynamic games
    • One-player discrete- and continuous-time dynamic games
    • State-feedback zero-sum dynamic games
  • Bayesian games
    • Bayesian Nash equilibrium
    • Auctions
    • Examples
  • Stochastic games
  • Market/electricity market
  • Learning

References

  1. Fudenberge D., Birole J., Game Theory, MIT Press, Cambridge, Massachusetts, 1991.
  2. Basar, T., Olsder, G. J., Dynamic non-cooperative game theory, Second Edition, SIAM, 1999.
  3. Hespanha, Joao P, An introductory course in noncooperative game theory, 2011.
  4. P. Bertsekas, Dynamic Programming- Deterministic and Stochastic Models, Prentice-Hall, Inc., 1987.
  5. Han, D. Niyato, W. Saad, T. Basar, and A. Hjørungnes, Game Theory in Wireless and Communication Networks: Theory, Models, and Applications, Cambridge Press 2011.
  6. Fudenberg, D.Levine, The theory of learning in games, MIT Press, Cambridge, Massachusetts, 1998.
  7. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Connected World, Cambridge University Press, 2010.

Lecture Files and Notes

No.TopicsSizeDownload
1Introduction, Engineering Application, What is Game Theory?, Rationality, What Game Theory is Not!, History, Real-Life vs. Game Theory games515 KBDirect Link
2Two-Person Zero-Sum, Matrix games, Strategic forms game, Nash Equilibrium, Saddle points, Security levels and policies682 KBDirect Link
3Saddle-point, Security levels and policies, Saddle-point and security levels, Election games, Order interchangeability, Security v.s. Regret, Dominant Strategy Equilibria, Strictly Dominating Policies, Weakly Dominating Policies, Pareto Optimality362 KBDirect Link
4Zero-Sum Matrix Games: Odds-and-Evens Game, Mixed Strategies, Min-Max Property,328 KBDirect Link
5Optimization: Least-squares, Linear programming, Convex optimization problem, Optimizing over simplexes, Epigraph problem form, Computing Mixed Strategies, Piecewise affine maximization367 KBDirect Link
6Zero sum games: Extensive form, Subgame, Subgame Perfect Equilibrium, Backward induction,224 KBDirect Link
7Zero sum games: Extensive form, Actions and strategies, Saddle-point, Feedback games, Mixed strategies, Behavioral strategies, Kuhn’s theorem989 KBDirect Link
8Non-zero sum games: Security levels, Nash equilibrium, Multiple Nash equilibria, Admissible Nash equilibria, self driving car example, Interchangeable Nash equilibria, Mixed Strategies, Mixed Nash equilibrium570 KBDirect Link
9Non-zero sum games: Completely Mixed Nash Equilibrium, Computing mixed NE, Braess paradox example368 KBDirect Link
10Non-zero sum games: Stackelberg Games, Rational reaction, Stackelberg equilibrium strategy, Compact pure-strategy space, Bilevel optimization problem, Stackelberg vs. bilevel optimization, Chemical process example, Iron Furnace example, Applications of Stackelberg games516 KBDirect Link
11Market: Cournot model, Quantity Competition, Iso-Profit Curves, Collusion Soft drinks 1986 merger, FTC intervenes, The Order of play, Stackelberg games, Supply Functions Equilibria783 KBDirect Link
12Non-zero sum games: Infinite Games, Finite v/s Infinite, Examples, Existence of NE, epsilon-Saddle Point for Zero-Sum Games, epsilon-NE solution for Nonzero-Sum Games, epsilon-NE in Mixed Strategies, Examples of Games with Continuous Action Sets, Reaction Curves, Pure Strategy NE, Stability of nonunique NE, Existence of Pure Strategy NE, NE in Zero-sum Infinite Games, NE in Mixed Strategies, Continuous Action Sets, InfiniteDynamic Games, Static v/s Dynamic, Examples of Infinite Dynamic Games
652 KBDirect Link
13InfiniteDynamic Games: Dynamic games in discrete time, Loop model, Example of a Nonzero sum Game, Information Structures, Examples of Information Structures980 KBDirect Link
14InfiniteDynamic Games: Examples of Information Structures, Continuous-time differential games, Example (zebra in the lake), Dynamic games in discrete time, Discrete-time cost-to-go, Discrete-time dynamic programming
636 KBDirect Link
15InfiniteDynamic Games: Open-loop optimization, State-feedback optimization, Dynamic Programming Example Affine-Quadratic Problems, Computational complexity, One-player Continuous-time differential games, Continuous-time cost-to-go, Continuous-time dynamic programming327 KBDirect Link
16InfiniteDynamic Games: Differential games with variable termination time, Dynamic games in discrete time, Discrete-time dynamic programming, Solving finite zero-sum games with MATLAB309 KBDirect Link
17InfiniteDynamic Games: Zero-sum dynamic games in continuous time, Linear quadratic dynamic games, Zero-sum Differential games with variable termination time288 KBDirect Link
18Stochastic Games: Markov Games, Histories and Rewards, Strategies, Equilibria, Two-Player Zero-Sum Stochastic Games, Evolutionary Simulations, Replicator Dynamics, Example: A Simple Lottery Game, Lottery Game with Replicator Dynamics, Lottery Game with Imitation Dynamics, Double Lottery Game, Double Lottery Game, Replicator Dynamics, Double Lottery Game, Imitation Dynamics1.4 MBDirect Link
19Bayesian Games: Incomplete Information, Bayesian Nash equilibrium, Incomplete Information Cournot Example264 KBDirect Link
20Bayesian Games: Auctions, Types of Auctions, English Auction, First-Price Sealed-Bid Auctions, First-Price Auctions for two bidders, Dutch Auctions, Sealed-Bid, Second-Price Auctions, Incomplete Information in Extensive Form Games, Dynamic Games of Incomplete Information278 KBDirect Link