**To the Bottom of the
Page**

Instructor: Dr. Shieu-Hong Lin

Class time: MW 10:30-11:45pm at Grove 4B

Office Hours: M~Th 8:30-10:30 am

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 Wednesday Feb.8: (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 Wednesday Feb.8**Practice**: Visit the online service for mathematical programming using AMPL. 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 Wednesday Feb.15- Chapter 1 of
*Strategies and Games: Theory and Practice* - Chapter 2 (diet
models) of
*AMPL: A Modeling Language for Mathematical Programming*

**Lab #2**Due Wednesday Feb.15

·
Explore the continuous
knapsack problem and see an example in 1 about how we can solve
the problem efficiently. As discussed 02/06 in the class, the optimization
problem in the production domain depicted in Chapter 1 of the *AMPL *book can be viewed and
efficiently solved as the continuous knapsack problem without using linear
programming. **Please reflect on how this
and describe how this can be done in your report.**

·
**Show in your report**
how you can apply your understanding of the continuous knapsack problem above to solve the production domain case depicted in the AMPL sample code on P.5 of Chapter 1 without
using linear programming.

**Submit your work**: Upload your report as a WORD document under Canvas.

**Homework #1**Due Wednesday Feb.15**The problem:**Do Exercise 1-1 of*AMPL: A Modeling Language for Mathematical Programming*and submit your work under Canvass as described in the following.**For Part d, the additional constraints there are: at least 2 magazine pages and at most 120 minutes of radios**.**Assignment**: For each part of Exercises 1-1, write down a simple linear program like AMPL sample code on P.5 of Chapter 1 and solve it by submitting your code to the online service for mathematical programming using AMPL as described in Lab#1.**Submission**: Put down all your answers for Exercise 1-1 inside this self-evaluation report (.doc file) and submit the file under Canvas.

**Note:****Examples about the AMPL syntax**: 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**param amt:**), 2**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 3: More on Linear Programming Using AMPL:
Transportation and Assignment Models**

**Reading #3**Due Wednesday Feb. 22- Chapter 2 of
*Strategies and Games: Theory and Practice* - Chapter 3
(transportation and assignment models) of
*AMPL: A Modeling Language for Mathematical Programming*

**Homework #2**Due: Wednesday Feb. 22 (extended to Saturday 02/25 without penalty)- 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 create an AMPL model for this homework.****Just write down plain linear programs in the way depicted in Sections 1.1 and 2.1 in the AMPL book.****Submission**: For each of the problem instances, put down the AMPL code and the optimal refueling policy and the minimal refueling cost determined by the solver inside this self-evaluation report (.doc file) and submit the file under Canvas.

**Notes:****Set cover problem:**The nutrient problem in chapter 2 is related to the set cover problem, which can be viewed as a special case of the nutrient problem where (i) the elements in the universal set*U**S**S*, which corresponds to buying either 1 or r0 package of a particular kind of food, (iv ) finding a minimum number of sets in*U**S*is equivalent to minimize the total food purchasing cost with a uniform price over each package of food.*U***Time complexity**: Read this article on time complexity of algorithms. Download and unzip this C++ project to feel the amount of time taken by O(n), O(n log n), O(n^{2}), and O (n^{5}) algorithms. Try n=1,000,000, n=10,000,000, n=100,000,000, and n=1,000,000,000 and measure the amount of time taken respectively if possible. In practice, the simplex algorithm works well for linear programming**, but the simplex algorithm for linear programming is an exponential-time algorithm in the worst case. There are polynomial-time algorithms (interior-point algorithms) for linear programming.**

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

**Week 4: Transportation/Assignment Model + Dominant
Strategies in Strategic Form Games **

**Reading #4**Due Wednesday March 1**Chapter 4****(Building Larger Models)**and**Chapter 5****(Simple Sets and Indexing**) in*AMPL: A Modeling Language for Mathematical Programming*.**Optiona**l: Chapter 3 of*Strategies and Games: Theory and Practice*

·
**Homework #3 **Due:
Wednesday March 8

- 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. See this template here.**For each of the two cases in the problem instances here, solve the problem instance again by using the AMPL model and specifying the data (in a way like what you see in**prod.dat**in Chapter 1) based on the problem instance. **Note:**It would be an easier task if you**(i)**use a set of numbers 1 to N (with N as a parameter to be specified in the data) to represent the set of fuel stations and**(ii)**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 you can use**equality constraints**as well as inequality constraints in your generic model if needed.**Submission**: please put down all your solutions to the two cases above inside this self-evaluation report (updated 03/03/2017) and submit the file under Canvas.

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

**Week 5: Dominant Strategies in Strategic Form Games **

**Reading #5**Wednesday March 8- 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.
- 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**due:**Tuesday March 14**(Submission under Canvas**remains open till Wednesday 03/29**with no penalty because of the mission conference)- Review the setting of the first price sealed-bid auction
(version 1) and the setting of second
price sealed-bid auction (version 1) and answer the following
questions:
**(i)**Regarding the first price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(ii)**Regarding the second price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(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 (**updated 03/13**) and submit the file under Canvas.

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

**Week 6: Dominance Solvability in Strategic Form Games**

**Reading #6**Due Wednesday March 22- Chapter 4 of
*Strategies and Games: Theory and Practice*

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

**Week 7: Dominance Solvability in Strategic Form Games and
Nash ****Equilibria**

**Reading #7**Due Wednesday**March 29**- 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: Wednesday**March 29**- 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**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(ii)**Regarding the second price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(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 (**updated 03/13**) and submit the file under Canvas.

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

**Week 8: Nash ****Equilibrium**

**Reading #8**Due Wednesday- Review Chapters 3-5 of
*Strategies and Games: Theory and Practice*for Test #1.

**Homework #5**Due Wednesday April 5- Answer the questions here regarding the ½ average-guessing game we discussed in the class.
- Put down your answers into a WORD document ( .doc file) and upload it under Canvas.

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

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

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

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

**Weeks 9-10: Application of Nash ****Equilibrium: Cournot Duopoly | Spring Break**

**Reading #9**Due Wednesday- Read Chapter 6 of
*Strategies and Games: Theory and Practice*.

**Reading #10**Due Wednesday- Read Chapter 7 of
*Strategies and Games: Theory and Practice*.

**Test
#1 (in-class open-book test) on Chapters 3-5 **of *Strategies and Games:
Theory and Practice*: **Wednesday April 12**

1) **Carefully review Homework #4A and Homework
#4B. What would happen if we adopt a similar "Third
Price" sealed bid auction mechanism where the winner pays the third
highest price among all bids? Carefully
review Homework #5.** **What would
happen if we adopt the variant mentioned in the end of Homework #5. It is recommended that you print out the rules of all the
games involved in them and bring them with you for your reference during the
test**. We may ask you questions related to these games or their related
variants.

2) **Carefully review (i)
the voting game on pages 10, 53, and 54, (ii) the hawk-and-dove game on page 37
and the spider-fight variant in Section 5.3, and (iii) the odd-couple example
on Pages 52, 53, and 67.**

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

**Week 11: Mixed Strategies**

**Reading #11**Due Wednesday- Read Chapter 8 of
*Strategies and Games: Theory and Practice*.

**Homework #6**Due Wednesday**:****As we did in the class,**show how you can derive the following**generalized oligopolistic results**regarding the generalized Cournot model with*N*firms described in**Section 6.8**of*Strategies and Games: Theory and Practice*:- at the Nash equilibrium,
the total market quantity is
**N*(a-c)/( (N+1)*b)**while each firm produces the quantity of**(a-c)/( (N+1)*b),** - the resulting market price
is
**a/(N+1) + N*c/(N+1),**and - the
profit for each firm is
**(a-c)**^{2}/[ b*(N+1)^{2 }].

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

**Week 12: Mixed Strategies + Linear Programming and Nash
equilibria in Zero-Sum Games**

**Reading #12:**Due Wednesday- Read here about a simple approach for
solving Homework #7and its limits for generalization.
**Read Sections 11.1~11.2**and the mini-max theorem in Section 11.3 of*Linear Programming: Foundations and Extensions, 2*.^{nd}ed**Read****Sections 5.1~5.4**on duality and duality theorems of*Linear Programming: Foundations and Extensions, 2*.^{nd}ed

**Homework #7:**Due Wednesday

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

**Week 13: More on Mixed Strategies, Zero-Sum Games, and
Nash equilibria**

**Reading #13:**Due Wednesday**Review**Sections 11.1~11.2 and the mini-max theorem in Section 11.3 of*Linear Programming: Foundations and Extensions, 2*.^{nd}ed**Review**Sections 5.1~5.4 on duality and duality theorems of*Linear Programming: Foundations and Extensions, 2*.^{nd}ed**Browse**Chapter 10 (**Zero-Sum Games**) of*Strategies and Games: Theory and Practice*.

**Homework #8:**Due: Wednesday- Set up linear programs in
AMPL to find a Nash equilibrium for the same game in Homework #7 again
but this time based on the approach described in Section 11.1~11.2 of
*Linear Programming: Foundations and Extensions, 2*.^{nd}ed **Submit your work**: Put down your AMPL code and your answers according to this self-evaluation report (.doc file) and submit the file under Canvas.

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

**Test #2 (take-home test):**Due: Thursday**Problem set**: Go to Canvas/Files to find the problem set there. Upload you solutions under Canvas (under**Assignments**/**Test 2)**.**40 points in total**: 1 point each for each question for problem#1~#5 and 10 points for Problem #6. 10 possible bonus points for creating a functional AMPL generic modeling for Problem #6.**Integrity rules**: (i)**Resources allowed**: The only resources allowed are the textbook and your class notes, and your earlier homework. The AMPL site is allowed for solving linear programs.**(ii) No collaboration**: You should not discuss the test with others for clues during the test**.****(iii) Violation of the integrity rules**is viewed as cheating in the test.**No meeting in the final exam week**.

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

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

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

**TA: William Tan.
TA hours in MATH lab: Monday/Wednesday
2:00~3:00pm**

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

**To the Top of the
Page**