Fair omega-Regular Games

on YouTube ↗24m

" summary

Defines games where both players must use designated fair moves and gives a formal winning rule: if one player is fair and the other not the fair player wins, if both fair use α, if both unfair use β. Proves determinacy, gives a gadget-based polynomial reduction from fair parity/parity to ordinary parity (gadgets add priorities up to 2K+2 and yield linear blowup when β is trivial), and supplies a direct symbolic fixpoint algorithm and a memory encoding (two values per node) that yields quasi‑polynomial solvability.

AI-written summary · about

" chapters (12)

1. 0:00Fair omega-regular games intro
2. 2:52Games in verification motivation
3. 3:55Parity games as verification
4. 8:03Solving standard parity games
5. 8:24Fair parity games single-player
6. 10:51Fair to standard parity reduction
7. 14:40Fairness for both players
8. 16:31Defining Fair Alpha-Beta games
9. 17:33Fair Alpha-Beta subclasses
10. 19:20Fair Alpha-Beta to parity reduction
11. 20:49Framework summary
12. 21:54Q&A