Version:0.9
StartHTML:0000000105
EndHTML:0000052836
StartFragment:0000000141
EndFragment:0000052796
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 profifile in every subgame. For a game on a graph
G = (N,M = (S, s
0
,E, #S,⇤S),
{
$i
}
i
2
N )
a subgame of G is any game
G = (N,M = (S, s⇤
,E, #S,⇤S),
{
$i
}
i
2
N )
such that there is a fifinite path s
0
!
...
!
s⇤ from s
0
to s⇤ in the underlying graph M
where the game is played. Using these defifinitions, 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) =
;
. Specififically, design a di↵erent game for the following set-based goals:
Reachability [1.5/6.0]; Safety [1.5/6.0]; B¨uchi [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 benefificial 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 profifile 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 profifile ~", 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 defifinitions, 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) =
;
and NE(G) =
;
.
Clearly indicate at least one Nash equilibrium of G which verififies that NE(G) =
;
.
Exercise 3: Boolean games [5]
Write a program in Python that takes as input a Boolean game G and checks whether
NE(G) =
;
. 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 defifinition
of a Nash equilibrium, as seen in the lectures, and exhaustive search over the fifinite set
of strategy profifiles to check if the Boolean game has a Nash equilibrium or not.]
Exercise 4: Reactive Modules games [2]
Write a Reactive Modules (RM) specifification 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.
2Additional 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 profifile 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
}
i
2
N
⌘
with
$0 = (x
^
y)
!
z $1 = (y
_
z)
$
w $2 =
¬
(x
! ¬
r)
which has a Nash equilibrium ~" = ("0, "1, "2) such that:
•
"0(x) = T and "0(y) = F
•
"1(z) = T and "1(w) = T
•
"2(r) = T
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.
