Fair Omega-Regular Games

Explore the concept of fair omega-regular games in this 24-minute conference talk from ACM SIGPLAN's GALOP'24. Delve into two-player games on finite graphs where both players face fairness constraints on their moves. Learn about the formalization of fair α/β games and their determinacy. Discover a polynomial reduction method for fair parity/parity games to normal parity games using a gadget construction. Examine a direct symbolic fixpoint algorithm for solving fair parity/parity games. Gain insights into the similarities between solution algorithms for fair and stochastic parity games, as well as fair games with single-player fairness restrictions. Presented by Daniel Hausmann, Nir Piterman, Irmak Saglam, and Anne-Kathrin Schmuck, this talk offers a comprehensive look at the intricacies of fair omega-regular games and their implications in game theory and formal methods.

[GALOP'24] Fair omega-Regular Games