  We study the problem of finding equilibrium strategies in multi-agent games
with incomplete payoff information, where the payoff matrices are only known to
the players up to some bounded uncertainty sets. In such games, an ex-post
equilibrium characterizes equilibrium strategies that are robust to the payoff
uncertainty. When the game is one-shot, we show that in zero-sum polymatrix
games, an ex-post equilibrium can be computed efficiently using linear
programming. We further extend the notion of ex-post equilibrium to stochastic
games, where the game is played repeatedly in a sequence of stages and the
transition dynamics are governed by an Markov decision process (MDP). We
provide sufficient condition for the existence of an ex-post Markov perfect
equilibrium (MPE). We show that under bounded payoff uncertainty, the value of
any two-player zero-sum stochastic game can be computed up to a tight value
interval using dynamic programming.
