Smoothed analysis of deterministic discounted and mean-payoff games
<|reference_start|>Smoothed analysis of deterministic discounted and mean-payoff games: We devise a policy-iteration algorithm for deterministic two-player discounted and mean-payoff games, that runs in polynomial time with high probability, on any input where each payoff is chosen independently from a sufficiently random distribution.   This includes the case where an arbitrary set of payoffs has been perturbed by a Gaussian, showing for the first time that deterministic two-player games can be solved efficiently, in the sense of smoothed analysis.   More generally, we devise a condition number for deterministic discounted and mean-payoff games, and show that our algorithm runs in time polynomial in this condition number.   Our result confirms a previous conjecture of Boros et al., which was claimed as a theorem and later retracted. It stands in contrast with a recent counter-example by Christ and Yannakakis, showing that Howard's policy-iteration algorithm does not run in smoothed polynomial time on stochastic single-player mean-payoff games.   Our approach is inspired by the analysis of random optimal assignment instances by Frieze and Sorkin, and the analysis of bias-induced policies for mean-payoff games by Akian, Gaubert and Hochart.<|reference_end|>
@article{loff2024smoothed,
    title={Smoothed analysis of deterministic discounted and mean-payoff games},
    author={Bruno Loff and Mateusz Skomra},
    journal={arXiv preprint arXiv:2402.03975},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.03975},
    primaryClass={cs.GT cs.CC}
}