Games Mathematicians Play

This site has several pages of material on the foundations of combinatorial game theory, and the connections to mathematical logic. It is part of my program to try to understand games. On this page, I outline a few basic facts, and give a few basic links. In the next page, I present an outline of the problem of what it means (mathematically) to be able to win a game, no matter what your opponent does: usually (but not always) this means having a "winning strategy". From that page I go into applications of combinatorial games to logic, primarily to "finite model theory", which is the study of finite structures like finite groups, finite graphs, etc.

Linguistic and Historical Introduction

The word "game" appears to be very ancient. It is a descendent of the Old High Gothic word "gomen", which means fellowship, and is thus related to gamble, gambol, and hence to gambit. It looks sort of like the Greek word "agon" (the ancestor of "agony": the Greeks took competition VERY seriously), and rather like the Sanskrit word "gam", which seems to refer more to large assemblies of people, animals, gods, etc., and hence to ... counting. My guess is that "game" is an Indo-European word. This raises the question of where the Arabic word "layba" came from: perhaps it is African (the Ethiopians, i.e., the Abyssinians, were in invasion mode way back when).

Language can tell us something about how people look at notions. The Romans were more decadent than the Greeks, and the Latin word "ludus" is more fun-oriented than "agon" (and more decadence-oriented than "gomen"). I have no idea where the Romans got "ludus", but it does live on, e.g., on the `play on words', i.e., "joke". Speaking of "play", the Greeks did not think much of it (from "paidos", or child, we get "paizo", or play, apparently not anything so serious as games). The Romans used the word "ludere"??, and the Arabs "yalayb": perhaps they knew something we don't.

It is not clear when mathematicians got interested in games. They probably always were, but there was a problem. Mathematics is serious and it is improper to approach such matters with an inappropriate levity. Fortunately, greed will find a way.

The classical tale of the origin of probability is that the Chevalier de Mere, a jaded roue, wanted to know how to adjucate a game. He went to M. Mersenne, who maintained a sort of pre-electronic newsgroup, and he passed the problem on to two amateurs, a customs official (Fermat) and a theologian (Pascal). For a no doubt accurate account of this tale, click here. Anyway, since then, dice, cards, and other such devices have found their way into studying a subject whose real objects of study were physics and finance.

(Here is an unpleasant truth behind this tale of innocent sin. During the High Middle Ages, when Europeans started getting filthy rich again, they discovered The Love of Money (see I Timothy 6:10). During the Renaissance --- the Late High Middle Ages --- Europeans went out on sea voyages to trade in nutmeg, gold, pepper, porcelain, sugar, human flesh, and so on. The profit margins were up to 1000 %, but the there were risks, like storms and pirates.

(This led to two inventions. One was insurance, which is an obvious application of probability. The other was an updated version of International Law, that said that when a privateer from one country pirated the cargo of a ship of another country, the lawyers should battle the matter out in a neutral prize court. Those cynical lawyers were soon interested in things like the odds of winning. The connection between probability and law still stands: S. D. Poisson wrote a book on the probabilities of correct decisions in criminal cases: it is a commentary on our state of denial that after two centuries, this book by a major mathematician has yet to be translated into English.

(The other invention was insurance, which needs no cynical introduction here.)

The financial people soon got interested in games as metaphors. There was some research into "economic game theory" in the two centuries before the book by John von Neumann and Oskar Morgenstern. Before then, Charles Sanders Peirce (the grandfather of Pragmatism, a popular, and controversial array of philosophical systems) proposed that a statement could be viewed the object of a game: there would be one player defending the statement, and another attacking it. Peirce was interested in this kind of game as being based on a wager: how much were the two players willing to bet on their respective positions?

Meanwhile, in the early 20th century, the forces of Levity started forcing their way into the Citadel of Seriousness. Games, like NIM and TIC-TAC-TOE were shown to have interesting number-theoretic properties, and thus worthy of study, even at taxpayer's expense! Like the grass that grows through the cracks, these games could not be denied, especially not after John Conway generalized NIM to get the game Hackenbush, which he and Elwyn Berlekamp and Richard Guy described, along with many other games, in their book WINNING WAYS. Conway also worked out an algebra of games, and used it to generalize Richard Dedekind's construction of the real numbers, getting what Donald Knuth called the surreal numbers (Knuth wrote a little book on them).

Games in Logic

Games in logic are probably ancient: people have been making wagers, and worrying about how wagers work, for a long time. The formal story begins with America's first eminent homegrown mathematician, Charles Sanders Peirce, the grandfather of pragmatism who called his own philosophy "pragmaticism" in order to distinguish it from the more psychological "pragmatism" of William James. Peirce got interested in what it meant by asserting that something is true rather than just having it be true. In the former case, there should be an Asserter who should be able to defend her case against a Denier. The resulting argument could take the form of a game: for example, if the Asserter claims that EITHER A OR B is true, then she should be free to choose A or B and then defend just that one statement; but if she claims that BOTH A AND B are true, then the Denier should be allowed to choose which statement to challenge. It is clear how games might be played on boolean combinations.

But it wasn't until the postwar era that games really took off in logic. True, Ernest Zermelo proved his theorem at the turn of the century, but it wasn't until after WW2 that efforts began in earnest (but see the paper by Schwalbe and Walker listed here). There were two currents that we are interested in here: the work in set theory inspired by Gale and Stewart's generalization of Zermelo's theorem, which we discuss a bit in succeeding pages, beginning here. The other current was representation of quantifiers by games, an approach to the analysis of natural languages pioneered and popularized by Jaakko Hintikka. We will not go into linguistics here, but this will be the primary thrust of these pages, beginning here.