TCS3 Assignment Check DUO for the submission deadline. You must reference any sources used. Please keep submit your solutions in a single pdf file. Full justification is required in each solution. The marks available for correct answers to each question are indicated. Partial credit will be given for good attempts. Complexity and Approximability Question 1 Let Short Path be the following problem: Instance: An undirected graph G, two vertices s, t in it and a number k > 0. Question: Does G have a path from s to t of length at most k? Let Short Path-2019 be the same problem as above, but with k ≤ 2019. 1. Show that Short Path is NL-complete. [25 marks] 2. Show that Short Path-2019 belongs to the complexity class L. [5 marks] Question 2 [20 marks] Let Two Cliques be the following problem: Instance: An undirected graph G = (V,E). Question: Are there two disjoint non-empty subsets V1 and V2 in V such that V = V1 ∪ V2 and each Vi is a clique? It is obvious that Two Cliques is in NP, so it cannot be PSPACE-complete, assum- ing that NP 6= PSPACE. However, it is open whether NP 6= PSPACE. Prove un- conditionally (i.e. without using any unproven assumptions) that Two Cliques is not PSPACE-complete with respect to logspace reductions. Algorithmic Game Theory Question 3 A community of n ≥ 3 people benefit from a piece of work that could be completed by two or more volunteers. They receive payoffs that are the same for every member and are as follows. 1. If you volunteered, you get 9. 2. If you didn’t volunteer but the work was done by others, you get 10. 3. If you didn’t volunteer and the work wasn’t done (because fewer than two others volunteered), you get 8. Find all pure-strategy equilibria. [10 marks] Find all symmetric mixed-strategy equlibria (i.e. the ones where all players have the same mixed strategy). For this part, determining the probability for volunteering as the solution of e.g. some polynomial equation is OK, in which case you may need to argue that such a solution exists. [25 marks] Question 4 [15 marks] Show that a Boolean function f (p1, p2) can be computed by a three-player game. That is, each player has two pure strategies that are the Boolean values T and F , and there’s a pure-strategy Nash equilibrium if and only the strategy of player three, p3 = f (p1, p2) where p1and p2 are the strategies of players one and two, respectively. 2
