Parity and Mean-Payoff Games

After the note on my Bachelor's thesis, I decided to talk about my Master's thesis in computational complexity. The thesis concern is the complexity of solving certain kinds of infinite games on finite graphs, with special emphasis on Parity Games (Archived) and Mean-Payoff Games. For parity games a breakthrough in their solution complexity was obtained some years ago, while mean-payoff games are thought to be much more difficult to solve, and only subexponential algorithms are known.

In the thesis, together with my supervisor Marcello Mamino, we defined a new type of graph game which is of intermediate complexity between parity and mean-payoff games, and we presented algorithms to solve it.

By now you may reasonably be asking what a graph game is. Below you can see an example of a mean-payoff game.

![[Esempio Mean-Payoff Graph Game.svg]]

As you can see the game consists of a finite graph, whose vertices are owned by one of the two players of the game (which are usually called max and min in the case of mean-payoff games). The game starts with a pebble placed on an initial vertex $v_0$ , and at each time step the player owning the vertex $v_i$ on which the pebble is currently placed can move it through an outgoing edge, collecting a weight $w_i \in \bbZ$ (which you can see written on the edges).

Other graph games, such as parity, are played in the same way. The kind of game that is being played is determined by the winning formula that, given the infinite sequence of collected weights $\lrg{w_i}_{i \in \bbN}$ during a play, determines the winning player.

For mean-payoff the winner depends on the limsup of the partial weight sequences, i.e. on $\limsup_{k \rar \infty} \frac1k \sum_{i \le k} w_i;$ in this setting max wins if the limsup is positive, while min wins if the limsup is negative. The rule for parity games, on the other hand, is that max wins if the highest number occurring infinitely often is even (yes, quite a strange rule).

Graph games have multiple applications to economical modeling (where the market is seen as the other player), or to certain instances of job scheduling¹, to testing pivoting rules of the combinatorial simplex algorithm, and to model-check the $\mu$ -calculus, a logic used to describe finite transition systems. Moreover I would say that the underlying ideas can also be found in Reinforcement Learning (Archived).

Apart from applications, graph games are interesting to complexity theorists because their complexity class is contained in $\text{NP} \cap \text{coNP}$ , the class of problems for which there exists polynomially verifiable certificates both for their solubility and for their non-solubility. Very few problems (mainly factoring (Archived) and the [approximated Shortest Vector problem](https://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_ (Archived)(SVP))) are known in $\text{NP} \cap \text{coNP}$ . Moreover the class is thought to consist of "easy" problems, since if a problem there turns out to be $\text{NP}$ -complete, the whole polynomial hierarchy would collapse.

Another interesting thing about them is that we can put graph games themselves in a hierarchy via the concept of Turing-reducibility, thus ordering them "by hardness".

![[Graph Games CC Hierarchy.svg]]

The hierarchy of graph games has been known since the nineties², but the result that puts parity games in Quasi-Polynomial Time³ is from 2017, and has generated a cascade of adaptations of existing algorithms to make them also quasi-polynomials, like Succinct Progress Measures, Register-Index Techniques and Zielonka Algorithm.

Interestingly enough, lower bounds for the existing parity algorithms (Archived) have been proven, which highlights how research must move to search for different types of strategies, in the hope to prove that graph games are effectively in $\text{P}$ .

I hope to have sparked your interest in them with this brief introduction; if you are interested in knowing more about the algorithms that are effectively used to solve them you can skim over the slides of the master defense (in italian) or, if you are feeling brave, to the whole thesis (in english).

The so called scheduling with and/or constraints, i.e. when a job can be scheduled for execution when all jobs of a set have finished executing (and constraint) or when any job of a set has finished (or constraint). ↩
When the subexponential (Archived) bound was found for the most difficult type of graph games using the theory of LP-type problems (Archived). ↩
Quasi-Polynomial Time means that the problems can be solved in $O(e^{\log^\alpha n})$ where $\alpha \in \bbR$ and $n$ is the number of nodes in the graph. To get a grasp of what this means if $\alpha = 2$ then we get $O(n^{\log n})$ which is slightly worse than polynomial, thus the name of the class. ↩

Footnotes