辅导FIT5226、辅导Python/c++程序

日期：2022-10-07 07:46

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
Note: for the Python program, it can be assumed that for the program to run properly,
the user must introduce the information correctly, i.e., giving as input valid informa-
tion, in the correct format, according to the way the program was designed for use.