Exercise 1: Games on graphs with set-based goals [6] Let o = (60, . . ., 'n) be a subgame-perfect Nash equilibrium (SPNE) if it represents a Nash equilibrium strategy profile in every subgame. For a game on a graph G = (N, M = (S, s', E, As, As), {viliEN) a subgame of G is any game G = (N, M = (S, s*, E, As, As), {VitiEN) such that there is a finite path so -> . .. > s* from so to s* in the underlying graph M where the game is played. Using these definitions, your task in this exercise is to design four different games on graphs with set-based goals and memoryless strategies (only) such that each game has a non-empty set of Nash equilibria and an empty set of subgame-perfect Nash equilibria, that is, four games G satisfying that SPNE(G) = 0 and NE(G) # 0. Specifically, design a different game for the following set-based goals: Reachability [1.5/6.0]; Safety [1.5/6.0]; Buchi [1.5/6.0]; Parity [1.5/6.0]. For each game above, clearly indicate a Nash equilibrium of G and a subgame of G (that is, the state/ vertex s* in the graph) without a Nash equilibrium, along with the set of players that have a unilateral beneficial deviation in the subgame rooted at s*. Exercise 2: Games on graphs with numeric goals [2] Let o = (60, . .., On) be a strong Nash equilibrium (SNE) if for every coalition of players C C N and every alternative joint strategy profile for C, denoted by o' = (ok, . ..,0m), with {k, . .., m} = C, we have uj (p()) 2 uj(p(o_c, 'c)) for every player j E C. That is, in an SNE no coalition of players, C, prefers a run different from the run p(6) induced by the strategy profile o, and therefore no deviations by coalitions of players are possible; since in a Nash equilibrium only single-player deviations are considered (that is, when (C| = 1), we have that for every game G, it is true that SNE(G) C NE(G), where SNE(G) denotes the set of strong Nash equilibria of a given game G. Using these definitions, your task in this exercise is to design a game on a graph with numeric goals such that the game has a non-empty set of Nash equilibria and an empty set of strong Nash equilibria, that is, a game G satisfying that SNE(G) = 0 and NE(G) # 0. Clearly indicate at least one Nash equilibrium of G which verifies that NE(G) # 0