Operations Research

MATH 333, Spring Semester, 2019

 

To the Bottom of the Page

 

Instructor: Dr. Shieu-Hong Lin          Email: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: LinEmail

Class: T Th 10:30 – 11:45am   Lim 041

Office Hours: Lim 137 MW 1:30-3:30pm T Th 3:00-5:00pm (Reserving a slot by email in advance is encouraged.)

 

Course syllabus

 

Books and references

·         Prajit K. Dutta. Strategies and Games: Theory and Practice. MIT Press, 1999. (Required textbook)

·         Robert Fourer, David M. Gay, and Brian W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. (Online)

·         Online service for mathematical programming using AMPL.  (Online)

·         R. Vanderbei. Linear Programming: Foundations and Extensions, 2nd ed.  Springer 2001. (Online)

·         D. Easley and J. Kleinberg. Networks, Crowds, and Markets, Addison Wesley, 2010. (Online)

 

********************************************************************************       

 

About the reading reports:

 

********************************************************************************       

 

Week 1: Introduction to Mathematical Programming and AMPL

 

Showcase 1: Optimization Problems for Vehicle Refueling Planning

Showcase 2: Mechanism of a Bidding Game: Design and Analysis

 

Reading #1 Due: Thursday Jan. 24

 

Lab #1 (AMPL) Due: Thursday Jan. 24

 

 

********************************************************************************       

 

Week 2: Overview of Linear Programming and the Simplex Algorithm

 

Reading #2 Due: Thursday Jan. 31

·         Review the concepts of standard form, duality, and the duality theorem in this article on linear programming and your class notes of what we explored in the class.

·         Read this article on the continuous knapsack problem, a special case of the production model depicted in Chapter 1 (diet models) of AMPL: A Modeling Language for Mathematical Programming.

·         Read Chapter 1 in Linear Programming: Foundations and Extensions.

·         Read the overview section of this article on the simplex algorithm and examine this step-by-step illustration of the simplex algorithm applied to a linear program, which is also explored in Section 2.1 in Linear Programming: Foundations and Extensions using an equivalent tableau format.

 

Homework #1 (Linear Programming and AMPL) Due: Thursday Jan. 31

 

********************************************************************************       

 

Week 3: Simplex Algorithm, Linear Programming, and Applications (I)

 

Reading #3 Due: Thursday Feb. 7

·         Game Theory (Overview): Browse Chapter 1 of Strategies and Games: Theory and Practice.

·         Linear Programming (Simplex Algorithm): Carefully review this step-by-step illustration of the simplex algorithm applied to a linear program, which is also explored in Section 2.1 in Linear Programming: Foundations and Extensions using an equivalent tableau format.

·         Linear Programming (AMPL): Review the basics of AMPL described in Sections 1.1-1.4 of Chapter 1 (production models) of AMPL: A Modeling Language for Mathematical Programming. Optional: Browse Chapter 2 (diet models) of AMPL: A Modeling Language for Mathematical Programming.

 

Homework #2 (Simplex Algorithm) Due: Thursday Feb. 7 (Open for submission till Feb. 14)

 

 

********************************************************************************       

 

Week 4: Simplex Algorithm, Linear Programming, and Applications (II)

 

Reading #4 Due: Thursday Feb. 14

·         Game Theory (Introduction): Read Chapter 2 of Strategies and Games: Theory and Practice.

·         Linear Programming (AMPL): Read Chapter 2 (diet models) of AMPL: A Modeling Language for Mathematical Programming. Optional alternative: If you read Chapter 2 last week and would like to know more about building generic models in AMPL, read Chapter 5 (Simple Sets and Indexing) in AMPL: A Modeling Language for Mathematical Programming.  

 

Homework #3 (Linear Programming Using AMPL) Due: Thursday Feb. 14 (Open for submission till Feb. 21)

 

Optional: Homework #3X for (Generic Modeling Using AMPL) Due: Thursday, May 9

Comments: Carefully read chapter 5 AMPL: A Modeling Language for Mathematical Program and the slide set under Canvas to understand the use of sets and indices in AMPL. Note that it would be an easier task if you (a) use an ordered set of numbers from 1 to N to represent the set of fuel stations and (b) explicitly incorporate variables Xi, Yi, and Zi in the formulation as mentioned in the handout for the fixed-path vehicle refueling problem. Also note that (a) you can use equality constraints as well as inequality constraints in your generic model if needed and (b) you can use an indexing expression like { i in Stations: i>=2} to imposed a condition on the index of i in an ordered set Stations.

 

********************************************************************************       

 

Week 5: Dominant Strategies in Strategic Form Games

 

Reading #5 due Thursday Feb. 21

·         Chapter 3 of Strategies and Games: Theory and Practice. Very carefully read definitions/explanations depicted in 3.1, 3.2, and 3.3 on pages 41~42 on the concepts of “strongly dominant strategies,” “weakly dominant strategies,” and “dominant strategy solutions.”

·         Read the setting of the first price sealed-bid auction and the setting of second price sealed-bid auction.

·         Optional: Read the linear-time fast algorithm for solving the fixed-path vehicle refueling problem described in this paper (available under Canvas | File opf the course): Shieu-Hong Lin, Nate Gertsch, and Jennifer R. Russell. A Linear-time Algorithm for Finding Optimal Vehicle Refueling Policies. Operations Research Letters, 35:3 (2007), 290-296.

 

Homework #4A (Billionaires in an auction) due: Thursday Feb. 28 (open till March 14 without penalty)

·         Read the setting of the first price sealed-bid auction (just version 1) and the setting of second price sealed-bid auction (just version 1) and answer the following questions: (i) Regarding the first price sealed-bid auction, is there a strategy for each player i that (weakly) dominates (see the definition in Chapter 3 of Strategies and Games: Theory and Practice) all other strategies for player i? If so, describe that strategy and provide a proof that it (weakly) dominates all other strategies for player i. If not, please describe why there is no such strategy. (ii) Regarding the second price sealed-bid auction, is there a strategy for each player i that (weakly) dominates (see the definition in Chapter 3 of Strategies and Games: Theory and Practice) all other strategies for player i? If so, describe that strategy and provide a proof that it (weakly) dominates all other strategies for player i. If not, please describe why there is no such strategy. (iii) Is there a dominant strategy solution for the auction game under the setting of the first price sealed-bid auction? Is there a dominant strategy solution for the auction game under the setting of the second price sealed-bid auction?

·         Note: 10 points in total. 4, 4, and 2 points for each of the three questions above.

·         Submit your work: Put down all your answers inside this self-evaluation report and submit the file under Canvas.

 

 

********************************************************************************       

 

Week 6: Dominance Solvability in Strategic Form Games

 

Reading #6 due Thursday Feb. 28

·         Read Chapter 4 of Strategies and Games: Theory and Practice

·         Review the setting of the first price sealed-bid auction and the setting of second price sealed-bid auction and do Homework 4A.

 

 

Homework #4B due: Thursday March 7 (open till March 14 without penalty)

·         Instead of version 1 of the first price sealed-bid auction and the second price sealed-bid auction, please consider version 2 of the first price sealed-bid auction and the second price sealed-bid auction,  and answer the same three questions as in Homework #4A: (i) Regarding the first price sealed-bid auction, is there a strategy for each player i that (weakly) dominates (see the definition in Chapter 3 of Strategies and Games: Theory and Practice) all other strategies for player i? If so, describe that strategy and provide a proof that it (weakly) dominates all other strategies for player i. If not, please describe why there is no such strategy. (ii) Regarding the second price sealed-bid auction, is there a strategy for each player i that (weakly or strongly) dominates (see the definition in Chapter 3 of Strategies and Games: Theory and Practice) all other strategies for player i? If so, describe that strategy and provide a proof that it (weakly) dominates all other strategies for player i. If not, please describe why there is no such strategy. (iii) Is there a dominant strategy solution for the auction game under the setting of the first price sealed-bid auction? Is there a dominant strategy solution for the auction game under the setting of the second price sealed-bid auction?

·         Note: 10 points in total. 4, 4, and 2 points for each of the three questions above.

·         Submit your work: Put down all your answers inside this self-evaluation report and submit the file under Canvas.

 

 

********************************************************************************       

 

Weeks 7-8: Nash Equilibria | Spring Break

 

Reading #7-8 due Thursday March 14

·         Read Chapter 5 (Nash equilibria) of Strategies and Games: Theory and Practice.

 

Homework #5 due: Thursday March 21 (open for submission till March 28, without penalty)

·         Answer the questions here regarding the ½ average-guessing game we discussed in the class.

·         Put down your answers into a WORD document and upload it under Canvas.

 

*****************************************************************************************************  

 

Weeks 9-10: Cournot Duopoly and Nash equilibria

 

Reading #9: Due Thursday March 21 (open for submission till March 28, without penalty)

·         Read Chapter 6 of Strategies and Games: Theory and Practice on Cournot Duopoly.

 

Reading #10: Due Thursday March 28

·         Review Chapters 3-6 of Strategies and Games: Theory and Practice for Test 1.

 

Test 1 (open-book) Thursday March 28

(i) Make sure you understand all the concepts in Chapters 3-6 of the game theory book. (ii) Carefully reexamine your understanding of Homework #1 to Homework #5. (iii) Make sure you understand the standard form for LP, dual programs, and the duality theorem. (iv) Carefully review the step-by-step illustration of the simplex algorithm and this sample solution 1 for Homework 2 (or this acceptable alternative solution 2 using the algebraic view of the simplex algorithm) to make sure you do understand the simplex algorithm.

 

*****************************************************************************************************  

 

Week 11: More on Nash equilibria: Cournot Duopoly + the Commons Problem

 

Reading #11: Due Thursday April 4

·         (i) Review Chapter 6 on Cournot Duopoly as needed. (ii) Read Chapter 7 of Strategies and Games: Theory and Practice on the Commons Problem.

 

*****************************************************************************************************  

 

Week 12: Mixed Strategies

 

Reading #12 due: Due Thursday April 11

·         Read Chapter 8 of Strategies and Games: Theory and Practice on mixed strategies

 

Homework #6 (updated 04/09) Mixed-strategy Nash equilibria in zero-sum games: an ad hoc case study

·         Due Thursday April 18.

·         Note that the ad hoc approach cannot lead you to Mixed-strategy Nash equilibria in zero-sum games in general.

 

 

********************************************************************************       

 

Week 13: Mixed Strategies and Zero-Sum Games

 

Reading #13 due: Thursday April 18

·         Review Chapter 8 of Strategies and Games: Theory and Practice on mixed strategies if needed.

·         Read Chapter 10 of Strategies and Games: Theory and Practice on zero-sum games.

 

********************************************************************************       

 

Week 14: Mixed Strategies: Linear Programming for Finding Nash equilibria in Zero-Sum Games

 

Reading #14: Due Thursday April 25

·         Read Sections 11.1~11.2 and the mini-max theorem in Section 11.3 of Linear Programming: Foundations and Extensions, 2nd ed.

·         Also see the summary note on zero-sum game under File/Canvas.

 

Homework #7 (Updated 04/18) Mixed-strategy Nash equilibrium in zero-sum games: a general approach

·         Due Thursday April 25, open for submission till May 2, without penalty.

·         When doing the homework, you should write down the required linear programs in terms of AMPL code and submit them to the online service for mathematical programming using AMPL to determine the optimal solutions.

 

 

********************************************************************************       

 

Week 15: Review of Mixed Strategies and Nash equilibria in Zero-Sum Games

 

Reading #15: Due Thursday May 2

·         Review Chapter 10 of Strategies and Games: Theory and Practice on zero-sum games.

·         Review Sections 11.1~11.2 and the mini-max theorem in Section 11.3 of Linear Programming: Foundations and Extensions, 2nd ed.

 

Homework #7 (Updated 04/18) Mixed-strategy Nash equilibrium in zero-sum games: a general approach

·         Due Thursday April 25, open for submission till May 2, without penalty.

·         When doing the homework, you should write down the required linear programs in terms of AMPL code and submit them to the online service for mathematical programming using AMPL to determine the optimal solutions.

 

 

Test #2 (Final Exam week):  

*****************************************************************************************************  

Power point class notes available under Files in our Canvas class site.

*****************************************************************************************************           

 

 

To the Top of the Page