HW5

Submit a single .pdf (or handcopy) for the written problems to me via email/on canvas (or in person) by the date of the deadline (11:59 pm)

(1) Please show ALL of your work!!!!

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

1) Integer Programming 1: There are n people who need to be assigned to execute n jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i,j =1,...,n. The problem is to assign people to jobs to minimize the total cost of the assignment. Express the assignment problem as a 0-1 integer programming problem (where the domain of the variables is in {0, 1}). (10 points)

2) Reduction: Show that the Set Cover (SC) problem is NP-hard by reducing from Independent Set (IS). (15 points) Hints: (1) Use the decision version of SC, take an instance of IS and reduce it to an instance of SC, then (2) show that if there is a solution for the instance of SC, then you can map it to a solution of IS, and (3) if there is a solution for the instance of IS, then you can map it to a solution of SC.

3) Define a maximin strategy for player 2 in any 2-player zero-sum game. Write a linear program to compute a maximin strategy for player 2 in any 2-player zero-sum game. (10 points)

4) Two-player zero-sum games: Use linear programming to compute a mixed-strategy equilibrium of (It is sufficient to show only the linear program)

(a) Matching Pennies. (5 points)

(b) Rock-paper-scissors. (5 points)

5) Support Enumeration Method: Use SEM to find all Nash equilibria of (It is sufficient to show only the linear program)

(a) Battle of the Sexes (5 points)

(b) Rock-paper-scissors (you don't need to consider any support size of 1) (5 points)

6) Correlated equilibrium: Compute correlated equilibria of the following games (It is sufficient to show only the linear program):

(a) Prisoner’s Dilemma (5 points)

(b) Battle of the Sexes (5 points)