Title of the talk: Absolute Combinatorial Game Theory
Speaker: Dr. Urban Larsson, Research Fellow at National University of Singapore.
Day, Date and Time: Thursday, April 29, 2021, 10 am to 11 am.
Abstract:
We propose a unifying additive theory for 2-player alternating play 0-sum terminating Combinatorial Games (CGT), including the normal-, misere- and scoring-play conventions, studied by Berlekamp, Conway, Dorbec, Ettinger, Guy, Larsson, Neto, Nowakowski, Milley, Renault, Santos, Siegel, Sopena, Stewart (1976-2019), and others. Recall that normal-play is the last-move-win convention, and so on. Each game convention defines an additive partially ordered monoid, by the rule G >= H if o(G+X) >= o(H+X), for all X under this convention, but only normal-play has a group structure, such that G >= H iff G - H >= 0. Here o(.) is the partially ordered optimal play outcome function, defined on the game positions, under a given convention, and with either player as a starting player. And the disjunctive sum '+' means that the current player plays in exactly one of the game components. We show that some of the structure induced by normal-play, generalizes to a much larger context. A game universe is a set of games that satisfies some standard closure properties. Sometimes, the fundamental game comparison problem, "Is G >= H?'', simplifies to a constructive (recursive/'local') solution, which generalizes Conway's foundational result in ONAG (1976) for normal-play games that player Left wins G + (-H) playing second if and only if G >= H. (The players are Left and Right, and Left is the 'maximizer'.) This happens in a broad and general fashion whenever a given game universe is absolute. An absolute universe of games satisfies an additional closure property, dubbed parentality: any pair of non-empty finite sets of games is admissible as options. This property implies that a universe is saturated with respect to the outcomes, basically, given a game, any outcome is attainable in a disjunctive sum. Game comparison is at the core of combinatorial game theory, and for example efficiency of potential reduction theorems rely on a local comparison. We distinguish between three levels of game comparison; superordinate (global), basic (semi-constructive) and subordinate (local) comparison. Moreover, in proofs, a sometimes tedious challenge faces a researcher in CGT; in order to disprove an inequality, one would attempt to find an explicit distinguishing game. Here, we explain how this job becomes obsolete whenever a universe is absolute. Namely, it suffices to see if a pair of games satisfies a certain Proviso (specific for each universe) together with a Common Normal Part (essentially same for all). This is joint work with Carlos P. Santos and Richard J. Nowakowski.
About the Speaker:
Urban Larsson is a Research Fellow at National University of Singapore, host Reza Shokri, and before Yair Zick, and before that he was a postdoctoral fellow at the Industrial Engineering and Management dept. at the Technion, Israel, and awarded an Aly Kaufman fellowship. Before that he was awarded a Killam postdoctoral fellowship at Dalhousie University, Canada, 2014-2016, which included lecturing, and before that he was a responsible lecturer in mathematics 2013-2014 and Ph.D. student (ending 2013) at Chalmers & University of Goteborg, Sweden. His main research areas are Game Theory, Number Theory, Discrete Mathematics, Computer Science and Algorithms, and some of his main contributions find bridges between Combinatorial Games and neighboring fields. He publishes regularly, with more than 30 research papers in high quality peer reviewed journals, and a total production of more than 50 papers. Urban has presented his research at more than 100 international conferences and seminars, he is an Associate Editor for International Journal of Game Theory, and he is the Editor of Games of No Chance; currently the only research forum that specializes in Combinatorial Game Theory. He has organized several workshops in Combinatorial Game Theory; "Games at Dal" (Dalhousie University, with R. J. Nowakowski), "Games at Carmel" (Technion), "Games at Ohio" (Columbus University, with E. B. R. Roa) and "Games at Mumbai" (IIT Bombay, hosts R. K. Rai and M. Rao)--and he was/is member of the program committee for CGTC I, II and III, the third was held in Lisbon January 2019, organized by C. P. dos Santos (University of Lisbon).
Meeting details:
Join Meeting
Meeting number: 184 868 2813
Password: g5C3M2MrWPs