The Only Winning Move
Game Theory is a cautionary tale about decision making under uncertainty.
We end the semester on games because they comprise the ideal application of decision making under uncertainty. As Samuel smartly noted 60 years ago, games are perfectly well-posed. The outcome we want to maximize is clear (winning). The rules of the game are fixed and don’t change. When we build a policy for playing the game, we optimize against the best possible adversary. If we can find a policy that always wins against the perfect adversary, we can’t lose to anyone else.
Computational gameplay has pushed computers forward, captivating engineers and people to build machines with better capabilities. And it has given us insights into how we play games. Playing games is part of being human, and these competitions help connect us with each other and challenge ourselves to improve. What turned out to be interesting about computer gameplay was not what it taught us about some pie-in-the-sky conception of artificial intelligence. It was what it taught us about the games themselves,
What did computers teach us about Chess? Shannon posited that you could build a Chess playing robot with efficient tree search and reasonable board evaluation. This turned out to be correct, and proving it correct was simply a matter of waiting 50 years for engineers to scale up computers.
What did computers teach us about Checkers? Checkers is so simple that an exhaustive search can and does find the optimal strategy. Playing optimally in checkers ends in a draw, just like in tic-tac-toe.
What did computers teach us about Go? Computer science researchers in the 2010s realized that a simple "code book" that just looked at the board and guessed the next move could probably beat amateur players. Even though Go looked harder than Chess because of its massive game trees, a computer didn't require impossibly deep tree search to beat people. Maybe in retrospect this is not that surprising. Perhaps Go is, in many ways, easier than Chess.
What did we learn about Poker? Around 2010, researchers realized you could find optimal betting strategies for small subgames of Poker by writing the game in the correct way. This led to the solving of Limit Hold 'Em and competitive play at No Limit. Professional poker players started memorizing expected value tables from poker solvers so they could play "Game Theory Optimal" strategies in big tournaments. And then everyone realized optimal poker was boring and just meant folding all the time. It turned out that people didn’t play poker because they loved optimal stochastic strategies. They played Poker because they were degenerate gamblers.
In all these cases, computers taught people how to play better. Did our pursuits into computational game theory teach us anything about building superintelligence? No. Did it give humans competitive advantages so they could go best other humans? Yes.
A second important contribution of Game Theory was providing a particular means of participatory decision-making. When there is a complex problem with competing interests, Game Theory provides a programmatic, though imperfect, solution framework. Stakeholders first have to agree that a rational solution is the best solution. Though economists and weirdo Bayesian Rationalists love to claim otherwise, we now all appreciate that the “rationality” as defined by economists is a choice, not a natural property of human decision-making. But, given a tricky problem where not everyone will be happy with the outcome, participants can agree that they will accept the decision of a rational decision-maker. They can debate and agree upon the acceptable utilities associated with each potential outcome. And then the policymaker can design a game-theory optimal solution to the agreed-upon formulation of the problem.
This sort of game theoretic design matches doctors to residency programs, allocates communication channels for telecom providers, assigns children to high schools, and finds kidney donors. These solutions do not make everyone happy, and they need to be revisited as unforeseen negative impacts are discovered after the implementation. But, in some instances, Game Theory provides acceptable outcomes to challenging decision problems. It’s not the only game in town, but it can be a valuable tool in a mediator’s toolbox.
When von Neumann and Morgenstern invented Game Theory in the 1940s, they had audacious goals for a mathematical theory of economics. That “the typical problems of economic behavior become strictly identical with the mathematical notions of suitable games of strategy.” But Game Theory, as a means of understanding humans and human economies, was a failure. It’s only in the games we play—Chess, Checkers, DOTA, Starcraft—where definite, clear rules apply. In the reality of human social interaction, there’s far more room to play. Humans are not rational and don’t make decisions based on an abstract construction of rationality. Game Theory is useless at predicting how humans will behave when complex decisions are laid out before them. And there is no fix for this. Behavioral Economic theories aimed at casting humans as “predictably irrational” have been sullied by deep and fundamental replication crises and high-profile fraud scandals.
The history of Game Theory tells a cautionary tale about believing too much in our mathematics. But this is true about all decision making under uncertainty. I know we just spent half a semester trying to prove otherwise, but decision making under uncertainty can’t generally be solved by mathematics because the future is uncertain.
There are special cases where we can make partial progress. If we can force the world to behave by rigid rules, like in aerospace or computer engineering, we can simply optimize and force the uncertainty to remain small through engineering. If we have a lot of uncertainty but a simple decision space and homogeneity in the outcomes of individuals, we can run lots of randomized trials to improve policies. If we can have a clear outcome and rules, we can solve for Nash equilibrium strategies.
But what if there isn’t such regularity in future outcomes? What happens when our actions change their meaning in context? What happens if our conception of what a good outcome is changes? What happens when those outcomes can’t be cleanly compared and quantified? What if we can’t even properly pose our problem as an optimization? At this point, perhaps we need to stop hoping there’s an answer in data, statistics, and optimization. But that doesn’t mean the situation is hopeless. It just means we need to think harder. This course has got me excited to think outside of the optimization mindset. What other concepts can we bring to make sense of the future?