Algorithmic Game Theory and Applications
Lecture 13: Games on Graphs
Kousha Etessami AGTA: Lecture 12
Copyright By PowCoder代写 加微信 powcoder
checkmates! II wins!
Player II:
king trapped! automatic draw
checkmates! II wins!
unbounded chess
• Consider chess: the same exact “position” might recur in the game, but the “game tree” does not reflect this: no relationship between distinct nodes of the tree in a PI-game is indicated.
• There are finitely many positions in the game (≤ 6432). After a certain depth, every “play” of the game contains a recurrence of a position.
” without any artificial
• Consider “unbounded chess
stopping conditions: a game that goes on for ever
is by definition a draw .
Is this win-lose-draw game determined? I.e., does Zermelo’s theorem still hold?
AGTA: Lecture 12
more serious motivation
• We can often model the dynamics of a system (e.g., a running program) as a state transition system or state machine.
• If the system interacts with an environment, transitions out of some states can be viewed as “controlled by the environment”.
• Can the environment force the system, with any sequence of inputs, into a “error state”?
• Even for state machines without environments, questions like: “can I reach the reset state from all reachable states of the system?”, can be formulated as a game on a graph.
• Such queries, and much more, can be formalized in certain “temporal logics”. Temporal logics (TLs) are formal languages for describing relationships between the occurrence of events over time.
Efficiently checking such queries against a system model (e.g., a state transition system) is the task of “model checking”. Some key model checking tasks are intimately related to efficiently solving certain games on graphs.
(To learn more, e.g., attend my short TPG course on “Automata-Theoretic Model Checking”.)
AGTA: Lecture 12
game graphs and their trees
A 2-player game graph, G = (V, E, pl) consists of:
• A (finite) set V of vertices.
• A set E ⊆ V × V of edges.
• A function pl : V → {1, 2} mapping each vertex to the player whose turn it is to play at that
vertex. Let V1 = pl−1(1), and V2 = pl−1(2).
A game graph G together with a start vertex v0 ∈ V , defines a game tree Tv0 given by:
1. Action alphabet Σ=V. Thus Tv0 ⊆V∗.
2. ǫ∈Tv0,andwv′′ ∈Tv0,forv′′ ∈V,ifandonlyif
• w=ǫand(v0,v′′)∈E,or
• w = w′v′, for some v′ ∈ V , and (v′, v′′) ∈ E.
• Weextendtheplayermappl:V →{1,2}toa
map pl′ : Tv0 → {1, 2} as follows: pl′(ǫ) := pl(v0), and pl′(wv′) := pl(v′).
It is easy to confirm that Tv0 is a game tree, where Act(wv′) = {v′′ | (v′,v′′) ∈ E}, and it’s plays are precisely all paths in the graph G starting from v0.
AGTA: Lecture 12
games on graphs A game on a graph, Gv0, is given by:
A finite game graph G,
a vertex v0 ∈ V ,
and a payoff function u : ΨTv0 → R,
These together define a 2-player zero-sum PI-game with game tree Tv0 and player map pl′.
Note: We already know that even for win-lose payoff functions u, games on finite graphs are not in general determined, because the infinite binary tree {L, R}∗ is the game tree for the following game graph:
Player I: R R Player II:
and we already know (lecture 11) that there are sets Y of plays such that the win-lose game ⟨{L, R}∗, Y ⟩ is not determined.
So, let’s restrict the possible payoff functions. AGTA: Lecture 12
“history oblivious” payoffs
• Suppose there is some vertex v′ of graph G that is a “dead end”. E.g., in chess this could be a vertex “checkmate for Player I”.
• There may be multiple ways to end up in vertex v′. But we would like the winner to be the same for any finite play wv′ ∈ V ∗. I.e., u(wv′) = u(w′v′), for any finite plays wv′ and w′v′.
So, the payoff is “history oblivious”.
• What about for infinite plays π?
We can think of π as an infinite sequence v0v1v2v3v4v5 ……, where each vi ∈ V .
We use the notation π ∈ V ω.
• Forπ=v0v1…,let
inf(π)={v∈V |for∞-manyi∈N,vi =v}
• Let’s call payoff function u() history oblivious1 (h.o.), if for all infinite plays π and π′,
if inf(π) = inf(π′), then u(π) = u(π′) and for all finite complete plays wv and w′v,
u(wv) = u(w′v).
Call a graph game h.o. if its payoffs are h.o.
We will only consider h.o. games (and often less).
1Technically, we are dispensing with more information here, beyond the info. in finite histories, but never mind the ill-chosen name.
AGTA: Lecture 12
“finitistic” payoffs
• Note that in chess, if the play π is infinite, then the play is always a draw, i.e., u(π) = 0.
• Let’s call an h.o. payoff function finitistic if for all infinite plays π and π′, u(π) = u(π′).
Let’s call a game on a graph Gv0 finitistic if its payoff function is.
So, in win-lose-draw finitistic games, infinite plays are either all wins, all losses, or all draws, for player 1.
Question: Are all finitistic games on graphs determined?
Answer: Yes…………..
In fact, more it true: for finitistic games there is always a memoryless strategy for each player that achieves the value of the game, and we can efficiently compute these strategies.
AGTA: Lecture 12
memoryless strategies and determinacy
Definition For a game Gv0, a strategy si for player i is a memoryless strategy if
for all wv, w′v ∈ Pl′i, si(wv) = si(w′v), and
if wv0 ∈ Pl′i then si(wv0) = si(ǫ).
I.e., the strategy always makes the same move from a vertex, regardless of the history of how it got there.
Let MLSi denote the set of memoryless strategies for player i. Note MLSi is a finite set, even if Si is not. In particular, if m = |Pli| is the number of vertices belonging to player i, then |MLSi| ≤ |Σ|m.
Definition Gv0 is memorylessly determined if both players have memoryless strategies that achieve “the value” of the game. I.e.,
max inf u(s1, s2) = min sup u(s1, s2) s1∈MLS1 s2∈S2 s2∈MLS2 s1∈S1
Theorem A Finitistic games on finite graphs are memorylessly determined. Moreover, there is an efficient (P-time) algorithm to compute memoryless value-achieving strategies in such games.
AGTA: Lecture 12
the win-lose case:
easy “fixed point” algorithm
We first prove the theorem for finitistic win-lose games via an easy “bottom up” fixed point algorithm.
Input: Game graph G = (V, E, pl, v0).
We assume w.l.o.g. that all infinite plays are a win for player 2 (the other case is symmetric).
A “dead end
” is a vertex with no outgoing edge.
Good:={v∈V |vadeadendthatwinsforplayer1}. Bad:={v∈V |vadeadendthatwinsforplayer2}.
1. Initialize: W in1 := Good; S t1 := ∅;
Foreach v ̸∈ Win1:
If(pl(v)=1 & ∃(v,v′)∈E: v′∈Win1) Win1 := Win1 ∪{v}; St1 := St1 ∪{v → v′};
If(pl(v)=2 & ∀(v,v′)∈E: v′∈Win1) W in1 := W in1 ∪ {v};
Until The set Win1 does not change;
Player 1 has a Win.-Strategy iff v0 ∈ W in1. If so,
St1 is a memoryless winning strategy for player 1.
AGTA: Lecture 12
why does this work?
Proof of Theorem A: (for the win-lose case)
• First, we claim that for each v ∈ Win1, St1 is a winning strategy for player 1 in the game Gv (i.e.,
the game that starts at node v).
Suppose v ∈ Win1. It must have entered Win1 after, say, m iterations of the repeat loop. By induction on m, if player 1 plays according to (partial) strategy St1, then it is guaranteed a win in the game Gv within m moves. Note that St1 may be partial: it may only tell us how to move from some vertices. This won’t matter.
Base case: m = 0, v ∈ Good.
Inductively: either v is player 1’s vertex or 2’s.
If it is player 1’s, then St1(v) = v′, where (v, v′) ∈ E and v′ ∈ Win1, and furthermore v′ entered W in1 by m − 1 iterations. By induction S t1 wins for player 1 from v′ in m − 1 moves.
If v is player 2’s, then we know that for all (v, v′) ∈ E, v′ ∈ W in1, and furthermore v′ entered W in1 by ≤ m − 1 iterations. Thus, no matter what move player 2 makes, in 1 move, by induction, we will be at a vertex v′ ∈ Win1 where player wins with St1 within m − 1 moves.
AGTA: Lecture 12
• Now consider v ̸∈ Win1 when algorithm halts. For each v′ ∈ pl−1(2), if ∃ (v′,v′′) ∈ E, with v′′ ̸∈ Win1, then pick one such v′′, and let St2 := St2 ∪ {v′ → v′′}. St2 may also be partial. We claim St2 is a memoryless winning strategy for player 2 in every game Gv, where v ̸∈ Win1. Suppose St2 is not a winning strategy for some v ̸∈ Win1. Then player 1 must be able to win by reaching a Good vertex within say, m moves from v against St2. Let’s show this is a contradiction. Base case: m= 0, but then v ∈ Good. ⇒⇐. Inductively: either v is player 1’s or player 2’s.
If player 1’s, then ∀(v, v′) ∈ E, v′ ̸∈ W in1, because otherwise by the algorithm v ∈ Win1. Suppose player 1’s winning strategy is to play (v,v′) ∈ E. It must have a win within m−1 moves from v′ ̸∈ W in1 against St2. ⇒⇐.
If it is player 2’s move, then one possibility is v ∈ Bad, (⇒⇐). Otherwise, St2(v) = v′ must be defined: since v ̸∈ Win1, there must exist (v, v′) ∈ E with v′ ̸∈ W in1. Otherwise, by the algorithm, v ∈ W in1.
By induction, player 1 must have a (m − 1)- winning strategy from v′ ̸∈ W in1.⇒⇐.
AGTA: Lecture 12
generalizing to finitistic zero-sum
The generalization is not hard:
In a finitistic game, there can only be a bounded number, r ≤ |V | + 1, of distinct payoffs u(π),
j1