<p>Here is a rather different application from what you may have had in mind. Linear programming has many practical applications. There are many algorithms for linear programming and those based on George Dantzig's <a href="http://en.wikipedia.org/wiki/Simplex_algorithm" rel="nofollow">simplex method</a> are among the most commonly implemented. An important parameter of simplex is called the pivoting rule. <a href="http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube" rel="nofollow">Victor Klee and George Minty</a> provides a set of polytopes on which the pivoting rule suggested by Dantzig would require an exponential number of pivoting steps. Since then, examples demonstrating an exponential lower bound have been discovered for nearly every deterministic pivoting rule.</p>

<p>Simplex can however use randomized pivoting rules. <a href="http://dl.acm.org/citation.cfm?id=129759" rel="nofollow">Gil Kalai in 1992</a> introduced a randomized pivoting rule and proved a sub-exponential upper bound for simplex with this rule. Also in 1992, Micha Sharir and Emo Welzl defined <a href="http://en.wikipedia.org/wiki/LP-type_problem" rel="nofollow">LP-type problems</a> which include  standard linear programming and <a href="http://dl.acm.org/citation.cfm?id=142678" rel="nofollow">with    Jiří Matoušek</a> also proposed randomized variants of simplex and proved subexponential upper bounds for this variant. Subexponential lower bounds were also discovered on LP-type problems, but till about 2010 there were no concrete examples of linear programs on which these lower bounds could be demonstrated. See these <a href="https://gilkalai.wordpress.com/2010/11/09/subexponential-lower-bound-for-randomized-pivot-rules/" rel="nofollow">two</a> <a href="https://gilkalai.wordpress.com/2008/11/04/a-diameter-problem-6-abstract-objective-functions/" rel="nofollow">posts</a> on Gil Kalai's blog for another telling of this story, the connection to the Hirsch conjecture and links to the literature.</p>

<p>What does any of this have to do with parity games? A couple of steps are required to set up a connection. An open problem in parity games research till about 2009 was to determine if certain policy iteration algorithms for solving parity games might have exponential behaviour. See the <a href="http://www.dcs.warwick.ac.uk/~mju/Papers/" rel="nofollow">papers of Marcin Jurdziński</a> for more on this. Oliver Friedmann, <a href="http://oliverfriedmann.com/science/publications/" rel="nofollow">starting in 2009</a>, exhibited examples of parity games on which certain policy iteration algorithms required exponential time. By exploiting a connection between parity games and certain LP-type problems he derived sub-exponential lower bounds for various pivoting rules for simplex. (Note however that one of the results, which concerned the Random Facet algorithm was shown by <a href="http://arxiv.org/abs/1410.7871" rel="nofollow">Oliver Friedmann, Thomas Hansen and Uri Zwick</a> to be erroneous.)</p>

<p>I hope you'll agree that's a pretty fascinating and convincing example of an application of parity games. </p>

<p>There is a more direct answer to your question as well. Suppose one wants to design a discrete controller that regulates how some physical system (thermostat, chemical plant, etc.) behaves based on the state of the system and the state of the environment. The question of whether a controller exists to provide the guarantees a designer wants can be reduced to solving parity games. So you can think of a parity game in terms of systems, environments and controllers.</p>

<p>Another setting is program analysis. Suppose you want to automatically determine if a  program satisfies some correctness property in the modal $\mu$-calculus. Model checking is one approach to solving this problem and $\mu$-calculus model checking is deeply connected to parity games.  </p>

CC BY-SA 3.0
2015-02-01T13:34:32.757Z
The papers that introduced random facet proved subexponential **upper** bounds on the (expected) number of pivoting steps (currently the answer says lower bounds). The new lower bounds are of a similar form, i.e. subexponential, not exponential.
Rahul Savani
CC BY-SA 3.0
2015-02-02T03:49:18.647Z
It may be worth pointing out that some of the lower bounds by Friedmann, Hansen, and Zwick are flawed: http://arxiv.org/abs/1410.7871
Sasho Nikolov
CC BY-SA 3.0
2015-02-03T04:14:26.840Z
Thanks Sasho. This is what happens when I stop following the literature!
Vijay D
CC BY-SA 3.0
2015-02-01T03:31:43.750Z
2015-02-03T04:13:47.137Z
2015-02-03T04:13:47.137Z
Vijay D
<p>Are there examples of practical applications of parity games, ie systems, in the real world, that can be represented as parity games ?</p>

<p>Usually related documentation on parity games has almost never a practical example of this application.</p>

CC BY-SA 3.0
2015-01-29T16:14:08.923Z
The game semantics of [modal μ-calculus](http://en.wikipedia.org/wiki/Modal_%CE%BC-calculus) is related to two-player games with perfect information, particularly infinite parity games. See also section [Relation with logic and automata theory](http://en.wikipedia.org/wiki/Parity_game#Relation_with_logic_and_automata_theory) in the wikipedia article on parity games.
Thomas Klimpel
CC BY-SA 3.0
2015-01-30T13:42:16.787Z
It is not really meant to be directly applied, but rather as an important part of theories (automata,games,logics) having other applications.
Denis
<lo.logic><two-player-games>
Practical applications of parity games
kafka
# Practical applications of parity games

(Asked by: username_0 on 2015-01-29)

Are there examples of practical applications of parity games, ie systems, in the real world, that can be represented as parity games ?

Usually related documentation on parity games has almost never a practical example of this application.

**Tags:** lo.logic, two-player-games

> **Comments:**
> **username_1**: The game semantics of [modal μ-calculus](http://en.wikipedia.org/wiki/Modal_%CE%BC-calculus) is related to two-player games with perfect information, particularly infinite parity games. See also section [Relation with logic and automata theory](http://en.wikipedia.org/wiki/Parity_game#Relation_with_logic_and_automata_theory) in the wikipedia article on parity games.  
> **username_2**: It is not really meant to be directly applied, but rather as an important part of theories (automata,games,logics) having other applications.  

---

## 1 answers

### Answer by username_3 on 2015-02-01. Score: 11 | Accepted answer

Here is a rather different application from what you may have had in mind. Linear programming has many practical applications. There are many algorithms for linear programming and those based on George Dantzig's [simplex method](http://en.wikipedia.org/wiki/Simplex_algorithm) are among the most commonly implemented. An important parameter of simplex is called the pivoting rule. [Victor Klee and George Minty](http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube) provides a set of polytopes on which the pivoting rule suggested by Dantzig would require an exponential number of pivoting steps. Since then, examples demonstrating an exponential lower bound have been discovered for nearly every deterministic pivoting rule.

Simplex can however use randomized pivoting rules. [Gil Kalai in 1992](http://dl.acm.org/citation.cfm?id=129759) introduced a randomized pivoting rule and proved a sub-exponential upper bound for simplex with this rule. Also in 1992, Micha Sharir and Emo Welzl defined [LP-type problems](http://en.wikipedia.org/wiki/LP-type_problem) which include standard linear programming and [with Jiří Matoušek](http://dl.acm.org/citation.cfm?id=142678) also proposed randomized variants of simplex and proved subexponential upper bounds for this variant. Subexponential lower bounds were also discovered on LP-type problems, but till about 2010 there were no concrete examples of linear programs on which these lower bounds could be demonstrated. See these [two](https://gilkalai.wordpress.com/2010/11/09/subexponential-lower-bound-for-randomized-pivot-rules/) [posts](https://gilkalai.wordpress.com/2008/11/04/a-diameter-problem-6-abstract-objective-functions/) on Gil Kalai's blog for another telling of this story, the connection to the Hirsch conjecture and links to the literature.

What does any of this have to do with parity games? A couple of steps are required to set up a connection. An open problem in parity games research till about 2009 was to determine if certain policy iteration algorithms for solving parity games might have exponential behaviour. See the [papers of Marcin Jurdziński](http://www.dcs.warwick.ac.uk/~mju/Papers/) for more on this. Oliver Friedmann, [starting in 2009](http://oliverfriedmann.com/science/publications/), exhibited examples of parity games on which certain policy iteration algorithms required exponential time. By exploiting a connection between parity games and certain LP-type problems he derived sub-exponential lower bounds for various pivoting rules for simplex. (Note however that one of the results, which concerned the Random Facet algorithm was shown by [Oliver Friedmann, Thomas Hansen and Uri Zwick](http://arxiv.org/abs/1410.7871) to be erroneous.)

I hope you'll agree that's a pretty fascinating and convincing example of an application of parity games.

There is a more direct answer to your question as well. Suppose one wants to design a discrete controller that regulates how some physical system (thermostat, chemical plant, etc.) behaves based on the state of the system and the state of the environment. The question of whether a controller exists to provide the guarantees a designer wants can be reduced to solving parity games. So you can think of a parity game in terms of systems, environments and controllers.

Another setting is program analysis. Suppose you want to automatically determine if a program satisfies some correctness property in the modal $\mu$-calculus. Model checking is one approach to solving this problem and $\mu$-calculus model checking is deeply connected to parity games.

> **Comments:**
> **username_4**: The papers that introduced random facet proved subexponential **upper** bounds on the (expected) number of pivoting steps (currently the answer says lower bounds). The new lower bounds are of a similar form, i.e. subexponential, not exponential.  
> **username_5**: It may be worth pointing out that some of the lower bounds by Friedmann, Hansen, and Zwick are flawed: http://arxiv.org/abs/1410.7871  
> **username_3**: Thanks Sasho. This is what happens when I stop following the literature!  

---

