Fall 2004

Professor Roman A. Polyak

OR 649/Math 493/Econ 496/SYST 465: Pricing in Optimization and Game Theory

Tuesday and Thursday 12:00-1:15 pm. ENT 173

�

Office: Room127, ST-II building; phone: 703-9931685; fax: 703-9931521

Office Hours: Thursday 3 pm-5 pm or by appointment. E-mail: [email protected]

�Text: Wayne Winston, M.Venkataramanan� �Introduction to Mathematical Programming�, Fourth Edition Book/Cole Thomson Learning Inc. 2003.

Course Summary: Finding the adequate mechanism for pricing limited recourses, goods and services is one of the main goals of theoretical analysis complex systems. On the other hand pricing is one of the main ideas for developing numerical methods to find optimal solutions and economic equilibrium .It reflects the fundamental role of the Classical Lagrangian�� and the Lagrange multipliers in constrained optimization.

In the first part of the course we will cover the basic ideas and methods in Linear Programming (LP) and Matrix Games (MG) and show the intimate relation between solving the dual pair of LP and finding equilibrium in two person MG. The fundamental role of pricing in LP will be particularly emphasized: duality, sensitivity analysis and decomposition.

In the second part we will introduce the basic facts of Nonlinear Optimization (NLP):

�KKT optimality condition, duality, equivalence of solving the dual pair of NLP to finding a saddle point for the correspondent Lagrangian. We will use these facts to establish existence of equilibrium in a Linear Exchange (LE) model and to develop the pricing mechanism for finding the equilibrium.��

�There will be homework assignment and �projects.

� Grading:� 25% homework; 30% midterm exam; 10 % project; 35 % final exam.�

Course Schedule��

1. Real life applications that led to LP and NLP formulation

2. Simplex method

3. Shadow prices, sensitivity analysis (review)

4. Duality in LP: basic duality theorems and their economic interpretation

5. Pricing mechanism in LP. Dantzig-Wolf decomposition

6. Two person MG. Pure and mixed strategies. The basic John Von Newman theorem for MG

7. MG and duality in LP. Solving MG using LP methods

�� Midterm

8. Braun-Robinson iterative method for solving MG. Pricing Mechanism for LP based on BR method

9. Basics in NLP: KKT conditions and duality in NLP.

10. Lagrange multipliers methods in NLP

11. Existence of equilibrium in LE market model

12. Finding Equilibrium in LE model