Can players who only look at their own past results end up playing the equilibrium?
Topics 11 to 15 asked who gains when several players choose. These nine go further: what changes when the moves come in turns (25), when players hold secrets (26), when they meet again (27), when they learn as they go (28), when a shared signal is allowed (29), when each chooses a route (30), when the question is how hard an equilibrium is to find (31), the one place where quantum physics changes a game's value (32), and then a market you design and attack yourself (33).
Topic 12 solved zero-sum games by linear programming: a calculation done once, by someone who knows the whole payoff table. Real players do not have that. They play, see how it went, and adjust. The question is what such adjusters end up doing.
The simplest adjusting rule is regret matching (Hart and Mas-Colell, 2000; the version used on this page compares each move with the best fixed move). After each round, for each of your moves, add up how much better you would have done had you played it instead. Then play each move in proportion to its accumulated positive regret. A close relative, multiplicative weights, plays each move with a weight that grows exponentially in how well it has done (Arora, Hazan and Kale, 2012).
Neither player needs to know the other's payoffs or rule, only how each of its own moves would have done. Yet in a zero-sum game, if both keep adjusting, the time average of each player's play converges to an optimal mixed strategy. The current play does not settle at all: it keeps lurching, as the figure shows. It is the long-run average, not any single round, that is unexploitable.
The game on the figure is a biased rock-paper-scissors: rock beats scissors for 2, paper beats rock for 1 and scissors beats paper for 1. Its equilibrium is not the familiar one third each. It is (1/4, 1/2, 1/4): paper twice as often as rock or scissors, the mix that leaves a best-responding opponent indifferent among its three moves.
Row's payoff table, with column's payoff the negative of it (rows and columns in the order rock, paper, scissors):
A = [ 0 -1 2] [ 1 0 -1] [-2 1 0]
The equilibrium by hand. A mix p is unexploitable when every column pays the row player at least zero, the value of this symmetric game. Setting pA = 0 gives pP = 2pS and pR = pS, so p = (1/4, 1/2, 1/4). A linear program (topic 03) gives the same answer, with value 0.
Regret. After T rounds a player's external regret is the best total they could have earned by always playing one fixed move, minus what they earned. Regret matching guarantees the average regret falls like 1/√T. If both players have average regret at most ε, the average strategies form a 2ε-equilibrium of the zero-sum game: neither player can gain more than 2ε by switching. Nobody had to be told the game.
Measured here. The table shows the row player's running average after T rounds, how much a best-responding column player could win against it (zero is unexploitable) and the average regret:
| Rounds | Average mix (rock, paper, scissors) | Exploitability | Average regret |
|---|---|---|---|
| 100 | (0.337, 0.470, 0.193) | 0.144 | 0.115 |
| 1,000 | (0.257, 0.484, 0.258) | 0.032 | 0.038 |
| 5,000 | (0.260, 0.501, 0.238) | 0.022 | 0.016 |
Multiplying the exploitability by √T gives 1.44, 1.01, 1.56 at T = 100, 1,000 and 5,000: it does not grow, which is what a 1/√T rate looks like. The current mix is another matter: over rounds 4,001 to 5,000 its exploitability swung between 0.17 and 2.00.
Where the theory stops. This is convergence of the average in a zero-sum game. In general games, learners that compare each move with the best fixed move are only known to approach the set of coarse correlated equilibria, which contains every correlated equilibrium (topic 29) and so every Nash equilibrium; a variant that asks "what if I had played b whenever I played a?" (the one in Hart and Mas-Colell's 2000 paper) reaches the correlated equilibria themselves.
Choose regret matching or multiplicative weights and slide the number of rounds. The dark line is the current mix over the last 400 rounds; the teal line is the running average. The readout gives how far the average is from unexploitable.
Poker Programs that play heads-up poker at or beyond professional level are built on counterfactual regret minimisation, a regret-matching method applied at every decision point of the game tree: Cepheus essentially solved heads-up limit hold'em (Bowling et al., Science 347, 145 (2015)), and Libratus beat four leading professionals at heads-up no-limit (Brown and Sandholm, Science 359, 418 (2018)). They solve a very large zero-sum game by letting a program play itself until its average strategy is hard to exploit.
Boosting and online learning Multiplicative weights is an old idea that keeps being rediscovered: it is the update behind AdaBoost, behind the Hedge algorithm for expert advice, and behind fast approximate solvers for linear programs. Arora, Hazan and Kale's survey (Theory of Computing 8, 121 (2012)) collects these.
The source for regret matching Hart and Mas-Colell, Econometrica 68, 1127 (2000), doi:10.1111/1468-0262.00153.
No quantum link is claimed for this topic.
Check yourself
Two players each use regret matching in a zero-sum game. What settles down to an equilibrium?
In a zero-sum game the running average of each player's play converges to an optimal mixed strategy, with exploitability falling like 1/√T. The play in individual rounds keeps lurching between near-pure moves, as the figure shows.