Strategy complexities of some infinite games

Logic Seminar
November 28, 2023
1:50PM - 2:45PM
240 Stillman Hall

Date Range
Add to Calendar 2023-11-28 13:50:00 2023-11-28 14:45:00 Strategy complexities of some infinite games Title:  Strategy complexities of some infinite games Speaker:  Liling Ko (The Ohio State University) Abstract:  We apply techniques in computability theory to compare strategies of infinite variants of games. Within a variant of Monty Hall, we showed that a disorderly door-opening strategy is independently strong from a weakly-adaptive door-opening strategy. This result separates two notions of stochasticities. Within the game of chip-firing, we show that there are computable game instances that are winnable, but that do not have a computable winning strategy. We also characterize the index set of computable chip-firing instances as $\Pi_3$-complete. These are joint works with Justin Miller and David Belanger. URL associated with Seminar:  https://research.math.osu.edu/logicseminar/ 240 Stillman Hall Department of Mathematics math@osu.edu America/New_York public

Title:  Strategy complexities of some infinite games

Speaker:  Liling Ko (The Ohio State University)

Abstract:  We apply techniques in computability theory to compare strategies of infinite variants of games. Within a variant of Monty Hall, we showed that a disorderly door-opening strategy is independently strong from a weakly-adaptive door-opening strategy. This result separates two notions of stochasticities. Within the game of chip-firing, we show that there are computable game instances that are winnable, but that do not have a computable winning strategy. We also characterize the index set of computable chip-firing instances as $\Pi_3$-complete. These are joint works with Justin Miller and David Belanger.

URL associated with Seminar:  https://research.math.osu.edu/logicseminar/

Events Filters: