MAT 347/789 / CMP 464/788: Game Theory and
Linear Programming
$$
\bbox[5px,,border:2px solid blue] {\large \max_\mathbf{x} \min_\mathbf{y} \mathbf{y^\intercal A x}~ = ~\min_\mathbf{y} \max_\mathbf{x} \mathbf{y^\intercal A x}}$$
Lehman College, CUNY
Prof. Johnson
Fall 2014
MW 6pm-7:40pm
225 Gillet
MAT 347/789 / CMP 464/788: Game Theory and Linear Programming.
This is an advanced (junior/senior/graduate-level) theory course (meaning, primarily math) in game theory and linear programming, paying special attention to the aspects of these two subjects that relate to one another: in linear programming--the mathematical/computational framework used to solve large-scale optimization problems in business, government, and elsewhere--we will emphasize the geometric view and the nature of LP duality; in game theory--the mathematical theory of the choices made by selfish agents with competing interests--we will emphasize zero-sum 2-person games, the minimax theorem, and the computation of equilibria.
Time permitting, we will also explore some further topics from game theory including the complexity of computing Nash equilibria, Bayesian games, auctions and mechanism design, and voting and social choice.
Although primarily mathematical, this course will also have a "programming" component: we will regularly implement LPs in AMPL and solve them (using NEOS).
Finally, please note--please note--that game theory has nothing to do with video games and computer graphics and whatnot. Game theory does, however, have lots of real, non-fanciful applications in settings like economics, politics, and life: classical problems like tragedy of the commons and prisoner's dilemma (or in the Cold War context, mutually assured destruction), collective action problems, perverse incentives and negative externalities and Pigovian taxes, etc., etc. Also, we'll play games in class!
Prerequisites: Discrete math, familiarity with linear algebra, at least one semester of calculus, and experience and comfort with writing mathematical proofs ("mathematical maturity").
25% - pop quizzes (around 8) and problem sets (around 4)
Most pop quizzes will be testing for minimal understanding of the previous class's material and the assigned reading. Please do not miss class.
25% - midterm 1
25% - midterm 2
25% - final
Instructor:
Prof. Matthew P. Johnson
email: mpjohnson@gmail.com
Office hours: Monday and Wednesday, 5-6pm and by appointment, Gillet 200B.
- When you need help please come to office hours! Seriously. It's not bad students
who come to office hours; good students to office hours.
- When you're going to come in, if possible please email me earlier that day to tell me to expect you.
This is a difficult class. To do well, you will need to keep up with the reading and study
the material you learn in each class. The quizzes, which in general will be questions that
you should be able to solve after attending the previous class (and studying its material), are intended to
incentivize this. Without consistent study,
most students will be unable to wait until the first
exam and then catch up. A good rule of thumb is: you should expect to spend at least two hours studying and doing
homework outside of class for every hour you spend inside of class. Again, seriously.
It is a very good idea to form study groups with classmates and work on homeworks together.
Please also take advantage of the Math Lab, located in Gillet 222.
I want the course to run smoothly, enjoyably and profitably. Feel free to let me know
what you find good, interesting, and fun about the course. The time devoted to different topics will likely be shaped be levels of student interest.
- game theory fundamentals: matrix games, optimal strategies, 2-person zero-sum games, pure and mixed strategies, solving games by LP, Nash equilibria, the minimax theorem and LP duality, normal form, extensive form, backward induction, subgame perfect equilibrium
- linear programming fundamentals: polyhedra and the geometry of LPs, extreme points, basic solutions, the simplex method, convex sets, LP duality, complementary slackness
- AMPL and example applications (diet problem, portfolio optimization) and integer programming (column generation, branch and bound)
- combinatorial problems as LPs (max-flow/min-cut, transportation problem, assignment problem) and the primal-dual method
- further topics in game theory: complexity of computing Nash equilibria (PPAD, etc.), Bayesian games & Bayes-Nash equilibrium, auctions and mechanism design (price of anarchy, Vickrey and VCG, incentive compatibility, Myerson's lemma), voting and social choice (Arrow's & Gibbard-Satterthwaite's impossibility theorems)
- intro: games and strategic thinking
- normal-form games, pure and mixed strategies, Nash equilibria, minimax
- alternative forms / solution concepts, backward induction, common knowledge
- LPs for solving games and solving combinatorial optimization problems
- polyhedra and the geometry of LPs, extreme points
- ?: midterm 1
implementing and solving LPs: AMPL and NEOS
- basic solutions, the simplex method, integer programming
- convex sets, LP duality, complementary slackness
- generalizations: mixed-integer, nonlinear, quadratic, semidefinite
- ?: midterm 2
- complexity of computing equilibria
- Bayesian games
- auctions and mechanism design, price of anarchy, Vickrey/VCG
- voting and social choice: Arrow & Gibbard-Satterthwaite
- weak duality, strong duality, fixed-point theorems
- ?: final exam
mpjohnson@gmail.com
|