Advanced Topics in Mathematics

SIT399 Advanced Topics in Mathematics Assignment Two-Option 1  Question 1 Find the values of x for which the following games have a saddle point and solve the game for these cases. 1. The 2-by-2 payoff matrix 2. The 3-by-3 payoff matrix Question 2 Find the expected payoff to each player if Player I uses mixed strategy (0.3, 0.7) and Player II uses mixed strategy (0.2, 0.8), in the two-person zero-sum game with the following payoff matrix. Question 3 This question illustrates the following theorem. If one player of a 2-person zero-sum game employs a fixed strategy, then the opponent has an optimal counter strategy that is pure. In other words, if Player I knows that Player II is using a particular mixed strategy y, then Player I can maximize their expected payoff by using a pure strategy, and vice versa. a. Work out the following. i. Find the expected payoff, E(x,y), to Player I if Player I uses mixed strategy (x1, 1-x1), 0 ≤ x1 ≤ 1, and Player II uses mixed strategy (y1, 1-y1), 0 ≤ y1 ≤ 1, in the 2-person zerosum game with the following payoff matrix. ii. Now, think of y1 is being fixed to y1=0.2, find the value(s) of x1 that maximizes E(x,y) for fixed y1. Make your case that, in general, if Player I can use a pure strategy to get the maximum expected payoff, given that Player I knows Player II’s strategy. b. Suppose that Player I knew that Player II is to use a mixed strategy (0.2, 0.3, 0.5) in the game with the following payoff matrix. Work out the three expected payoffs if Player I uses a pure strategy and hence deduce the best strategy for Player I. Question 4 Using the graphical method to solve the 2-person zero-sum game given in Question 2. Question 5 Using the same game given in Question 3(b): 1. Write down the linear programming problems induced by the game. 2. Solve one of them using any of the linear programming solution methods you have learnt so far to find the optimal strategies for both of the players and find the value of the game. (The following questions are taken/modified from “Integer Programming” by Lawrence A. Wolsey) Question 6 Suppose that you are interested in choosing a set of investments {1,…,7} using Integer Programming with 0—1 variables. Model the following constraints: a. You cannot invest in all of the seven investments. b. You must choose at least one of them. c. Investment 1 cannot be chosen if Investment 3 is chosen. d. Investment 4 can be chosen only if Investment 2 is chosen. e. You must either choose both of Investments 1 and 5 or choose neither. f. If you choose at least one of the investments {1, 2, 3}, then you have to choose at least two investments from {2, 4, 5, 6}. Question 7 Show that X1, X2, X3 contains the same feasible set. X1 = x ∈ {0,1} 4 : 97x1 +32x2 + 25x3 + 20x { 4 ≤139} X2 = x ∈ {0,1} 4 : 2x1 + x2 + x3 + x { 4 ≤ 3} X3 = x ∈ {0,1} 4 : x1 + x2 + x3 ≤ 2, x1 + x2 + x4 ≤ 2, x1 + x3 + x { 4 ≤ 2} Question 8 Vicky is attending a summer school where she must study four units. She must do a one-hour lecture for each of the units every day. There are 6 onehour time slots in a day. As there are way too many students, repeating lectures for each unit is offered at every time slot of the day and are taught by different lecturers. Vicky’s decision on the class of a unit she likes to take is purely influenced by how much the lecturer looks like Keanu Reeves. [Hint: the decision variables should help you decide which class Vicky will take for each unit—i.e., Vicky to take Class i of Unit k. Also, you only need to do the time-table for one day, doesn’t matter which day, and then Vicky will just follow this time-table every day for the whole summer. Furthermore, the score for how much the lecturer for Class i of Unit k looks like Keanu Reeves can be represented by the score pik.] a. Now, formulate an integer programming model to help Vicky choose her classes that maximize the total Keanu Reeves lookalike score. b. Derive a constraint so that Vicky never has to do more than two consecutive classes without a break. c. Modify the objective function, if Vicky’s objective is now to start her day as late as possible, (since she is not exactly a morning person, just like you ☺). Question 9 Solve the following IP using the BNB method. max 17x1 + 10x2 + 25x3 + 17x4 s.t. 5x1 + 3x2 + 8x3 + 7x4 ≤ 12 x ∈ {0,1}4