Question 1. (9 marks) Suppose that P is an m × n matrix, whose entries are non-negative integer. Imagine a game in which Alice chooses an integer in [m] = {1, . . . , m} and Bob chooses an integer in [n] = {1, . . . , n}. When Alice chooses i and Bob chooses j, then Alice pays Pi,j dollars to Bob. Alice’s goal is to minimize how many dollars she pays to Bob, and Bob’s goal is to maximize how many dollars he receives. We will allow Alice and Bob to choose their integers randomly. Part a. (4 marks) Suppose that, in the above game, Alice first chooses a probability distribution D over [m], and tells D to Bob. Based on knowing D, Bob chooses his integer j ∈ [n], so that he maximizies the expected value of the payment he receives, assuming Alice chooses her integer according to the distribution D. Then the expected value of Alice’s payment to Bob is: valueA(D) = n max j=1 EI∼D[PI,j ], (1) where EI∼D means that the expectation is with respect to taking I to be a random integer in [m] sampled according to the probability distribution D. For example D could give probability 12 on I = 1 and probability 12 on I = 2, and then we have valueA(D) = n max j=1 P1,j 2 + P2,j 2 . Show how to use a linear program to compute a probability distribution D for Alice that minimizes valueA(D) as defined in (1). The linear program should have as variables the probabilities assigned by D to any integer in [m], and should also have a variable for valueA(D). Prove that the optimal solution to your linear program gives an optimal D and its value. Part b. (5 marks) Suppose next that, instead, Bob goes first and chooses a probability distribution F over [n], and tells F to Alice. Based on knowing F, Alice chooses her integer i ∈ [n], so that she minimizes the expected value of the payment she gives to Bob, assuming Bob chooses his integer according to the distribution F. Then the expected value of Alice’s payment is: valueB(F) = m min i=1 EJ∼F [Pi,J ], (2) where EJ∼D means that the expectation is with respect to taking J to be a random integer in [n] sampled according to the probability distribution F. Using the strong duality theorem, prove that the maximum of valueB(F) defined in (2) over all probability distributions F on [n] equals the minimum of valueA(D) defined in (1) over all probability distributions D on [m]. Question 2. (15 marks) Let G = (A ∪ B, E) be a connected undirected bipartite graph, where A and B are the two sides of the bipartition. Consider the following system of linear constraints: ∀u ∈ A ∪ B : Xv:(u,v)∈E xuv = 1 (3) ∀e ∈ E : xe ≥ 0 (4) Let x be a feasible solution to (3)–(4). Your goal in this question is to design a polynomial time algorithm that, on input G and x, computes a random matching M in G such that, for any e ∈ E, P(e ∈ M) = xe. Part a. (4 marks) Let F = {e ∈ E : 0 < xe < 1} be the set of edges corresponding to the fractional coordinates of x. Prove that, if F is not empty, the subgraph H = (V, F) of G has a cycle C. 2 Part b. (6 marks) Assume that not all coordinates in x are integers. Use the cycle C to compute two feasible solutions x0 and x 00 of (3)–(4), so that both x0 and x 00 have strictly fewer fractional (i.e., not equal to 0 or 1) coordinates than x. Moreover, there should be a value p ∈ [0, 1] such that x = px0 + (1 p)x 00 . Hint: use the fact that C must have even length, and consider alternatingly adding and subtracting a value to the xe variables for e ∈ C (i.e., you add a value for one edge, and subtract for the next edge in the cycle.) Part c. (5 marks) Use the previous subquestions and describe a polynomial time algorithm that, on input G and x, computes a random matching M in G such that, for any e ∈ E, P(e ∈ M) = xe. Justify the correctness and running time of your algorithm.