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

Academics

 

Instructor

João P. Hespanha

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

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

Textbook

The course will follow closely the following set of lecture notes:
[1] J. Hespanha. An Introductory Course in Noncooperative Game Theory. [pdf]

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 an automated player for board game
  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. Static infinite games (Ch. 4 of [2])
    c. Learning and evolution in repeated games (pp. 23-29 of [3])
    d. Markov games
    e. Computer network games (security, resource management)
    f. Pursuit-evasion (Ch. 8 of [2])
    g. Cooperative games

A one-page project proposal is due on Oct 31th. Every student is expected to meet the instructor, at least, once before the project presentations.

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
9/26 No class  

Lect #1

10/1

Introduction and course overview

Noncooperative Games

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

Lect #2

10/3

Policies

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

Lect #3

10/8

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

10/10

Mixed policies

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

Lect #5

10/15

Minimax theorem and its consequences

 

Lect #6

10/17

Computation of mixed saddle-point equilibrium policies

  • Graphical method
  • Linear programming
  • Dominating policies
 

Lect #7

10/22

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

10/24

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
 
10/29 No class  

Lect #9

10/31

Two-player games

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

Lect #10

11/5

Computation of Nash equilibria for bimatrix games

  • Completely mixed Nash equilibria
  • Computation of mixed policies
 

Lect #11

11/7

N-person games

  • Pure and mixed policies
  • Completely mixed policies
 

Lect #12

11/12

Potential games

  • Identical interest and potential games
  • Potential games with interval action spaces
  • Classes of potential games

 

 

Lect #13

11/14

Dynamic games

Dynamic games

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

 

 

Lect #14

11/19

One-player dynamic "games" (optimization)

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

One-player differential "games" (optimization)

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

Lect #15

11/21

State-feedback zero-sum dynamic games

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

State-feedback zero-sum differential games

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

Lect #16

11/26

TBA  

11/28

Thanksgiving  

Lect #17

12/3

Project presentations  

Lect #18

12/5

Project presentations  

 

Homework Assignments

 

Number Posted on Due date Exercises Relevant lectures

#1

10/11 10/17

Download problems from here.
Download solutions from here.

#1-#5

#2

10/11 10/24

Download problems from here.
Download solutions from here.

#6

#3

10/11 11/5

Download problems from here.
Download solutions from here.

#7-#8
#4 10/11 11/12

Download problems from here.
Download solutions from here.

#9-#10
#5 10/11 11/19

Download problems from here.
Download solutions from here.

#12