ECON 496 003 / MATH 493 002 / SYST 465 001
Pricing in Optimization and Game Theory
George Mason University
Spring 2009
Instructor: Ursula Morris Class Room: Robinson A 205
Class Time: Fr. 10:30 - 1:10 Office Hours:
Email: UMorris1@gmu.edu
Course Description
Finding the adequate mechanism for pricing limited resources, goods and services is one of the main goals of the theoretical analysis of complex systems. Pricing is one of the driving forces for developing numerical methods to find optimal solutions and economic equilibria. Game theory provides methods to analyze the likely responses of competitors to strategic decisions about prices, expenditures and investments.
The first part of the course will cover the basic ideas and methods in Linear Programming (LP). The fundamental role of pricing in LP will be emphasized: duality, sensitivity analysis and decomposition are important topics. The introduction of Matrix Games (MG) will show the close relationship between solving the dual pair of an LP and finding an equilibrium in a two person MG. The introduction of two-person nonconstant-sum games leads to an understanding of the Nash equilibrium. The lecture will finish with the demonstration of an algorithm for finding an equilibrium in a linear market using modified barrier functions.
Text: Wayne L. Winston, Operations Research, Applications and Algorithms, Fourth Edition, Thomson, Brooks/Cole 2004.
Software: The computational project will use LINDO software which is provided with the book by Wayne L. Winston.
Course Schedule (tentative):
| Lecture Topics | |
| 1 | Introduction and real life applications that led to Linear Programming (LP); Gauss-Jordan elimination |
| 2 | Simplex method |
| 3 | Shadow prices and sensitivity analysis. |
| 4 | Duality in LP; basic duality theorems and their economic interpretation; primal-dual systems |
| 5 | Two person matrix games; pure and mixed strategies; John von Neuman's theorem for matrix games |
| 6 | Matrix games and duality in LP; solving matrix games using LP |
| 7 | Midterm |
| 8 | (Lemke-Howson's Method for zero-sum matrix games; Prisoner's Dilemma, Nash Equilibrium, Lemke-Howson's method for bimatrix games) |
| 9 | Brown-Robinson iterative method for solving matrix games; |
| 10 | Dantzig-Wolfe decomposition; pricing mechanism for LP based on BR method. |
| 11 | Nonlinear Programming |
| 12 | Method of steepest ascent, Newton's method |
| 13 | Constrained Optimization; Lagrange Multipliers; KKT conditions |
| 14 | Equilibrium in a linear exchange market model |
| 15 | Final |
Grading:
| Homework | 20% |
| Midterm | 35% |
| Computational project | 10% |
| Final exam | 35% |