FIT5226: Multi-Agent Systems and Collective Behaviour Assignment: Repeated Games and Logical Foundations. Due date: 7th October 2022 (23:55). Evaluation: 15 marks = 15%. Submission: Moodle. Exercise 1: Games on graphs with set-based goals [6] Let ~ = ( 0, . . . , 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, s0, E, S,⇤S), { i}i2N) a subgame of G is any game G = (N,M = (S, s⇤, E, S,⇤S), { i}i2N) such that there is a finite path s0 ! . . .! s⇤ from s0 to s⇤ in the underlying graph M where the game is played. Using these definitions, your task in this exercise is to design four di↵erent 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) = ; and NE(G) 6= ;. Specifically, design a di↵erent game for the following set-based goals: Reachability [1.5/6.0]; Safety [1.5/6.0]; Bu¨chi [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 ~ = ( 0, . . . , n) be a strong Nash equilibrium (SNE) if for every coalition of players C ✓ N and every alternative joint strategy profile for C, denoted by ~ 0C = ( 0k, . . . , 0m), with {k, . . . ,m} = C, we have uj(⇢(~ )) uj(⇢(~ C ,~ 0C)) for every player j 2 C. That is, in an SNE no coalition of players, C, prefers a run di↵erent from the run ⇢(~ ) induced by the strategy profile ~ , 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) ✓ 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) = ; andNE(G) 6= ;. Clearly indicate at least one Nash equilibrium of G which verifies that NE(G) 6= ;. Exercise 3: Boolean games [5] Write a program in Python that takes as input a Boolean game G and checks whether NE(G) 6= ;. In case the game, G, has a Nash equilibrium, present one to the user. [Hint: these are win-lose games, where only the players that do not get their Boolean logic goal achieved may have an incentive to deviate; for this exercise, use the definition of a Nash equilibrium, as seen in the lectures, and exhaustive search over the finite set of strategy profiles to check if the Boolean game has a Nash equilibrium or not.] Exercise 4: Reactive Modules games [2] Write a Reactive Modules (RM) specification of a game (an SRML script) such that the RM game has a Nash equilibrium if and only if a given LTL formula is valid. 2 Additional notes. The following games are given as an Example only. Students are allowed to present their solutions in the way they think it is best, as long as it is clear and well presented. A solution for Exercise 1 can be given using the following format (as a table) to represent memoryless strategies in a game on a graph – as seen in the lectures: The strategy profile in the table induces the unique run: ⇢( 0, 1) = s 0 s2 s 0 s2 s 0 s2 s 0 s2 s 0 s2 . . . Regarding Exercise 3, the Python program may have an interface as follows: Players = 3 Phi = x y z w r Phi0 = x y Phi1 = z w Phi2 = r gamma0 = (x /\ y) -> z gamma1 = (y \/ z) <-> w gamma2 = !(x -> !r) HasNE = Yes NE = x:T y:F z:T w:T r:T for a Boolean game G = ⇣ N = {0, 1, 2}, = {x, y, z, w, r}, 0 = {x, y}, 1 = {z, w}, 2 = {r}, { i}i2N ⌘ with