Candidate: Thomas Gao
Date: November 20, 2024
Time: 8:00am
Location: online
Supervisor: Chrystopher L. Nehaniv
All are welcome!
Abstract:
Expanding upon Rhodes' 2009 study on game complexity using Krohn-Rhodes theory, this seminar bridges game theory and algebraic automata theory through three key parts. First, we introduce essential concepts from semigroup and Krohn-Rhodes theories and propose novel algorithms to calculate complexity lower bounds for transformation semigroups. Second, we analyze simple two-player games like Tic-Tac-Toe, considering symmetries to reduce state spaces and evaluating their algebraic structures to verify some of Rhodes' conjectures. Third, we extend our analysis to extensive-form games, tackling challenges with non-determinism in mixed strategies by proposing new constructions that enable algebraic complexity analysis.