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

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

**About the reading reports:**

**Effort (2 points):**How much time have you spent in the reading? What percentage of the contents in the reading do you think you understand? Have you come to the class this week?**Assessment**: The student is expected to**(i)**have attended the class this week at least once (0.5 point), and**(ii) have either**gained a good understanding of**80% or more of the contents****or**have spent at least**three hours**in the reading (1.5 points).**Reflection on the reading (2 points)**: Put down 1~2 paragraphs of your thoughts such as notes of new insight you gained, interesting things encountered, questions of things you don’t understand, and so forth.**Assessment**: the student is expected to show substantial evidence of understanding or effort of trying to understand the contents in the reading.

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

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

**Practice**: Visit the online service for mathematical programming using AMPL. (i) First click the submit button. Secondly copy and paste this linear program in standard form into the input pane of the*model and data*section (the bottom section) of the page. Thirdly solve it for a solution by clicking the*send*button in the*AMPL commands*section. (ii) First click the submit button. Secondly copy and paste this linear program in standard form (the dual program of the one above) into the input pane of the*model and data*section (the bottom section) of the page. Thirdly solve it for a solution by clicking the*send*button in the*AMPL commands*section. (iii) First click the submit button. Secondly copy and paste this AMPL sample code on P.5 of Chapter 1 into the input pane of the*model and data*section (the bottom section) of the page. Thirdly solve it for a solution by clicking the*send*button in the*AMPL commands*section.**Submit your work**: Copy and paste the results you got from AMPL into a WORD document and describe any problems you encountered when using AMPL. Upload the WORD document under Canvas.

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

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

**Duality**: See the following two linear programs: 1 and 2 in standard form written in AMPL. Please write down the dual programs of them in AMPL. Note that in each case the dual program and the primal program should end in the same optimal objective function value if you correctly put down the dual program in AMPL and submit it to the online AMPL service for finding the optimal solution value**Submission**: For each of the two linear programs, put down your AMPL code for the dual program in a text document and submit the file under Canvas.

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

**Week 3: Creating Generic Models Using AMPL**

**Reading #3 **Due Monday, Jan.29

**Linear Programming**:**First**carefully examine the generic modeling for the production domain in Chapter 1 of*AMPL: A Modeling Language for Mathematical Programming*to understand the basic use of parameters, sets, and indices.**Second**, carefully examine the generic modeling for the diet-nutrient domain in chapter 2 to understand more advanced features of using parameters, sets, and indices in the AMPL for creating generic models: See the original AMPL code here based on diet.mod and diet .dat here. Compare it with the following variants of AMPL code on the 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) . You may also want to review Chapter 1 (production models) and Chapter 2 (diet models) of*AMPL: A Modeling Language for Mathematical Programming*as needed.**Game Theory**: Read*Strategies and Games: Theory and Practice*.

**Homework #2 **Due: Monday, Jan.29

- The
**fixed-path vehicle refueling problem:**Examine two problem instances here and read the general description of the problem in this handout. **For each of the two****problem instances**here, write your AMPL code (declare variables and minimize the objective function subject to constraints over the variables in the fashion depicted in Sections 1.1 and 2.1 in the AMPL book) to translate the optimal refueling problem over the problem instance as a linear program. Then submit each linear program to the AMPL online service to find the optimal refueling policy and the minimal refueling cost.**Note that you don’t need to use the more advanced features in AMPL to create an AMPL generic model with separate data sections for this homework.****Just use the basic features of AMPL to write down linear programs in AMPL in the way you did for Homework #1.**We will have a separate homework in the future for you to create an AMPL generic model with separate data sections for solving the fixed-path vehicle refueling problem.**Submission**: For each of the problem instances, put down the AMPL code and the optimal refueling policy (the amount to refuel in each of the stations) and the minimal refueling cost determined by the solver inside this self-evaluation report (.doc file) and submit the file under canvas.

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

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

**(i). Build an AMPL model**for the**fixed-path vehicle refueling problem:**Develop an AMPL model (i.e. something like**prod.mod**in Chapter 1) for solving the**fixed-path vehicle refueling problem**described in this handout and save it in**one text file**(**refueling.mod for example)****.****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 X_{i}, Y_{i}, and Z_{i}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**to imposed a condition on the index of i in an*{ i in Stations: i>=2}***ordered set Stations**.**(ii) Create one data file**separately**prod.dat**in Chapter 1) for each of the two cases in the problem instances here and save them in**two separate text files**(**refueling1.dat**and**refueling2.dat for example)**.**(iii) Solve the problem instances using the AMPL online service**: Visit the online service for mathematical programming using AMPL. For each case here, choose to upload the model file and the corresponding data file you created above, and then submit them to online solver to determine the optimal solution. Copy and paste the optimal solutions found for these two cases and save them in a text file (**solutions.txt for example)****(iv) Submission**: Upload the AMPL model file created in step (i) above, the two data files you created in step (ii) above, and the file containing the optimal solutions found in step (iii) under Canvas.

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

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

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

·
**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, 2 ^{nd} ed*.

·
**Read
Sections 11.1~11.2** and the mini-max theorem in Section 11.3 of *Linear Programming: Foundations and Extensions, 2 ^{nd} 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.

**(i) Build an AMPL model:**Develop an AMPL model (i.e. something like**prod.mod**in Chapter 1) for finding a Nash equilibrium for any given two-person zero-sum games. Save your model in**one text file**(**zeroSum.mod for example)****.****Comments:**Review what you did earlier this semester for Homework #3 about an AMPL generic model.**Note**: You can create just a single generic model for modeling the linear program for player #2 (the column player) to find the mixed strategy. The mixed strategy for player #1 (the row player) can be determined by using the same generic model with a data file that transposes the payoff matrix of player #1 (essentially treating player #1 as player #2 in an equivalent game).**(ii) Create data files**separately**prod.dat**in Chapter 1) for each of the two cases of zero-sum games you encountered in**Homework #6**and**Homework #7**respectively and save them as**separate text files**(such as**zeroSum1Player1.dat, zeroSum1Player2.dat,**and**zeroSum2Player1.dat, zeroSum2Player2.dat for example)**.**(iii) Solve the problem instances using the AMPL online service**: Visit the online service for mathematical programming using AMPL. For each case in**Homework #6**and**Homework #7**respectively, choose to upload the model file and the corresponding data file you created above, and then submit them to online solver to determine the optimal solution. Copy and paste the optimal solutions found for these two cases and save them in a text file (**solutions.txt for example)****(iv) Submission**: Upload the AMPL model file created in step (i) above, the 4 data files you created in step (ii) above, and the file containing the optimal solutions found in step (iii) under Canvas.

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

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