AAMAS-2019 Tutorial

Bridges with Combinatorial Game Theory (half-day)

pic

PRESENTERS


ABSTRACT

This is a half-day tutorial. There will be three talks divided in three main topics of CGT.

1) The disjunctive sum theory of CGT, and the order of combinatorial games Guaranteed Scoring play exploits the power and beauty of standard CGT normal play theory, and it transforms our thinking about scoring (0-sum) disjunctive sum play. Presenter Carlos P. dos Santos.
2) Combinatorial games and bargaining This talk will present novel approaches of CGT where the players bid on who is to play, and how these approaches can bridge CGT with classic multiagent systems and game-theoretic problems. Presenter Reshef Meir.
3) Sequences and games generalizing the combinatorial game of Wythoff Nim We survey how various subjects, such as Combinatorics (Algebra on words), Number Theory (Beatty sequences, the Golden section, Numeration systems), Computer science (Complexity, Cellular Automata), Physics (Renormalization), Biology (Phyllotaxis) and Mechanism Design enter the theory of Combinatorial Games. Presenter Urban Larsson.

Detailed descriptions:

1) The disjunctive sum theory of CGT, and the order of combinatorial games The family of combinatorial games consists of games with perfect information (no hidden information as in some card games), no chance moves (no dice), and where the players move alternately. Combinatorial Game Theory (CGT) primarily considers rulesets in which the positions decompose into independent subpositions as case studies. This class of rulesets has been called additive to distinguish it from maker-maker and maker-breaker positional rulesets.

In rulesets played with normal-play convention, last player wins. The theory of normal-play was developed first. The analysis of NIM, by Charles Bouton, was published in the early twentieth century. After this, the Sprague–Grundy theory for impartial combinatorial games (in all subpositions, the players are restricted to the same set of moves), appeared. This was a fundamental step for the subsequent establishment of combinatorial game theory; the important concept of disjunctive sum of games was established, and this idea was already present in the game of NIM, where, of course, the most central concept is that of «nim-sum».

The next big step was in the 1950s, by Milnor, when the notion of game comparison first appeared in so-called «positional games», and this theory was inspired by the famous eastern game of GO.

Later, in the 1970s, Conway was able to expand the theory to include partizan game theory (not necessarily impartial games) followed up in the 1980s with Conway, Berlekamp and Guy’s Winning Ways. Combinatorial games played with normal-play convention, together with the disjunctive sum, are an ordered, abelian group. To check if G>=H, it is only necessary to see if Left wins G-H playing second. There are two fundamental reductions: domination and reversibility, and there is a unique simplest game equivalent to G. That game is obtained by making all the possible reductions in G and its followers. There is a bijection between the outcome classes and the order. These are very good properties of normal-play.

Other conventions as misère-play (last player loses), scoring‑play (the player with the largest number of points at the end wins), cyclic-play (games with cycles and loops), etc., are much harder. We only have monoids, comparisons are more complex, reductions are more subtle.

Guaranteed Scoring Games have the property that the players want the games to continue; that is, it is always better for a player to continue the game than to run out of options. The class of Guaranteed Scoring Games is interesting because, although it is only a monoid, it still allows mathematically treatable reductions and comparisons. In addition, it allows establishing bridges of understanding with the analysis of other classes like dicotic misère-play or dead-end misère-play.

Nowadays, many different CGT partial orders are being studied. The goals of these talks are to present and discuss some details of this mathematical development.

2) Combinatorial games and bargaining Bidding games are extensive form games, where in each turn players bid in order to determine who will play next. Each player starts with a fixed budget, and the winner of every round's bid makes a move and pays the loser so that the total budget remains constant. Zero-sum bidding games like Bidding Tic-Tac-Toe have been extensively studied [Lazarus et al.'99, Develin and Payne '10], and are known as Richman games.

This part of the tutorial will present both traditional Richman games and their extension to general-sum bidding games due to Meir, Kalai and Tennenholtz [EC'15, GEB'18]. Bidding games over binary trees have a natural interpretation as bargaining over a set of items among two agents, and thus provide a first bridge between combinatorial games and standard multiplayer games from the economic literature. In particular it can be shown that any such game has a natural subgame perfect equilibrium that corresponds to a Pareto efficient and fair allocation of items. Moreover, the natural equilibrium can be computed efficiently due to its unique properties.

Relaxing the zero-sum requirement is a promising direction in the development of combinatorial game theory, and some related questions will be presented.

3) Sequences and games generalizing the combinatorial game of Wythoff Nim The game of Wythoff Nim is usually played with a single Queen of Chess on a large Chess board. Two players alternate to move the Queen towards the lower left corner, using its standard moves from Chess, and the player who cannot move loses. This is a classical impartial game in combinatorial game theory, and it became popular because the winning strategy has an appealing explicit formula description which involves the Golden Section.

A multitude of variations and generalizations of this game are known today, with branches in diverse fields such as Combinatorics (Algebra on words), Number Theory (Beatty sequences, the Golden section, Numeration Systems), computer science (Algorithms, Cellular Automata), Physics (Renormalization) and Biology (Phyllotaxis) and more. The purpose of this talk is to survey some of the current literature in this field. The presenter has published more than 10 papers on extensions and restrictions of this game, with more than 10 coauthors. One of these papers revolves around the idea that when we forbid the winning moves, in the game of 2-heap Nim, then the new winning strategy is the same as that of Wythoff Nim. These type of problems are related to Mechanism Design in Algorithmic Game Theory and we believe that some bridges can be built with Autonomous Agent and Multiagent Systems. A new field of reverse engineering combinatorial games is emerging, where some candidate solution is given and the quest is to find appealing rules that match the given solution.

PRESENTERS' SHORT BIOS

Carlos Pereira dos Santos is a researcher of the Center for Functional Analysis Linear Structures and Applications, University of Lisbon and Lecturer at the High Institute of Engineering of Lisbon. Before that he was Lecturer 2005-2014 at the Institute of Education and Sciences. His main interests are Combinatorial Game Theory, Recreational Mathematics, and Mathematics Education. He organizes the Combinatorial Game Theory Colloquia (third edition in January 2019). He publishes regularly in CGT and neighboring fields (7 papers in 2017-2018). He also enjoys cultural and sociological issues related to games, being a fervent follower of good popularization of mathematics. He is in the Editorial Board of the Board Game Studies Journal, and he is the Editor of the Recreational Mathematics Magazine. He is a Teacher Trainer and Researcher in Colégio de São Tomás. Mananger of the Centre for Teacher Training of the Portuguese Mathematical Society (2005-2009). Certication of school books for Portuguese Mathematical Society. Author of a set of primary math books. 
 Carlos P. dos Santos
  Center for Functional Analysis, Linear Structures and Applications, University of Lisbon
  High Institute of Engineering of Lisbon 
  1600-677 Lisbon, Portugal
  URL: https://sites.google.com/site/cpshomepage
  email: cmfsantos@fc.ul.pt
Reshef Meir is a Senior Lecturer (Asst. Prof.) at the Industrial Engineering and Management dept. at the Technion. Before that he was a postdoctoral research fellow at the Center for Research on Computation and Society (CRCS) at Harvard University (USA). He has completed his BSc, MSc and PhD at the School of Computer Science and Engineering of The Hebrew University in Jerusalem, Israel, and was an intern in Microsoft research during 2010-2013. His main research areas are Algorithmic Game Theory and Mechanism Design. In particular, he studies mechanisms that promote cooperation, stability, and social welfare. Reshef is a recipient of the Rothschild fellowship for post-doctoral studies (2013-2014), and of the 2013 Maschler prize for an outstanding research student in game theory (together with Omer Tamuz), and was named as one of \emph{AI's 10 to Watch} by IEEE Intelligent Systems (2015). He served as a program committee member at a number of international conferences, and was a co-chair of a workshop on cooperative games at AAMAS'14,AAMAS'15, and AAMAS'16, as well as of the three installations of AGT@IJCAI (2015-2017) and was at the steering committee of AI3 at AAMAS’18. 
Reshef Meir
 The Faculty of Industrial Engineering and Management
 Technion–Israel Institute of Technology
 Haifa 3200003 Israel
 URL: http://reshef.net.technion.ac.il
 email: reshefm@ie.technion.ac.il
Urban Larsson is a postdoctoral fellow at the Industrial Engineering and Management dept. at the Technion (and awarded an Aly Kaufman fellowship), and moving to NUS, host Yair Zick dept. Computer Science. 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, Computer Science and Algorithms, and some of his main contributions find bridges between Combinatorial games and neighboring fields. He publishes regularly (with 13 peer reviewed published papers in international journals in 2017-2018). Urban, has presented his research at about 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 5 (in press), and the next issue Games of No Chance 6 (still collecting submissions). He has co-organised three workshops in Combinatorial Game Theory--Twice “Games at Dal” (Dalhousie University), with Nowakowski, and once “Games at Carmel”--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). 
Urban Larsson 
  The Faculty of Industrial Engineering and Management
  Technion–Israel Institute of Technology
  Haifa 3200003 Israel
  URL:  www.urbanlarsson.mine.nu
  email: urban031@gmail.com

TUTORIAL NOTES

Slides: