Course Objectives

This graduate-level course provides an introduction to non-cooperative game theory, auction theory, and mechanism design. The coverage will encompass both theoretical and algorithmic developments, with engineering applications to computer communication and networking. Note that we discuss all game-theoretic concepts with practical computer and communication examples.

Intended Learning Outcome

Students would be able to model their engineering problems with a game-theoretic approach, analyze defined games, and use the game results to design protocols (i.e., mechanism design).

Slides

  1. Introduction to Game Theory: Simple Definition (Rationality, Values, Beliefs, and Limitations), Formal Definition and Brief History, Game Theory for Electrical and Computer Engineering, Course Outlines and Administrations, References

  2. Non-Cooperative Games: Game Elements, Strictly Dominant vs Strictly Dominated Strategy, Contracts and Collusion, Prisoner's Dilemma, Coordination, Think Strategically, Applied Examples

  3. Iterative Deletion: Formal Definitions/Notations, Strict versus Weak Dominance, Iterative Deletion of Dominated Strategy, Median Voter Theorem, Model Simplification for Engineering Application

  4. Best Response: Best Response Definition, Partnership Game, Multiple Access Game

  5. Nash Equilibrium I: Definition and Motivation, Rationality vs NE, Finding a Nash Equilibrium, Nash Equilibrium vs Dominance

  6. Nash Equilibrium II: The Investment Game, Coordination Games, "The Battle of the Sexes" Game, Two-person Zero-sum Games and Saddle Point, Nash Equilibrium in "The Forwarder's Dilemma Game", "The ISP Routing Game", "The Joint Packet Forwarding Game", "The Multiple Access Game"

  7. Cournot Game: BR and NE in Cournot Duopoly Game

  8. Mixed Nash Equilibrium I: RSP Game, Randomization and Mixed Strategy

  9. Mixed Nash Equilibrium II: Mixed Strategy Nash Equilibrium, Tennis Game, CSMA mixed Nash in 802.11

  10. Dynamic Games I: Sequential vs Simultaneous Moves, Extensive Forms (Trees), Analyzing Dynamic Games: Backward Induction, Moral Hazard, Incentive Design, Norman Army vs. Saxon Army Game, Revisit Cournot Duopoly (Stackelberg Model)

  11. Dynamic Games II: First Mover or Second Mover, Zermelo Theorem, Formal Definitions: Perfect Information/Pure Strategy/Information Set, Informtion vs Time

  12. Dynamic Games III: Solve Imperfect Information Games, Sub-game Definitions, Sub-game Perfect Nash Equilibrium (SPNE), Don't Screw-Up Game, Match Maker Game, Applied Examples: Market Game, Microsoft vs Mozilla, TDMA Transmission

  13. Repeated Games: The War of Attrition, Repeated Prisoner's Dilemma, Lame Duck Effect, Grim Trigger Strategy, Punishment, Repeated Forwarder's Dilemma, Infinite Repeated Game, Minmax Value, Folk Theorem

  14. Evolutionary Stability: Game Theory meets Biology, To Cooperate or Not, ESS, Social Convention, Hawks and Dove Game, Pareto Optimality

  15. Mechanism Design: Stable Matching, Algorithmic Mechanism Design, Gale-Shapley Algorithm, Cellular Stable Matching

  16. Auction Theory: Winner Curse, Bids and Payoffs, Private Value Auction

  17. Bayesian Game: Incomplete Information Games: Definitions, Bayesian Nash Equilibrium, Sheriff's Dilemma: An Example

Books

An Introduction to Game Theory, by Martin J. Osborne

Game Security The book is intended for 3rd and 4th year undergraduates, and graduate students with no background in game theory. The book emphasizes the ideas behind the theory rather than their mathematical expression, but at the same time is precise..



A Course in Game Theory, by Martin J. Osborne and Ariel Rubinstein

Game Security A course in game theory by Martin J. Osborne and Ariel Rubinstein is published by MIT Press. The book presents the main ideas of game theory at a level suitable for graduate students and advanced undergraduates. It emphasizes the theory's foundations and interpretations of its basic concepts. Precise definitions and full proofs of results are provided; generality is sacrificed and the scope of the material is limited in order to do so. The text is organized in four parts: strategic games, extensive games with perfect information, extensive games with imperfect information, and coalitional games.

Game Theory, by Drew Fudenberg and Jean Tirole

This advanced text introduces the principles of noncooperative game theory - including strategic form games, Nash equilibria, subgame perfection, repeated games, and games of incomplete information - in a direct and uncomplicated style that will acquaint students with the broad spectrum of the field while highlighting and explaining what they need to know at any given point. The analytic material is accompanied by many applications, examples, and exercises.

Journal and Conferences

  1. Conferences
    • Infocom (IEEE conference on International Conference on Computer Communications)
    • GameNets (Game Theory for Networks)
    • WEIS (Workshop on the Economics of Information Security)
    • GameSec (Conference on Decision and Game Theory for Security)
  2. Journals
    • JSAC: Cooperative Communications in MIMO Cellular Networks, December 2010
    • JSAC: Game Theory in Communication Systems, September 2008
    • JSAC: Non-Cooperative Behavior in Networking, August 2007
    • JSAC: Cooperative Communications and Networking, February 2007