NONCOOPERATIVE GAME THEORY
ECE594D — Fall 2007
Enrollment Code 54098, 1-5 units
Tue/Thu 2:00-3:50pm @ Phelps 1437
Course description
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.
|
|
![[ROCK]](ECE594DFall07Games_files/image004.gif){kind=small}
![[PAPER]](ECE594DFall07Games_files/image005.gif){kind=small}
![[SCISSORS]](ECE594DFall07Games_files/image006.gif){kind=small}
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 made a major splash in control theory and robust filtering.
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,
· Dynamic optimization (dynamic programming) for discrete and continuous time.
·
Dynamic games, both open and closed-loop
policies. Saddle-points and
The intended audience includes (but is not restricted to) students in communications, controls, signal processing, and computer science. The class will be entirely project-oriented (no exams!) and the students are strongly encouraged to choose a project that is relevant to their own area of research.
Further information (including a detailed syllabus) is available on the web at
http://www.ece.ucsb.edu/~hespanha/ece594d/.
Prerequisites
ECE 210A Matrix
Analysis and Computation: Graduate level-matrix theory with introduction to
matrix analysis and computations: SVD's, pseudo-inverses, variational
characterization of eigenvalues, perturbation theory (e.g., ECE 210A).
A review of basic
probability theory is very much encouraged!
Instructor
João P. Hespanha (hespanha at
ece.ucsb.edu), phone:
Office hours: Please email or phone in advance to schedule an appointment.
Textbook
The main textbooks are:
[1] Tamer
Başar and
[2]
[3] D.
Bertsekas. Dynamic programming and optimal control, vol I, Athena Scientific.
The classes will
follow closely chapters 1-6 of Başar’ book [1].
The lectures follow closely the following (very preliminary) lecture notes:
http://www.ece.ucsb.edu/~hespanha/published/games.pdf
Projects
The following two types of projects are possible in this course:
1. Solution of a research problem relevant to the student’s area of research
2. 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 [1])
b. Static infinite games (Ch. 4 of [1])
c. Learning and evolution in repeated games (pp. 23-29 of [2])
d. Markov games
e. Computer network games (security, resource management)
f. Pursuit-evasion (Ch. 8 of [1])
g. Cooperative games (G. Owen, Game Theory, 3rd edition, Academic Press, 1995)
A one-page project proposal is due on Nov 1st
Detailed Syllabus
The following is a tentative schedule for the course. As revisions are needed, they will be posted on the course's web page. The rightmost column of the schedule contains the recommended reading for the topics covered on each class. Students are strongly encouraged to read these materials prior to the class.
|
Class |
Content |
References |
|
#1, Set 27 |
No
class |
|
|
#2, Oct 2 |
Course overview |
|
|
#3,
Oct 4 |
Noncooperative games 1
Players,
actions, and policies 2
Information
structure 3
Optimality
vs. equilibrium 4
Static
vs. Dynamic games |
Ch 1 of [1] |
|
#4, Oct 9 |
Zero-sum games: Matrix
form
|
Secs 2.1-2.2 of [1] |
|
#5, Oct 11 |
|
Secs 2.2-2.3 of [1] |
|
#6, Oct 16 |
No class |
|
|
#7, Oct 18 |
|
Secs 2.3-2.4 of [1] |
|
#8, Oct 23 |
Zero-sum games in
Extensive form 1.
Extensive/tree
form 2.
Saddle-point
policies |
Sec 2.4 of [1] |
|
#9, Oct 25 |
3.
Feedback
games 4.
Feedback
saddle-point policies 5.
Mixed
policies |
|
|
#10, Oct 30 |
6.
Behavioral
policies Extensions* |
Sec 2.5 of [1] Secs 2.6-2.8 of [1] |
|
#11, Nov 1 |
Bimatrix games 1.
2.
Mixed policies 3.
Existence
of Nash equilibrium in mixed policies (no proof) 4.
Computation
of mixed policies: QP |
Secs 3.1-3.2, 3.4 of [1] and Sec 1.2 of [2] |
|
#12, Nov 6 |
No class |
|
|
#13, Nov 8 |
N-person games: Matrix
form 1.
2.
Mixed policies 3.
Existence of Nash equilibrium in mixed policies N-person games: Extensive form* Games with chance moves* |
Secs 3.3-3.5 of [1] Secs 3.6-3.7 |
|
#14, Nov 13 |
Static infinite games 1.
e-Nash equilibrium 2.
Pure vs.
mixed policies 3.
Semi-infinite
bimatrix games (Th. 4.2) 4.
Continuous
kernel games (Ths. 4.3*, 4.4 for multi-player and 4.5*,
4.6* for zero-sum) Braess Paradox (Sec 4.7) |
Secs 4.1-4.4, 4.6-4.7 |
|
#15, Nov 15 |
Infinite dynamic games 1.
Discrete-time
dynamic games 2.
Continuous-time
dynamic games |
Secs 5.1-5.3 |
|
#16, Nov 20 |
Dynamic (one player)
optimization (discrete- and continuous-time) 1.
Dynamic
programming |
Secs 5.5-5.6 |
|
Nov
22 |
Thanksgiving (no class) |
|
|
#17, Nov 27 |
2.
Minimum
principle Dynamic zero-sum games
(discrete- and continuous-time) 1.
Necessary
conditions for open-loop equilibrium |
Secs 5.5-5.6, 6.1-6.2, 6.5 |
|
#18, Nov 29 |
2.
Sufficient
conditions for open-loop equilibrium 3.
Sufficient
conditions for feedback equilibrium 4.
Linear
quadratic games (H-infinity control) |
Secs 6.1-6.2, 6.5 |
|
#19, Dec 4 |
Project presentations |
|
|
#20, Dec 6 |
Project presentations |
|