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:
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: