AAMAS-2019 Tutorial

- Urban Larsson National University of Singapore)
- Reshef Meir (Technion-Israel Institute of Technology)
- Carlos P. dos Santos (University of Lisbon)

**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.

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.

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 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 The Faculty of Industrial Engineering and Management Technion–Israel Institute of Technology Haifa 3200003 Israel URL: www.urbanlarsson.mine.nu email: urban031@gmail.com

- Lecture 1: CGT: disjunctive sum and partial order Lecture 2: Bidding games Lecture 3: Sequences and games generalizing the combinatorial game of Wythoff Nim