Understanding Memoryless Determinacy of Parity Games
Explore the intricacies of memoryless determinacy in parity games through a comprehensive walkthrough of concepts such as complexity results, sub-games, attractors, and the determinacy theorem. Learn about the partitioning of vertices into 0-paradise and 1-paradise, alongside insights on non-deterministic algorithms, creating memoryless strategies, and checking winning strategies efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Memoryless Determinacy of Parity Games Itay Harel
Table of Contents Quick recap Complexity results Definitions and lemmas sub-games ?-traps Attractors ?-paradise Determinacy 3 important lemmas non-constructive proof
Quick recap parity games Game : (?,?,???) A arena : ?0,?1,? ? ? ? ? ? coloring function: ?:? ?, Acc winning condition for inf. In parity games: 0-player wins if max(??? ? ? Strategy: ?? ? ?? ?, a partial function ? is even
Determinacy Theorem: The set of vertices of a parity game is partitioned into a 0-paradise and a 1-paradise ? ???? M.W.S ? ???? M.W.S
Complexity class of finite parity games ???? = ?,? | ? ?? ? ?????? ?????? ???? ??? ? ?? ? ??????? ???????? ??? ?????? 0 Theorem: Theorem: ???? ?? ?? ??
???? ?? A non-deterministic algorithm: Given G and v, guess a memoryless strategy w Check whether w is a M.W.S Why is it O.K. to only guess memoryless? How can we check a strategy quickly?
Creating ?? A memoryless strategy w can be represented using a sub-graph of G: ?3 ?0 ?1 ?2 ?4
Checking a strategy (1) Check whether there exists a vertex ? such that: ? is reachable from ? ? ? is odd ? lies on a cycle in ?? containing only vertices of priority less or equal ? ? Claim: w is a winning strategy iff ? such a vertex doesn t exist
Checking a strategy (2) Let s assume such a vertex ? exists Observation: In ??, if a vertex is reachable from v, player-1 can force the token into it (formal proof with induction) Observation: In ??, if the token is inside a cycle of vertices, player-1 can force the token to go over the entire cycle A winning play for player-1: Force the token into ? Go over the cycle forever If ? exists, w is not a M.W.S Other direction very similar
???? ???? ?? We saw that: ???? ?? For ???? ?? ??, we need to show that for: ???? = ?,? | ? ?? ? ?????? ?????? ???? ??? ? ?? ? ??????? ???????? ??? ?????? 1 ???? ?? Exactly the same (switch odd with even)!
Sub-games Definition: Let U V be a subset of V. Denote: ? ? = |?,?|? The graph G[U] is a sub-game of G if every dead-end in G[U] is also a dead-end in G
Sub-game example ? = ?0,?1,?2,?3,?4,?5 ?3 is the only dead-end ?0 ?1 ?4 Let s look at ? = ?0,?1,?2,?3 G[U] is a sub-game of G Let s look at ? = ?0,?1,?2 ,?4 G[W] not a sub-game ?2 ?5 ?3
Sub-games lemma Claim: Let ? and ? be subsets of V s.t. ? ? ? If?[?] is a sub-game of ? and ? ? [? ] is a sub-game of ?[?] then ?[? ] is a sub-game of G Proof: Notice that ? ? ? = ?[? ] If ? ? is a dead-end in ? ? , it is a dead-end in ? ? Since ? ? ? is a sub-game of ? ? , v is a dead-end in ? ? Using the same argument, v is a dead-end in ? ?
? ????? In English: ? can t force the token out of U, ? can always stay inside U. ? is trapped . Definition: A set ? ? will be called a ? ???? if: 1. ? ?? ? ?? ? 2. ? ? ? ? ?? ? ?
? ????? example 1 ????: ?0,?7 0 ???? ?0,?1,?2,?3,?7
? ????? lemmas (1) Claim 1: For every ? trap U in G , ?[?] is a sub-game of ? Proof: Let ? ? be a dead-end in ? ? . If ? ?? ? then ?? ? , which means v was a dead-end in ?. If ? ? ? ? then ?? ? ?, which means it can t be a dead-end in ? ?
? ????? lemmas (2) Claim 2: For every family ?? ??? of ? traps the union ??is a -trap as well. Proof: Trivial
? ????? lemmas (3) Claim 3: Let X be a -trap in G and Y is a subset of X Y is a -trap in G iff Y is a -trap in G[X] Proof : Doodle time
Attractor Sets Mathematical definition was given in chapter 2 For a game G and a set ? ?, denote ?????(?,?)as: The set of vertices from which Player has a strategy to attract the token to X or a dead-end in ? ?in a finite (possibly 0) number of steps Claim: Said strategy can be memoryless
Attractor Sets example ?0 ?1 ?5 X ?2 ?4 ?3 ?6 ?7
Attractor sets lemmas (1) Claim 1: The set ?\Attr?(?,?)is a -trap in G. Proof: Let us look at ? ?\Attr?(?,?) If ? ?? and ?? Attr? ?,? ? then: There is a move can do to take the token to some ? ???? ?,? From ?, there is a -strategy that reaches a member of X in a finite set of moves This means that there is a -strategy that reaches X from ? in a finite set of moves ? ???? ?,? in contradiction If ? ?? then ?? ?\??????,?
Attractor sets lemmas (2) Claim 1: The set ?\Attr?(?,?)is a -trap in G. Proof (cont.): If ? ? ? and ?? (V\Attr? ?,? ) = ? then: Notice that v can t be a dead-end. ?? Attr? ?,? ? ? must move the token to some ? ???? ?,? From ?, there is a -strategy that reaches a member of X in a finite set of moves This means that there is a -strategy that reaches X from ? in a finite set of moves ? ???? ?,? in contradiction If ? ? ? then ?? (?\????? ?,? ) ?
Attractor sets lemmas (3) Claim 2: If X is a -trap in G, then so is ???? ??,? Proof: Trivial Do a doodle proof! Claim 3: X is a -trap in G iff??????,?\X = ?\X Proof: Another doodle proof
Attractor sets lemmas (4) Claim 4: ??????,? = ? \ U where U is the greatest (w.r.t. set inclusion) -trap contained in ? \ ? Proof: Is U well defined? ? is a -trap so there is at least one -trap. Further more, union of -traps is a -trap, which means U is well defined! Now doodle away!
? ???????? In English: A region from which: 1. ? cannot escape 2. wins from all vertices of this region using a memoryless strategy Definition: A set ? ? will be called a ? ???????? if: 1. U is a ? ???? 2. ?? ?? ? ?.?.? ??? ? ?? ?
? ???????? ?????? (1) Claim 1: If U is a -paradise, then so is ??????,? Proof: U is a ? ????, which means that ??????,? is also a a ? ???? Also, we know that player ? has a memoryless strategy from ??????,? that either: 1. Brings the token to U 2. Brings the token to a dead-end for ? Combine said strategy with ?? and you get a M.W.S for ??????,?
? ???????? ?????? (2) Claim 2: For every family ?? ??? of ? paradises the union ??is a -paradise as well Proof: A union of ? ????? is a ? ????, which means that U is a ? ???? We will find a M.W.S using Rom s trick! Denote ?? the M.W.S on ?? for player ? Define a well-ordering relation < on ?. Define the strategy: ? ? ?? ??? ? ? = ??(?) where i is the least element of I s.t. ? ?? It s easy to see that using said construction, a play p is either finite and ends with a dead-end to ?, or infinite and its suffix conforms with some ??
Another quick recap! Sub-game: a sub graph with no new dead-ends ? ????: a sub set of the arena from which: ? can t leave ? can always stay ?0,?1,? ? ? ? ? ?????(?,?) all vertices from which ? can: Force ? to a dead-end Force the game into X ? paradise: ? can t leave ? has a M.W.S
Determinacy Theorem: The set of vertices of a parity game is partitioned into a 0-paradise and a 1-paradise We will prove this using an induction over ? max(?? ? )
Base case: n = 0 Lemma 0: If the maximum parity of G is 0, then V is partitioned into a 0 and a 1-paradise Proof: Observation: player 1 can only win by taking player 0 to a dead-end The winning region of player 1 is ????1(?,?) From above lemmas, ????1(?,?) is a 1-paradise (why?) Let s look at ?\Attr1?,? From above lemmas, we know that it is a 1-trap. Also, since the maximum parity is 0, and there are no dead-ends for 0 in ?\Attr1?,? , 0 always has a winning strategy! ?\Attr1?,? is a 0-paradise and ????1(?,?) is a 1-paradise
The construction (1) Induction step: assume the theorem holds for every parity game with maximum parity less than n Let us mark ? ? ??? 2 Let ? ? be a ? ???????? s.t. ?? ?\? ? ?? ? ? ???? Define: ? = ? ?? ? ? = ?} Define ? = ??\Attr(? ??,?)
The construction (2) A few observations: ?? is a trap ? ?? is a sub-game of ? Z is a -trap in ? ?? since it is the complement of an Attr set From the above ? ??[?] is a sub-game of ? ?? From a previous lemma: ? ? is a sub-game of ?
The construction (3) A few more observations: ????? ?|? 0,1,2, ,? 1 The induction hypothesis applies to ? ? ! We can partition Z to ?0 and ?1 - 0 and 1 paradises in ? ?
Important lemma Lemma 1: ? ? ????? ? ? ? ? ?? ? ? ???????? Proof: Let s look at the sketch
Last lemma before we win! Lemma 2: ?? ? ?= ?,? ?? ?? ?? ? ? ???????? Proof: Let s look at the sketch
So whats left? We need to find ?? ,? ? such that: ? ? is a ? ???????? ?? ( ?\? ?) is a ? ???? ? ? is the empty set Reminder: we saw that ? ? ? ? ?? ? ? ???????? Maybe, if ? ? is the maximal ? ????????, we can finish ?
Creating ? ? ?????? ? ? ?? ?? ? ? ??? ?? ??? ? ????????s ? ?= ? ? ?? : since paradises are close under union, ? ? is the largest ? ???????? We have seen before that the attractor set of a paradise is still a paradise ???? ??,? ? ?? ? ? ???????? Since ? ? is the largest paradise: ? ?= ???? ??,? ? We have seen before that the complement of an attractor set is a trap: ??= ?\? ?= ?\???? ??,? ? ?? ? ? ???? Just like we wanted!
Proving determinacy Theorem: The set of vertices of a parity game is partitioned into a 0-paradise and a 1-paradise. Outline: Do an induction over ? max(?? ? ) We have proved the base case We shall define ? ? as the union of all ? ????????? and ?? as its complement Use lemma 1 to show that ? ? is a ? ???????? Use lemma 2 to show that ?? is a ? ????????
