We have an undirected graph G = (V, E) with V| players, in which each player i controls exactly one, distinct vertex Vi e V. Each edge e E E is associated with a nonnegative weight we. A cut is a partition of the set of vertices into two disjoint sets LEFT and RIGHT. Each player selects the set in which his controlled vertex will be, i.e. the strategy space of each player i is Qi = :{LEFT, RIGHT} and let a = (ai, ..., An) be the corresponding strategy profile. Let CUT(a) be the set of edges that have one endpoint in each set and let N; be the set of neighbours of vi in the graph G. The payoff of player i is defined as We Ui(a) = ECUT(a)nNi 1. Design a cut game in which the Price of Anarchy is 2. Hint:Use a graph with four vertices and unit weights. 2. Prove that the Price of Anarchy of cut games is at most 2 in the general case, not only for the game with 4 vertices. Hint: First argue that in a pure Nash equilibrium, the total weight of the neighbouring vertices of a vertex vi in the cut is at least half the total weight of all the neighbouring vertices of the vertex