{"id":630,"date":"2015-10-15T17:10:32","date_gmt":"2015-10-15T15:10:32","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=630"},"modified":"2015-10-26T14:47:02","modified_gmt":"2015-10-26T13:47:02","slug":"memoryless-determinacy-of-parity-games","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/games-with-%cf%89-regular-winning-conditions\/memoryless-determinacy-of-parity-games","title":{"rendered":"Memoryless determinacy of parity games"},"content":{"rendered":"

In this page, we prove the following theorem:<\/p>\n

Theorem (Memoryless Determinacy of Parity Games).\u00a0<\/strong>In a parity game, one of the players has a memoryless winning strategy.<\/p>\n

Recall that in a parity game, the positions are assigned ranks from a set \"\set{0,\ldots,n}\", and the goal of player 0 is to ensure that for infinite plays, the minimal\u00a0number appearing infinitely often is even. The proof of the theorem is by induction on the number of ranks used in the parity game.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

Attractors<\/strong><\/p>\n

Consider a set of positions \"X\" in a parity game (actually the winning condition is irrelevant for the definition). For a\u00a0player \"i \in \set{0,1}\", we define\u00a0below the \"i\"-attractor of \"X\"<\/em>, which intuitively represents positions where player \"i\" can force a visit to the set \"X\". The attractor is approximated using ordinal numbers \u2013 for an ordinal number \"\alpha\", define\u00a0\"X_\alpha\" to be \"X\" plus
\n\u2022 positions owned by player \"i\" where some outgoing edge leads to \"\bigcup_{\beta < \alpha} X_\beta\";
\n\u2022 positions owned by the opponent of \"i\" where all\u00a0outgoing edges lead to \"\bigcup_{\beta < \alpha} X_\beta\".
\nThe set \"X_\alpha\" grows as \"\alpha\" grows, and therefore at some point it stabilises. This stable set is called the \"i\"-attractor of \"X\"<\/em>. Over positions in the \"i\"-attractor, player \"i\" has a memoryless strategy which guarantees that after a finite number of steps, the game will end up in \"X\" or in a terminal position owned by the opponent of player \"i\".\u00a0This strategy, called the attractor strategy,\u00a0<\/em>\u00a0is to go toward \"X_\alpha\" with smaller and smaller index \"\alpha\".<\/p>\n

 <\/p>\n

\n

 <\/p>\n

Induction base.<\/strong><\/p>\n

The\u00a0induction base\u00a0is when only one rank is used. Let \"i\" be the parity of the only rank, without loss of generality we assume \"i \in \set{0,1}\".\u00a0This means\u00a0that\u00a0every infinite play is won by player \"i\". This does not necessarily mean that player \"i\" wins the game, because the game might end up in a terminal position owned by player \"i\".\u00a0 Let \"X\" be the \u00a0\"(1-i)\"-attractor of the empty set. We claim that on positions from \"X\", player \"1-i\" has a memoryless winning strategy, and on positions outside \"X\", player \"i\" has a memoryless winning strategy. For positions in \"X\", player \"(1-i)\" plays the attractor strategy, which guarantees reaching a terminal position owned by player \"i\" in a finite number of steps. For positions outside \"X\", we make the following observation, which follows immediately from the definition of \"X\":
\n\u2022 if player \"i\" owns a position outside \"X\", then\u00a0some\u00a0outgoing edge leads to a position outside \"X\";
\n\u2022 if player \"1-i\" owns a position outside \"X\", then all\u00a0outgoing edges lead to a position outside \"X\".
\nIt follows that if the play begins outside \"X\", then player \"i\" has a memoryless strategy that guarantees avoiding \"X\" forever, in particular this strategy is winning.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Induction step<\/strong><\/p>\n

 <\/p>\n

The proof is by induction on the number of ranks used<\/p>\n

Consider a parity game. For \"i \in \set{0,1}\" define\u00a0\"W_i\" to be the set of positions\u00a0\"v\" such that if the initial position is replaced by \"v\", then player \"i\" has a memoryless winning strategy.\u00a0Define \"U\" to be the vertices that are in neither \"W_0\" nor in \"W_1\". Our goal is to prove that \"W\" is empty. Here is the picture:<\/p>\n

\"trojpodzial\"<\/a><\/p>\n

Consider the minimal\u00a0rank that appears in the\u00a0entire\u00a0game, let it be \"n\". By symmetry, we assume that this minimal\u00a0rank is \"0\". (The symmetric case is when the minimal rank is \"1\".) \u00a0Define \"A\" to be the \"0\"-attractor, inside the game limited to \"U\", of positions that are in \"U\" and have minimal rank \"0\". Here is the picture of the game restricted to \"U\":<\/p>\n

\"partition<\/a><\/p>\n

In the original\u00a0game, if the play begins in a position from \"A\" and player \"0\" plays the attractor strategy on the set \"A\", then the play\u00a0is bound to either end up in a position in \"U\" that has rank \"0\", or in the set \"W_0\". Let us consider the game restricted to set \"U-A\". Since this game does not use rank \"0\", the induction assumption can be applied to get a partition of \"U - A\" into two sets of positions \"U_0\" and \"U_1\", such that on each \"U_i\" player \"U_i\" has a memoryless winning strategy, assuming that the game is limited to \"U - A\":<\/p>\n

\"partition<\/a><\/p>\n

 <\/p>\n

Here is how the sets \"U_0,U_1\" can be interpreted in terms of the bigger original game. For every \"i \in \set{0,1}\", if in the original\u00a0game, if the play begins in a position from \"U_i\" and player \"i\" uses the memoryless winning strategy corresponding to \"U_i\", then either the play stays forever in \"U-A\" and player \"i\" wins, or it eventually leaves \"U-A\".<\/p>\n

Here is a picture of the original game with all sets:<\/p>\n

\"ostateczny-podzial<\/a><\/p>\n

 <\/p>\n

Claim. <\/strong>\"U_1\" is empty.<\/p>\n

Proof. <\/strong>Consider the following memoryless strategy for player \"1\" in the\u00a0original\u00a0game:
\n\u2022 in\u00a0\"U_1\", use the winning memoryless strategy inherited from the game restricted to \"U-A\";
\n\u2022 in\u00a0\"W_1\", use the winning memoryless strategy from the definition of that set;
\n\u2022 on other positions do whatever.\u00a0
\n<\/strong>We claim that the above memoryless strategy is winning for all positions from \"U_1\", and therefore \"U_1\" must be empty by assumption on \"W_1\" being all positions where player \"1\" can win in a memoryless way. Suppose player \"1\" plays the above strategy, and the play begins in \"U_1\". If the play never leaves \"U - A\", then player \"1\" wins by assumption on the strategy. Suppose that the play does leave \"U-A\". If it enters \"W_0\" or \"A\", this would have to be a choice of player \"0\", but positions with such a choice already belong to \"W_0\" or \"A\". Therefore, if the play leaves \"U-A\", then it enters \"W_1\", where player \"1\" wins as well. \"\Box\"<\/p>\n

In the entire game, consider now the following memoryless strategy for player \"0\":
\n\u2022\u00a0in\u00a0\"U_0\", use the winning memoryless strategy inherited from the game restricted to \"U-A\";
\n\u2022\u00a0in\u00a0\"W_0\", use the winning memoryless strategy from the definition of that set;
\n\u2022 in \"A\" use the attractor strategy to reach rank \"0\" inside \"U\";
\n\u2022 on other positions, i.e. on \"W_1\", do whatever.<\/p>\n

We claim that the above strategy wins on all positions except for \"W_1\", and therefore the theorem is proved. We first observe that the play can never enter \"W_1\", because this would have to be a choice of player \"1\", and such choices are only possible in \"W_1\". \u00a0Next we observe that if the play enters \"W_0\", then player \"0\" wins by assumption on \"W_0\". Other plays will reach positions of rank \"0\" infinitely often, by using the attractor, or will stay in \"U_0\" from some point on. In the first case, player \"0\" will win by the assumption on \"0\" being the minimal rank. In the second case, player \"0\" will win by the assumption on \"U_0\" being winning for the game restricted to \"U-A\".<\/p>\n","protected":false},"excerpt":{"rendered":"

In this page, we prove the following theorem: Theorem (Memoryless Determinacy of Parity Games).\u00a0In a parity game, one of the players has a memoryless winning strategy. Recall that in a parity game, the positions are assigned ranks from a set , and the goal of player 0 is to ensure that for infinite plays, the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":615,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-630","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/630"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=630"}],"version-history":[{"count":6,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/630\/revisions"}],"predecessor-version":[{"id":714,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/630\/revisions\/714"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/615"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=630"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}