An Objective Improvement Approach to Solving Discounted Payoff Games
Daniele Dell’Erba, Arthur Dumas, Sven Schewe · Electronic Proceedings in Theoretical Computer Science · 2023
While discounted payoff games and classic games that reduce to them, like parity and mean-payoff games, are symmetric, their solutions are not. We have taken a fresh view on the constraints that optimal solutions need to satisfy, and devised a novel way to converge to them, which is entirely symmetric. It also challenges the gospel that methods for solving payoff games are either based on strategy improvement or on value iteration.