CS 6301-001: Game Theory
  Spring 2021 ...... TR 10:00 -- 11:15   

 

Instructor: R. Chandrasekaran
Office: ECSS 4.611

 Phone: (972) 883-2032
Office Hours: W: 1:30 -- 3:00  BB-Collaborate
URL: http://www.utdallas.edu/~chandra
email: chandra AT utdallas DOT edu

Teaching Assistant:

email:

Prerequisite: CS 6363: Design and Analysis of Algorithms

Grading: Assignments (25%); Exam I (35%); Presentations (40%) ?

In this course we will study about competition, cooperation, and rational decision making when more than one set of interests are involved. A list of books is found at www.economicsnetwork.ac.uk/books/GameTheory.htm. Of these many books I will draw from the following:

  1. Game Theory: G. Owen (Third Edition), Academic Press 1995.
  2. Game Theory for Applied Economists: Robert Gibbons, Princeton University Press 1992
  3. Games and Information: Eric Rasmusen, Basil Blackwell, 4th Edition (2005)
  4. Games and Decisions: D. Luce and H. Raiffa, Harvard University Press 1967 (available in Dover Edition)
  5. Game Theory in the Social Sciences: Concepts and Solutions by M. Shubik, MIT Press 1989
  6. Game Theory: D. Fudenberg and J. Tirole, MIT Press 1993
  7. Game Theory: Analysis of Conflict: R. Myerson, Harvard University Press 1991
  8. A course in game theory: M.J. Osborne, and A. Rubinstein, The MIT Press, 1994

 Topics:

0. Definition of a Game

1. Games with complete information:
        a. Players, Strategies, Normal (Strategic form), best response, equilibrium concept
        b. Dominance, iterated dominance, dominant equilibrium
        c. Mixed strategies, Cournot-Nash equilibrium, pareto optimality

2. Utility Theory :
        a. von-Neumann Morgenstern
        b. Transferable and Non-transferable utility
        c. Ordinal and cardinal utility
        d. Bounded utility

3. Two-person-Zero-Sum Games :
        a. Linear Programming and its relation to games
        b. Minimax theorem and LP duality
        c. Minimax strategies and Nash equilibria
        d. Constrained Games and LP formulation

4. Non-zero-sum Games :
        a. Nash's proof of existence of Nash equilibria using Brower's (Kakutani's) fixed point theorem
        b. Two-person nonzerosum games (Bimatrix Games)
        c. Lemke-Howson algorithm and constructive proof of existence of Nash equilibrium.

5. Correlated strategies and correlated equilibria :
        a. Relation to Nash equilibria.
        b. Efficiency

6. Examples :
        a. Cournot Model
        b. Bertrand Model
        c. Stackelberg Model
        d. Infinitely many pure strategies

7. Extensive Forms :
        a. Game Trees
        b. Information Structures
        c. Subgames
        d. Credible and Noncredible Threats
        e. Subgame perfectness
        f. Trembling-hand perfectness
        g. Backward induction
        h. Repeated games
        i. Stochastic Games
        j. Multiple subgame perfect equilibria
        k. Sequential rationality
        l. Perfect recall: memory and actions
        m. Behavior strategies
        n. Markov Strategies

8. Perfect/imperfect, Complete/incomplete, Symmetric/asymmetric information :
        a. Harsanyi transformation
        b. Bayesian equilibria
        c. Bayesian perfectness

9. Bargaining Models:
        a. Axiomatic Models: Nash, Kalai, Roth
        b. Strategic Models: Nash, Osborne and Rubinstein

10. Cooperative Game Theory
        a. Games in Characteristic form
        b. Dominance and stability
        c. Equivalence and isomorphism
        d. Concepts of solution: Stable Sets, Core, Bargaining Sets, Kernel, Nucleolus
        e. Concepts of Value or index of power
        f. Shapley Value, Banzhaf-Coleman index; computation, and application to voting systems

11. Student Presentations:
        a. Fisher Markets
        b. Mechanism Design
        c. Congestion and Potential Games
        d. Auctions/Bidding Models
        e.   Bargaining Models
        f.  Nucleolus Computation
        g. Common Knowledge

 

12. Weighted Voting Games

 

Lecture Notes: