The solution that was a losing set

The two subjects called game theory parted company early, and the usual account of the split is that one studies payoffs and the other studies who moves last. Von Neumann and Morgenstern’s book of 1944 has players, coalitions and shares of a sum. The theory running from Bouton’s Nim through Sprague and Grundy has heaps and a rule for losing. The notes on negatives make the contrast sharply: a payoff is a number somebody is trying to make large, and a position is an element of a group, and nothing in the first world corresponds to the operation that defines the second.

That is true, and there is one place where it fails. Chapter six of the 1944 book defines what it calls a solution, and the definition does not mention numbers. It is two conditions on a set of outcomes and one relation between pairs of them. Write the relation as a move and the set becomes something every reader of this subject already knows. A solution of a game that must end is its set of lost positions, and nothing else. The first sentence of the theory of coalitions and the first sentence of the theory of Nim are the same sentence.

They stop being the same the moment play can go round in a circle, and the way they differ is the subject of the essays that follow. On a graph with cycles, the object the 1944 definition picks out may not be unique and may not exist, and the smallest game on which it fails has three positions.

Two conditions and no numbers #

The setting of the definition is an outcome and the question of whether it will hold. A division of a sum among players is under threat if some group of them could arrange a different division that each member of the group prefers, and has the power to enforce it. Von Neumann and Morgenstern call this domination. Division x dominates division y when a group able to act on its own gets strictly more from x than from y, every member of it.

Domination alone does not pick out a best division, because it goes in circles. If x dominates y and y dominates z, z can perfectly well dominate x, with a different group doing the dominating each time. So no division is safe on its own, and the book’s answer is the move for which it is remembered: a solution is not a division but a set of divisions, with two properties.

The first is that nothing in the set dominates anything else in the set. The second is that everything outside the set is dominated by something inside. The first says that the set does not undermine itself, the second that it has an answer to every proposal from outside it. A society with this set as its standard of behaviour has no internal reason to abandon any member of it, and can reject any alternative by pointing to one that is preferred. That is the whole of the definition, and it carries no reference to what the divisions are.

The simplest example is the one the book itself develops, with three players and majority rule. Any two of them can impose any division of the whole sum. The figure draws that game on a grid of six units, which turns the continuous triangle of divisions into 28 points, each a position on it, with the three corners being one player taking all. Take the three divisions that split the sum evenly between two players, with the third getting nothing. Moving from (3, 3, 0) to (3, 0, 3) helps player three and hurts player two, and leaves player one where they were, so no group of two gains: no member of the three dominates another. And any other division gives less than half to at least two players, so those two would both rather have the even split between them. The arrow marks that argument for one division, (1, 2, 3), which players one and two both abandon for (3, 3, 0). Checked on all 28 points, the three really are a solution.

Notice what the set is not. It does not predict which of the three will happen, or say that any of them is fair to the player left out. It describes an arrangement stable as a whole, and that wholeness is what will carry over.

Read the relation as a move #

Now take a game with no coalitions in it at all. Draw its positions as points, and draw an arrow from each position to every position a player can move to. Ask which positions lose for the player to move. The recursive answer, which is older than either subject and which Zermelo’s paper is usually credited with making explicit, has two clauses. A position is lost if every move from it leads to a won position. A position is won if some move from it leads to a lost one.

Put these in terms of the set L of lost positions. No move goes from one member of L to another, since a move from a lost position leads only to won ones. And every position outside L has a move into L, since that is what being won means. Those are the two conditions. Domination has become a move, read in one direction: y is overruled by x when y can move to x. Nothing else has changed. The set of lost positions is a solution in the sense of the 1944 book, applied to a relation that nobody at the time would have called a preference.

The heap game in the figure is the smallest thing that shows it clearly. The multiples of three are the positions where the player to move has lost, as every reader of the first essay on subtraction games knows. Read as a set in the graph, they are independent, because a move changes a heap by one or two and so never carries a multiple of three to another one; and they absorb, because every other heap is one or two above a multiple of three. It is a stable set, and a search of all subsets of the thirteen positions finds no other.

This is the term the rest of these essays will use. Stable set is the phrase game theorists settled on for the 1944 solution, once “solution” had come to mean too many things. Graph theorists call the same object a kernel, a name that comes through Claude Berge’s work on graphs in the 1950s, where the connection to games was stated outright. Both words describe a set with no arc inside it and an arc into it from everywhere outside, and the two literatures have mostly developed them separately. Which direction the arrow runs is a convention, and both directions are in use; here an arrow is a move, so the set is what a move must arrive at.

Nothing about the argument depends on the particular rule. Allow takes of two or three instead, and the heap with one counter has no move at all, so it is lost along with the empty heap.

The pattern of lost heaps now repeats every five, in pairs, where before it repeated every three, singly. A reader used to the periodic tables of subtraction games will read this as a statement about the rule. The definition of a stable set was not told anything about the rule. It looks at a graph and asks two questions, and the answer is whichever set survives them. That indifference is what lets it apply to a graph with no heaps in it, as it does to the triangle of divisions, and to graphs built from things stranger than either.

Why a game that must end has exactly one #

The heap game’s single stable set was not luck. On any graph where play must end, a stable set exists and there is exactly one, and the reason is that the two conditions, applied from the end of play upward, leave nothing to decide.

Start at the bottom. A position with no moves at all cannot be outside the set, because the second condition would demand a move into it and there is none. So it is in. Now anything with a move into a member is out, by the first condition. Then any position whose moves all lead to excluded positions has no way of satisfying the second condition from outside, so it must be in. Each round is forced by the last, and because every line of play ends, the rounds reach every position. Existence and uniqueness are one argument here. It is the same argument as the backward labelling that computes outcomes, since it is literally that algorithm with different words on the two labels.

The census agrees and is worth stating because of what comes next. Among the 302 different directed graphs on five positions that have no cycle, every single one has exactly one stable set, and that set is its lost positions. The same holds for all 31 at four positions and all 6 at three. A reader who only ever met finite games would have no reason to think of a stable set as a separate idea. It would be a rather elaborate way to say “lost”.

That is the historical oddity at the centre of this. The two conditions were written down in 1944 for the case where the relation goes round in circles, because domination among divisions does. There were 180 distinct triples of divisions in the 28-point grid above in which each dominates the next and the last dominates the first. A finite game is the case the definition was not written for and where it is trivially decided. The book’s authors needed a definition that survives cycles, and they got one. The game theorists who had Nim had no cycles, and so had no reason to ask.

The surprising part: a definition that survives cycles can also fail on them #

Everything about the definition is unchanged on a graph with cycles, and it is natural to expect the argument to carry over with minor repairs. It does not. Without a bottom to start from, the peeling has nowhere to begin and the question is open again. So the first thing to do is to look at the smallest cases completely.

There are sixteen games on three positions. The figure draws them all. Nine have exactly one stable set: all six with no cycle, and three that have a cycle and still leave only one way to choose. Six have several: the two positions that move to each other, for instance, offer two stable sets, one each, since either may be chosen and the other then has a move into it. The graph with three positions moving to each other in both directions has three, one per position. In the language of the first definition, these are societies with several consistent standards of behaviour, and the three-person majority game is one of them: it has the three even splits as one solution and, on the continuous triangle, infinitely many others in which one player’s share is fixed and the other two bargain.

And one has none. Take three positions in a cycle, each with a single move to the next. Suppose some set works. If it is empty, nothing is inside for an outsider to move to, so it fails. If it holds one position, the position that moves into that member is fine, but the third moves only to the one that moves into the member, which is outside the set, and so the third has no move in. If it holds two, they are adjacent on the cycle and one moves to the other. There is nothing else to try. That three-position loop has no solution.

What took twenty-four years on the other side #

This small graph puts a long-standing question from the other literature in an odd light. The stable set was the central solution concept of the 1944 book, and for a generation the outstanding question about it was whether every game has one. Von Neumann and Morgenstern evidently hoped so. Examples accumulated in which solutions were many and strange, and none in which they were absent. William Lucas settled it in 1968, with a game of ten players and a carefully constructed set of coalition values, published under the title A game with no solution.

The cycle of three does not contradict that history or make it look foolish, and it is important to be clear why. Lucas’s question was not whether some relation has no stable set. It was whether a relation arising as domination among divisions of a characteristic-function game can lack one, and that is a heavily constrained kind of relation: its arrows have to be those some coalition’s interests produce, which is why the construction took ten players and a long verification. A bare graph of positions has no such constraint. Any directed graph at all is the move graph of some game, because a game can simply be defined by its graph, so the smallest counterexample in this form is three positions and a single line of argument.

What the comparison shows is how much the choice of relation is doing. The definition is one sentence. On finite games it always has a unique answer, on divisions in a coalition game the existence question resisted for a quarter of a century, and on general graphs it fails on three positions. None of those facts is about the definition alone, which is why the object has been rediscovered under different names in fields that had little to say to each other.

Where the convention enters #

Two conventions are holding this together, and the result changes if either is moved.

The first is the rule for losing. The identification of a stable set with the lost positions uses normal play, where a player with no move has lost. Under misère play a position with no moves is a win for the player who reached it, and the lost positions satisfy a different pair of conditions, in which the terminal positions are forced out and not in. Those conditions are not those of a stable set of the move graph. Misère outcomes on a finite graph are still unique, since the backward labelling still runs, but what is unique is no longer a stable set of the same relation.

The second is what the arrow means. The 1944 relation runs from the dominating outcome to the dominated one, and a solution dominates everything outside it. The arrows here run from a position to where it can move, with the set on the receiving end, so this essay’s arrow is the reverse of the book’s. Reversing every arrow in a graph does change which sets are stable, so this is not a matter of taste. The translation between the two subjects has to be made in that direction, with x dominates y read as y may move to x, and it works only because a lost position is what a player wants to hand to the opponent. It is a slightly unexpected reading of the word “dominates”: the winner is the player who moves to the dominating outcome and leaves the opponent with nothing to say.

What the pictures cannot show #

Anything about play. The catalogue of sixteen says which graphs have stable sets. It does not say what a stable set is good for on a graph where it is not the set of lost positions, and on the graphs with several of them, nothing here distinguishes one from another. Those are the questions the next essays take up. On a graph with cycles the lost positions and the stable sets are genuinely different objects, and a draw is where they part.

The continuous game. The figure of the majority game is a grid of 28 points standing in for a continuous triangle of divisions. On the grid, the three even splits work, and that is checked. The infinite families of further solutions that the book finds on the continuous game do not transcribe cleanly, since “strictly more” behaves differently when shares come in whole units: one player’s fixed share leaves a line of divisions that are stable among themselves, but a neighbouring division may need to exceed a member by a whole unit on two coordinates at once, which the grid can make impossible. So the phrase “several solutions” for that game is the book’s result and is not measured here.

Whether the two literatures would call this one idea. The two conditions are identical and the translation is exact. But the 1944 definition was a claim about social arrangements and the rule of a heap game is nothing of the kind, and calling them the same does not make a coalition into a move. What is established is an identity of definitions. Nothing here supposes that either author had the other world in view when writing them, and this essay does not claim to know.

Still open: what stands in for the bottom of the graph #

A game that must end has one stable set because the end of play gives the argument somewhere to start. Take away the end and the cycle of three shows the conclusion can fail, while the cycle of two shows it can fail the other way, with too many. The natural next question is whether anything in the shape of a graph replaces the bottom: some property, weaker than having no cycles, which still guarantees that at least one stable set exists. Looking at the catalogue, the failure has an obvious suspect. The one graph with no stable set has a cycle of odd length, and the graphs with several have cycles of even length.

That suspicion turned out to be a theorem, and an early one. Moses Richardson proved in 1953 that a graph with no odd cycle always has a stable set, and his proof is a version of the same peeling with a parity argument replacing the bottom of the graph. It is a statement about the 1944 definition that uses nothing from the theory of coalitions and could have been written by someone who had only ever thought about Nim.