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.
 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/

 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: Solution of a research problem relevant to the student's area of research Software implementation of a game player 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]) 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 May 16th. 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

Lect #1

4/2

Introduction and course overview

Noncooperative Games

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

Lect #2

4/4

Policies

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

Lect #3

4/9

Zero-sum games

Zero-sum marix games

• Security levels and policies
• Alternate vs. simultaneous play
• Security levels
• Order interchangeability
• Computational complexity

Lect #4

4/11

Mixed policies

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

Lect #5

4/16

Minimax theorem and its consequences

Lect #6

4/18

Computation of mixed saddle-point equilibrium policies

• Graphical method
• Linear programming
• Dominating policies

Lect #7

4/23

Games in extensive form

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

Lect #8

4/25

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

4/30

Two-player games

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

Lect #10

5/2

Computation of Nash equilibria for bimatrix games

• Completely mixed Nash equilibria
• Computation of mixed policies

Lect #11

5/7

N-person games

• Pure and mixed policies
• Completely mixed policies

Lect #12

5/9

Potential games

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

Lect #13

5/14

Project proposal due May 14th

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

5/16

Dynamic games

Dynamic games

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

Lect #15

5/21

One-player dynamic "games" (optimization)

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

Lect #16

5/23

One-player differential "games" (optimization)

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

Lect #17

5/28

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

Lect #18

5/30

State-feedback zero-sum differential games

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

6/4

Project presentations

6/6

Project presentations

Homework Assignments

Number Posted on Due date Exercises Relevant lectures

#1

4/5/2018 4/11/2018

#1-#2

#2

4/5/2018 4/18/2018

#3-#4

#3

4/12/2018

4/25/2018

Download exercises from here and the solutions from here. These solutions were reposted on 5/7/2018 to correct for a typo in exercise 8 B.

#5-#6
#4 4/14/2018

5/2/2018