Operations Research

MATH 333, Spring Semester, 2018

 

To the Bottom of the Page

 

Class: MW 10:30 – 11:45am   at Lim 041

Instructor:       Dr. Shieu-Hong Lin  

Office:             Lim 137

Office Hours: M, T, Th 9:00-10:30am; 1:30-3:00pm (Make appointment in advance by email)

 

Syllabus: compact version

 

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 

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

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

 

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

 

About the reading reports:

 

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

 

Week 1: Introduction to Mathematical Programming and AMPL: Production Models

 

Showcase 1: Optimization Problems for Vehicle Refueling Planning

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

 

Reading #1 Due: Monday Jan.15: (i) Introduction and Chapter 1 (production models) of  AMPL: A Modeling Language for Mathematical Programming (ii) Read this article on linear programming. (iii) Optional: Browse this article on mathematical optimization. Enter your report online under Canvas according to this format.

 

Lab #1 Due: Monday Jan.15

 

 

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

 

Week 2: More on Linear Programming Using AMPL: Diet Models

 

Reading #2 Due: Monday, Jan.22

·         Review standard form and duality in this article on linear programming and our exploration of standard form and duality in the class.

·         Chapter 2 (diet models) of  AMPL: A Modeling Language for Mathematical Programming

 

Homework #1 Due: Monday, Jan.22

 

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

 

Week 3: Creating Generic Models Using AMPL

 

Reading #3 Due Monday, Jan.29

 

 

Homework #2 Due: Monday, Jan.29

 

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

 

Week 4: Sets and Indices + Introduction to Game Theory

 

Reading #4 Due Monday Feb. 5

·         Chapter 5 (Simple Sets and Indexing) in AMPL: A Modeling Language for Mathematical Programming.

·         Chapter 2 of Strategies and Games: Theory and Practice

 

Homework #3 Due Monday Feb. 5 extended to Feb. 12 without penalty.

 

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

 

Week 5: Dominant Strategies in Strategic Form Games

 

Reading #5 due Monday Feb. 12

·         Chapter 3 of Strategies and Games: Theory and Practice. Very carefully read definitions/explanations including 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.

·         Revisit the original AMPL code here based on diet.mod and diet.dat in Chapter 2 (diet models) of  AMPL: A Modeling Language for Mathematical Programming. Compare it with the following variants of AMPL code on the same diet problem: 1 (in the data section param amt (tr): now changed into param amt: ), 2 (in the model section index j for FOOD, i for NUTR: changed into i for FOOD, j for NUTR:) , 3 and 4 (index order for param amt[: in the model section param amt { NUTR, FOOD} changed into param amt {FOOD, NUTR} so that we use amt[i,j] instead of amt[j,i] in diet constraints) .

 

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

 

Week 6: Dominance Solvability in Strategic Form Games

 

Reading #6 due Monday Feb. 19

·         Chapter 4 of Strategies and Games: Theory and Practice

 

Homework #4A due: Monday Feb. 19

·         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 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 or strongly) 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 or strongly) 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 7: Dominance Solvability in Strategic Form Games and Nash Equilibria

 

Reading #7 due Monday March. 5

·         Review Chapter 4 of Strategies and Games: Theory and Practice if needed.

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

 

 

Homework #4B due: Monday March. 5

·         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 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 or strongly) 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 or strongly) 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 8: Nash Equilibria

 

Reading #8 due: Monday March. 12  

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

 

 

Homework #5 due: Monday March. 12

·         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.

 

 

Be very careful about the following definitions of terms in the textbook:

                                i.            A strategy x is a dominant strategy for player i if and only if x weakly dominates all other strategies for player i.

                              ii.            A strategy x is a dominated strategy for player i if and only if x is weakly dominated by one or more strategies for player i.

                            iii.            Note that for player i if a strategy x strongly dominates a strategy y then x also weakly dominates y.

 

 

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

 

Week 9: Mixed Strategies

 

Reading #9 due: Monday March. 19 extended to Friday March. 23

·         Read Chapter 8 of Strategies and Games: Theory and Practice.

 

 

Test #1 Wednesday March 21

·         In-class open-book test on (i) Duality of Linear Programs and (ii) Chapters 3-5 of Strategies and Games: Theory and Practice.

·         Carefully review your work and understanding of Homework 4A, 4B, and 5.

 

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

 

Week 10: Mixed Strategies and Zero-Sum Games

 

Reading #10 due: Wednesday March. 28

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

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

 

Homework #6: Due Wednesday April 4

 

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

 

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

 

Reading #11: Due Wednesday April 4

·         Read Section 5.2-5.4 on duality and duality theorems of Linear Programming: Foundations and Extensions, 2nd ed.

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

 

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

 

Week 12: Linear Programming, Nash equilibria in Zero-Sum Games, and the Mini-Max Theorem

 

Reading #12: Due Wednesday April 11

·         Carefully review Reading #11 last Week to work out Homework #7 below.

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

 

Homework #7: Due Wednesday April 11

 

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

 

Week 13: Cournot Duopoly and Nash equilibria

 

Reading #13: Due Wednesday April 18

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

·         Browse Chapter 7 of Strategies and Games: Theory and Practice on the Commons Problem.

 

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

 

Week 14: The Commons Problem and More

 

Reading #13: Due Wednesday April 25

·         Review Chapter 7 of Strategies and Games: Theory and Practice on the Commons Problem.

·         Read Chapter 8 of Networks, Crowds, and Markets on modeling network traffic using game theory.

 

Homework #8: (Optional for bonus points):  Due Wednesday May 2.

 

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

 

Test #2: Due Thursday May 3.

·         Take-home open-book test on all things covered this semester, especially Nash equilibria, mixed strategies, zero-sum games and linear programming, the Cournot model and its variants.

·         Carefully review your work and understanding of Homework 4A, 4B, 5, 6, and 7.

·         Find the problem set under File/Canvas.

 

 

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

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

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

TA:  Ho Leung.  TA hours in Computer lab (Lim 182): Monday 2:00-4:00pm

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

 

 

To the Top of the Page