Nobody has to move

Everything on this site rests on a sentence that is never examined: the players move alternately. Every value, every outcome class, every theorem about sums assumes it, and nothing anywhere argues for it.

Richman’s variation replaces it with an auction. The two players hold a fixed total of money between them. Before each move they bid; the higher bid wins the right to move and pays the bid to the other player. A player who wins an auction and has no move has lost, which is the normal-play convention with whose turn it is replaced by who is willing to pay.

The remarkable fact is that a position stops having an outcome class and starts having a number.

The recursion #

There is a critical fraction $R(G)$ such that Right wins with more than that share of the money and Left wins with less, and it is computed by a recursion as short as the one for values:

$$R(G) = \tfrac12 \Bigl( \max_{G^L} R \; + \; \min_{G^R} R \Bigr)$$

with a player who has no option scoring the loss: $0$ if it is Left who is stuck, $1$ if it is Right.

The reading is direct. If Left wins the auction, Left moves to whichever option leaves Right needing the most; if Right wins it, to whichever leaves Right needing the least. Nobody knows in advance which of the two will happen, so the position is worth the average — and the $\tfrac12$ is the auction.

Everything infinitesimal comes out at a half #

Eight of the 22 day-two values have $R = \tfrac12$. Seven of them are $0$, $\ast$, $\uparrow$, $\downarrow$, $\uparrow\!\ast$, $\downarrow\!\ast$ and $\ast 2$ — everything infinitesimal born by day two, together with zero.

The eighth is $\{1 \mid -1\}$, which is not infinitesimal at all: it is the hottest thing born by day two, with a whole unit at stake. It lands on a half for a different and equally clean reason. It is its own negative — negating swaps the two options and negates them, and $\{1 \mid -1\}$ comes back unchanged — and a position symmetric between the two players cannot possibly need a majority of the money for either of them.

So the class at a half is two classes: things too small to matter, and things exactly balanced. Under alternating play those seven infinitesimals are all different — $\uparrow$ is a Left win, $\downarrow$ a Right win, $\ast$ a first-player win and $0$ a second-player win, four different answers from one class.

Under the auction they are one thing. A half means the position itself decides nothing and whoever has more money wins.

That is the sharpest statement of what the two conventions measure. Alternating play cares who runs out of moves, so a position worth an amount smaller than every number can still be the whole game — small things decide when nothing else is happening. The auction cares who can afford to move, and an advantage smaller than every number is worth nothing at all when a move can simply be bought.

The two ways of arriving at a half are not the same situation, and the recursion says so in a quantity the critical fraction hides. Run it on a star.

Now the other half, the one that is not infinitesimal.

So the class at a half is two classes and the bid separates them. A star is a position nobody will pay for; $\{1 \mid -1\}$ is a position worth a quarter of everything on the table to move in, and the two are the same number because the critical fraction records who is ahead and not how much is at stake. That is the auction’s own version of a distinction the alternating theory draws with temperature, and it arrives from a completely different direction.

The hot positions do separate #

Away from the infinitesimals the auction is discriminating and it is discriminating in the direction one would hope.

An integer $n$ has $R(n) = 1 - 2^{-(n+1)}$: a Left lead of one needs three quarters of the money to overcome, a lead of two needs seven eighths, a lead of three fifteen sixteenths. Each extra free move for Left halves the money Right can afford to be short by, and the recursion shows why in one line.

That is the striking part of the arithmetic and it is worth pausing on, because it says the auction is much more forgiving than alternating play. Under alternating play a Left lead of three is hopeless for Right whatever else is true; under bidding, one sixteenth of the money is enough. Money buys consecutive moves and consecutive moves are exactly what a lead of three is.

The bid falls with the lead as fast as the value rises: a sixteenth here against a quarter at $\{1 \mid -1\}$. A position nearly decided is a position hardly worth bidding on, which is the auction saying in its own currency what a cold position is.

The fractions $\tfrac38$, $\tfrac58$, $\tfrac9{16}$ and $\tfrac7{16}$ that fill the rest of the table are the same phenomenon at finer grain: the auction reads a position’s advantage as a share of the money, and reads small advantages as small shares.

What survives, and what does not #

Two structural questions, asked of the same pool.

The order survives, exactly. If $G \ge H$ — Left is at least as well off in $G$ — then $R(G) \ge R(H)$: Right needs at least as much money to beat it. Over the 179 ordered comparable pairs among the 22 values, this holds 179 times.

That is not obvious and it is a genuine compatibility. The game order is defined by playing a difference out under alternating play, and there is no reason in the definition of $R$ for it to respect a relation defined by a different convention. It does.

Addition does not survive at all. $R(G + H)$ is not a function of $R(G)$ and $R(H)$.

Two positions both with $R = \tfrac58$, added to two others both with $R = \tfrac58$, can give sums worth $\tfrac{23}{32}$, $\tfrac34$ or $\tfrac{25}{32}$. There is no arithmetic on Richman values, and the failure is not marginal — it is a third of the input pairs.

So the auction hands every position a number and takes away the one thing this site is built to do with numbers.

Why the fractions are dyadic #

Every Richman value in the sweep has a denominator that is a power of two, and the reason is in the recursion: each step averages two numbers, which halves a denominator’s precision at most once, and the base cases are $0$ and $1$.

So $R$ of a position of depth $d$ has denominator at most $2^d$, which makes the value a dyadic rational — the same class of numbers the game values themselves live in, arrived at by a completely different route.

That is a coincidence of the two-player auction rather than a deep fact. An auction with a different tie-break, or three players, or a bidding rule where the winner pays to a bank rather than to the opponent, produces different arithmetic; the Richman rule’s specific “pay the winner’s bid to the loser” is what makes each step an exact average.

What the number is not #

It is not a value. Two positions with equal Richman values are not interchangeable in company, because there is no meaningful notion of company: sums have no theory here.

It is not a probability, except that it is. There is a second reading of $R(G)$ that is the reason the theory is well known. Play the same game with a coin flip deciding who moves at each turn rather than an auction, and the probability that Left wins under optimal play is exactly $R(G)$. The two settings — money and chance — give the same recursion, because averaging the two branches is what a fair coin does and what a fair auction does. Which player the probability belongs to is worth checking rather than assuming: $R(1) = \tfrac34$, and a position where Left has a free move and Right has none is one Left wins three times in four under the coin, not one in four.

That is Peres, Schramm, Sheffield and Wilson’s observation, and it is what makes bidding games a bridge to random-turn games. The site’s own alternation is the difficulty argues that alternation is what makes a game hard where a puzzle is easy; random-turn play removes the alternation and makes a class of games that are hard under alternation completely analysable.

It is not a value in this site’s sense, and the position index records it as a computed quantity with an outcome beside it rather than as a game value, because there is no game whose value it is.

It is not a strategy. Knowing $R$ says who wins from a given split of the money and says nothing about what to bid beyond the one number, and it says nothing about which move to make once the auction is won — that comes from the recursion’s $\max$ and $\min$, which have to be recomputed.

What the convention cannot reach #

Ties. At exactly $R(G)$ the rule needs a tie-break — the same knife-edge problem a draw poses in the loopy theory, arrived at from a different direction, and the theory has several — the standard one gives a tiny extra chip to one player to break exact ties. Everything in this essay stays away from the knife edge by counting the positions at exactly $\tfrac12$ separately rather than assigning them to a player.

Sums. Already said, and worth saying twice: the whole of this site’s method is unavailable.

The pool. Twenty-two values born by day two is a small pool for a structural claim. A sample of 400 values born by day three gives 15 distinct Richman values and 79 at exactly a half, so the collapse continues at scale and the counts are not proportional to anything.

The values, not the games. Everything swept is a value from the construction rather than a position from a ruleset, and the two lists barely meet. What a real game’s positions look like under the auction is a different sweep, and the day-three sweep is a sample rather than the whole. Nothing here is a theorem; the order result is checked and the additivity failure is exhibited.

The two conventions never contradict each other #

One more count, and it is the reassuring one.

Cross-tabulating the outcome class under alternating play against the winner under bidding at an even split, there is no case in which one convention says Left and the other says Right. Left wins under bidding exactly where alternating play says Left wins either way; Right likewise; and the first-player and second-player classes map onto “the money decides”.

So the auction is not a different opinion about who is better off. It is a coarser instrument: it agrees wherever alternating play is decisive regardless of who moves, and declines to answer wherever alternating play’s answer depends on the turn.

A worked auction, with the money on the table #

The number is easier to believe once one line of play is written out.

Take the position $1$: Left has one free move and Right has none. $R(1) = \tfrac34$, so Right needs more than three quarters of the money.

Suppose the pot is four units and Right holds three of them — exactly the threshold, so the position is on the knife edge, and suppose the tie goes to Left. Right must win the auction, because if Left wins it Left moves to $0$ and then whoever wins the next auction must move and cannot, and Left has just been paid. So Right bids. Right cannot bid more than three; Left, holding one, need only bid enough to make winning expensive.

Now suppose Right holds three and a half of four. Right bids one and a quarter, wins, and has no move: Right loses on the spot. So Right does not bid. Left wins the auction cheaply, moves to $0$, and now holds one and a quarter against Right’s two and three quarters — and at $0$ the player who wins the auction loses, so both want to lose it, and the player with less money loses the auction by bidding nothing. Left, with less, is stuck with the move and has none.

The knife edge is genuinely a knife edge, which is why every count in this essay treats the positions at exactly $R$ as a separate column rather than assigning them.

Who found it, and when #

The convention is David Richman’s, from the late 1980s, and he did not publish it: the theory appeared after his death in two papers by Lazarus, Loeb, Propp and Ullman in the 1990s, which established the recursion, the critical ratio and the connection to random turns.

The random-turn reading was pushed much further by Peres, Schramm, Sheffield and Wilson in the 2000s, where the payoff is a family of results about random-turn versions of hard games — random-turn Hex being the famous one, where the win probability is computable and the alternating game is not.

There is a moral in that pairing which this site’s complexity essays keep arriving at from the other side. Alternation is not decoration. Removing it does not make a game a slightly different game; it makes the analysis a different subject, with a different answer, computed a different way — and, for several games, a much easier one.

What changes when a player can decline #

Removing the obligation to move changes more than a rule, and it is worth listing what goes with it, because nearly every theorem on this site depends on the clause being there.

The recursion loses its base case. Normal play ends because a player runs out of moves, and the whole theory is grounded on the position with no options is a loss for the mover. If a player may decline, running out of moves is not the end of anything, and the recursion needs a different reason to terminate.

Length starts to matter. A component’s spare moves are worthless under normal play because a player always has somewhere better to go — the disjunctive sum guarantees it. Take away the obligation and spare moves become a resource a player can hold, so the quantity the value discards is back in the game.

And the outcome stops being about who moves last. With declining allowed, a game can end with both players declining, and what settles it then is a rule from outside the recursion — a score, a repetition count, a convention — which puts the position in a different theory entirely.

So the obligation is not a technicality of the ending convention; it is what makes a value a value. It is why every move is a resource spent, why a number is a standoff rather than a quantity, and why the last player to move wins is a rule with arithmetic behind it rather than a scoring choice.

Which is the right frame for the games that do let a player decline. They are not normal-play games with an extra option; they are a different subject, and the interesting question about each is which of the three losses above it can buy back.

What a number instead of a class costs #

It is worth being explicit about the trade, because “every position gets a number” sounds like an improvement and is not one.

Under alternating play a position has an outcome class, which is one of four, and a value, which is an element of a partially ordered group. The class is coarse and the value is fine, and the value’s whole justification is that it composes: a board falls into parts, the parts are added, and the answer to the whole comes out of the arithmetic.

Under bidding a position has one real number. It is finer than an outcome class — seven distinct numbers where alternating play has four classes, over the day-two pool — and it composes not at all.

So the exchange is a finer summary of a single position for the complete loss of the ability to combine positions. Which is the better bargain depends entirely on whether the game in front of the reader falls apart, and most of the board games here do.

There is a second cost and it is subtler. A Richman value depends on the money, which is a resource external to the board, so two players sitting down to a position do not know who is winning until the stakes are set. Under alternating play the position is the whole of the information. Under bidding it is half of it.

Where the ladder goes next #

The first rung out is the discrete version. Real bidding games are played with a finite number of chips rather than a continuum of money, and the critical ratio becomes a threshold on an integer — which is where the tie-break stops being a technicality and starts deciding real positions.

The second is the structure the auction does have. The order survives, so the Richman values are a monotone map from a partially ordered group to the unit interval, and asking which such maps arise this way is a question with a shape.

And the third is the direction that connects back to everything else here: three players and no answer found that with three players the winner is a fact about the convention rather than about the position. Bidding is the same discovery on a different axis — change the turn order rather than the number of players and the answer changes, in a way that is completely determined and completely different.