
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 IndoEuropean 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 funoriented than "agon" (and more decadenceoriented
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 preelectronic 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
TICTACTOE were shown to have interesting
numbertheoretic 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.

