**George****
****Mason**** ****University**

**Department of SEOR
and Mathematical Sciences Department**.

# Fall 2005

*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. IN 209

* *

* *

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

**Office
Hours**: Tuesday 3 pm-5 pm or by appointment. E-mail: *rpolyak@gmu.edu*

**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

###

### Final Exam: December 13, 2005