Beyond worst-case analysis for mean-payoff games

Speaker(s)

Lorenzo Clemente

Affiliation

Uniwersytet Warszawski

Date

Oct. 15, 2014, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Mean-payoff games are classical quantitative games where the objective is to optimise the long-term average payoff.
In this purely adversarial setting, one is interested in whether Player 0 has a strategy that guarantees a certain mean-payoff against every strategy of Player 1.
It is well-known that mean-payoff games are memoryless determined,
and that the winner can be decided in NP \cap coNP (membership in PTIME is a long-standing open problem).

However, modelling Player 1 as a totally adversarial opponent is overly pessimistic in some situations.
Suppose Player 1 promises to use a fixed (finite-memory, randomised) strategy.
In this case, Player 0 can do better than in the worst-case,
and try to optimise the expected mean-payoff against this specific opponent.
This essentially boils down to solve a 1-1/2 player mean-payoff game, which can be done in PTIME.

In the beyond worst-case setting, Player 1 declares a strategy, but he might or might not play according to it.
Then, the goal is to maximise the expected mean-payoff provided Player 1 fulfills his promise,
and, at the same time, to guarantee a certain (usually lower) worst-case mean-payoff against *any* behaviour of Player 1.
These two objective are usually conflicting, and infinite-memory is more powerful in general.
We show a solution for deciding in NP \cap coNP whether Player 1 can win with finite-memory.

The 1-dimensional case has been studied by Bruyère-Filiot-Randour-Raskin (STACS'14).
The technically more involved case with tuples of payoffs is under active investigation (jointly with Raskin).

---