The Complexity Landscape of Partial-Observation Stochastic Games – Krishnendu Chatterjee, ATVA’14

Krishnendu heads of in a direction different from Monday’s tutorial talk altogether. Whereas on Monday he considered perfect information games, today he is considering games with imperfect information. Instead of a mean-payoff objective, he considers game graphs with a parity objective.

The motivation to consider games with imperfect information is that, in practice, the assumption that a controller knows everything is unrealistic since, e.g., systems have internal variables, and sensors are unreliable. In today’s talk, transitions are stochastic.

In the talk, a lot of different complexity results are discussed. Essentially, all combinations are considered where: player 1 has partial/perfect information and player 2 has partial/perfect information, and then for all these instances, three types of winning criteria are considered: sure winning, almost sure winning, and quantitative analysis.

His slides contain a number of nice comprehensive overview slides regarding the complexity results, so I would encourage you to check them out.

To conclude, I want you to give the following quote that came up during the talk. “In computer science, what God van do we can also do by non-determinism”.