**To the Bottom of the
Page**

Instructor: Dr. Shieu-Hong Lin Email:

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

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

**Showcase
1: Optimization Problems for Vehicle Refueling Planning **

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

**Reading #1 **Due: Thursday Jan. 24

- (i) Read this article
on linear programming, focusing on the concepts of
**standard form**and**duality**. (ii) Browse Introduction of*AMPL: A Modeling Language for Mathematical Programming*, focusing on the part explaining the term ‘*mathematical programming*’. (iii) Read Sections 1.1-1.4 of Chapter 1 (production models) of*AMPL: A Modeling Language for Mathematical Programming*. **Enter your report online under Canvas according to this format**.

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

**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 (the dual program of the one above,**not**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. (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: 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

**Duality**: Consider the following two linear programs: 1 and 2 in standard form written in AMPL. For each case, (i) please**write down**the dual program in AMPL, (ii)**solve**both the primal program and the dual program by using the online service for mathematical programming using 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.**Submission**: Record in a text document (Homework1.txt for example) (i) your AMPL code for the dual programs and (ii) the optimal solutions to the dual programs provided by the online service for AMPL. Upload the file under Canvas.

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

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

- Consider the linear program shown in the very end of this step-by-step illustration of the simplex
algorithm (updated version 02/05) as an exercise problem. Apply the
simplex algorithm in the way depicted in the step-by-step
illustration to solve this problem accordingly. Download the WORD
version of step-by-step illustration here
(updated
version 02/05) as a template to work on this problem. Record in the file all the intermediate steps needed
until you find the optimal solution in the end.
**Submission**: Complete your work above and upload the file under Canvas.

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

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

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

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

**This is an optional homework for extra bonus points.**You are not required to do this homework.**(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 { i in Stations: i>=2}** to imposed a
condition on the index of i in an

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

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

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

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

** **** **

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

**To the Top of
the Page**