Syllabus
 

 

 

In optimization, one attempts to find values for parameters that minimize a suitably defined criterion (such as monetary cost, energy consumption, heat generated, etc.) However, in most engineering applications there is always some uncertainty as to how the selected parameters will affect the final objective. One can then pose the problem of how to make sure that the selection will lead to acceptable performance, even in the presence of some degree of uncertainty. This question is at the heart of most zero-sum games that appear in engineering applications. In fact, game theory provides the mathematical framework for robust design in engineering.
rockpaperscissors
saddle-point
 Modern game theory was born in the 30's, mostly propelled by the work of John von Neumann, further refined by Morgenstern, Kuhn, Nash, Shappley and others. Throughout most of the 40's and 50's, Economics was its main application, eventually leading to the 1994 Nobel prize in Economic Science awarded to John Nash, John C. Harsanyi, and Reinhard Selten for their contributions to Game Theory. It was not until the 70s that it started to have a significant impact on engineering and in the late 80's it led to significant breakthroughs in control theory and robust filtering. Currently Game theory is pervasive to all areas of engineering.

The purpose of this course is to teach students to formulate problems as mathematical games and provide the basic tools to solve them. The course covers:

  • Static games, starting with two-player zero-sum games and eventually building up to n-player non-zero sum games. Saddle-points andNash
    equilibria will be covered.
  • Dynamic optimization (dynamic programming) for discrete and continuous time.
  • Dynamic games, both open and closed-loop policies.

The intended audience includes (but is not restricted to) students in communications, controls, signal processing, and computer science. The class is project-oriented (no exams!) and the students are strongly encouraged to choose a project that is relevant to their own area of research.

Prerequisites

Graduate level-matrix theory with introduction to matrix analysis and computations (e.g., ECE 210A). A review of basic probability is very much encourage.

Course's web page

The syllabus, homework, solutions to homework, and all other information relevant to the course will be continuously posted at the course's web page. The URL is

http://www.ece.ucsb.edu/~hespanha/ece270/

quick links
STUDY GUIDE
HOMEWORK ASSIGNMENTS

Academics

 

Instructor

João P. Hespanha

email: hespanha@ece.ucsb.edu
phone: (805) 893-7042
office: 4165 Harold Frank Hall

Office hours: Please email or phone me to schedule for an appointment.

Textbook

The course will follow closely the following set of lecture notes:
[1] J. Hespanha. Noncooperative Game Theory: An Introduction for Engineers and Computer Scientists. Princeton Press, 2017. ISBN-13: 978-0691175218.

Other recommended textbooks are:
[2] Tamer Başar and Geert Olsder. Dynamic Noncooperative Game Theory, 2nd ed. SIAM Classics in Applied Mathematics, 1999. ISBN 0-89871-429-X.
[3] Drew Fudenberg and Jean Tirole. Game Theory. MIT Press, 1991. ISBN 0-262-06141-4
[4] D. Bertsekas. Dynamic programming and optimal control, vol I, Athena Scientific. Athena Scientific, 1995. ISBN 1-886529-12-4.

Projects

The following three types of projects are possible in this course:

  1. Solution of a research problem relevant to the student's area of research
  2. Software implementation of a game player
  3. Independent study of a topic not covered in class (e.g., reading a paper or book chapter). Possible topics include:
    a. N-person games in extensive form (Sec 3.5 of [2])
    b. Cooperative games
    4. c. Markov games
    d. Computer network games (security, resource management)
    e. Pursuit-evasion (Ch. 8 of [2])
    f. No-regret learning
    g. Bandit problems

A one-page project proposal is due on Feb 21.

The project evaluations will be based on your class presentations

Study Guide

 

The following is a tentative schedule for the course. If revisions are needed they will be posted on the course's web page. Students are strongly encouraged to read the corresponding chapter of the lecture notes prior to each class.

Class Contents Remarks

Lect #1

1/8

Introduction and course overview

Introduction to game theory

Noncooperative Games

  • Elements of a Game
  • Cooperative vs. noncooperative games
  • Robust designs
  • Mixed policies
  • Nash Equilibria

Lect #2

1/10

Policies

  • Actions vs. policies
  • Multi-stage games
  • Open vs. closed-loop
  

1/15

 Martin Luther King day  

Lect #3

1/17

Zero-sum games

Zero-sum marix games

  • Security levels and policies
  • Alternate vs. simultaneous play
  • Saddle-point equilibria
  • Security levels
  • Order interchangeability
  • Computational complexity
  

Lect #4

1/22

Mixed policies

  • Mixed action spaces
  • Mixed security policies and levels
  • Mixed security policies and saddle-point equilibria
  

Lect #5

1/24

Minimax theorem and its consequences

  

Lect #6

1/29

Computation of mixed saddle-point equilibrium policies

  • Graphical method
  • Linear programming
  • Dominating policies
  

Lect #7

1/31

Games in extensive form

  • Extensive form representation
  • Multi-stage games
  • Saddle-point equilibria
  • Matrix-form for games in extensive form
  • Feedback games
  • Recursive computation of equilibria for multi-stage games
  

Lect #8

2/5

Stochastic policies for games in extensive form

  • Mixed policies and saddle-point equiliria
  • Behavioral policies and saddle-point equilibria
  • Recursive computation of equilibria for feedback games
  • Mixed vs. behavioral interchangeability
  • Non-feedback games
  

Lect #9

2/7

Non-zero-sum games

Two-player games

  • Nash equilibrium
  • Bimatrix games
  • Admissible Nash equilibria
  • Mixed policies
  • Strategically equivalent games
  

Lect #10

2/12

Computation of Nash equilibria for bimatrix games

  • Completely mixed Nash equilibria
  • Computation of mixed policies
 

Lect #11

2/14

N-person games

  • Pure and mixed policies
  • Completely mixed policies
  

2/19

 President's day  

Lect #12

2/21

Potential games

  • Identical interest and potential games
  • Potential games with interval action spaces
  • Interval action spaces

Project proposal due Feb 21

Lect #13

2/26

Classes of games

  • Dummy and decoupled games
  • Bilateral symmetric games
  • Congestion games
  • Distributed resource allocation
  • Computation of Nash equlibria for potential games
  • Ficticious play
 

Lect #14

2/28

Dynamic games

Dynamic games

  • Dynamic programming
  • Information structure
  • Continuous- vs. discrete-time games
  • Games with variable termination time
  

Lect #15

3/4

One-player dynamic "games" (optimization)

  • Cost-to-go
  • Dynamic programming
  • Solving one-player games with MATLAB

 

  

Lect #16

3/6

One-player differential "games" (optimization) [optional]

  • Cost-to-go
  • Dynamic programming
  • Variable termination time
  

Lect #17

3/11

 State-feedback zero-sum dynamic games
  • Cost-to-go
  • Dynamic programming
  • Solving zero-sum games with MATLAB
  

Lect #18

3/13

 State-feedback zero-sum dynamic games

State-feedback zero-sum differential games (optional)

  • Cost-to-go
  • Dynamic programming
  • Linear quadratic games
  • Variable termination time
  • Pursuit-evasion
 

3/18

Project presentations

  

3/20

Project presentations

  

Homework Assignments

 

Number Posted on Due date Exercises Relevant lectures

#1

 12/16/2023 1/17/2024

See canvas

 #1-#2

#2

 12/16/2023 1/29/2024 See canvas #3-#4

#3

 12/16/2023 2/5/2024 See canvas #5-#6
#4 12/16/2023 2/12/2024 See canvas #7-#8
#5 12/16/2023 2/21/2024 See canvas #9-#10
#6 12/16/2023 3/4/2024 See canvas #12-13