| The legendary mathematician John von Neumann made major contributions to many fields of math and science, from set theory to quantum physics to climate science. But he's most famous for two works that appeared just one year apart in the mid-1940s. The first was a 600-page book that established the theoretical foundations of game theory, the mathematical study of strategic competitions. The second, a technical report on the design of a new kind of computer that could run different programs to accomplish different tasks, was one of the most influential documents in the history of computer science.
If von Neumann saw a connection between computer science and game theory, he never wrote about it, and the two fields mostly evolved separately for the next 50 years. But toward the end of the 20th century, researchers began to appreciate that mathematical techniques from computer science could illuminate many of the most important questions in game theory and vice versa.
Game theorists study mathematical models of competitions ranging from rock-paper-scissors to markets and auctions. In all of these contests, the most advantageous moves for each player can depend on what other players do. It can be hard to figure out what strategy is best.
Computer scientists also study mathematical models of real-world problems. But they traditionally focus on cases where a single actor evaluates a fixed environment. For the classic problem of finding the fastest route through a road network, for instance, they assume that the time required to travel down each road doesn't change.
Of course in the real world, if everyone takes the same roads, there might be a traffic jam, which will affect which route is fastest. Similar congestion effects can arise in communication networks. The advent of the internet prompted computer scientists to pay more attention to cases where many actors try to solve a problem at once, and ideas from game theory were indispensable to their analysis. Computer science techniques, in turn, proved useful for analyzing games where players compete directly.
Researchers discovered many other links between computer science and game theory in the 1990s and early 2000s. More recently, the growing use of price-setting algorithms and the rise of powerful artificial intelligence models have raised new questions that scientists are just beginning to explore.
What's New and Noteworthy
One of the most famous results in game theory says that in every game, there's a special state called Nash equilibrium, where each player's strategy is the best possible response to what every other player does. In principle, once a game reaches equilibrium, nothing will change, since no player has any incentive to try a different strategy. But the original theorem that established the existence of a Nash equilibrium said nothing about how players would get there. In a celebrated 2008 paper, a team of computer scientists including Constantinos Daskalakis proved that in some games, it's fiendishly difficult to figure out what the Nash equilibrium would look like. Erica Klarreich recounted the story of that breakthrough in her 2018 profile of Daskalakis. Klarreich also covered a related result, in which two computer scientists established limits on how quickly players can reach equilibrium when they don't initially know how much their opponents value different outcomes.
To theoretical computer scientists, the word "algorithm" means a mathematical procedure for solving a specific problem. Game theorists have embraced this definition, using algorithms to model the strategies that humans adopt in many different games. But these days, humans are no longer the only players in economic competitions that game theorists study. Merchants often determine how much to charge for their products using pricing algorithms — computer programs that follow mathematical rules to automatically adjust prices based on the latest data about the market. The widespread adoption of pricing algorithms has provoked concern that unexpected interactions between them could yield artificially high prices, a phenomenon dubbed "algorithmic collusion." In October, I wrote about a recent paper that identified a new way that inflated prices can arise even with seemingly well-behaved algorithms.
Much of the work at the intersection of computer science and game theory uses computer science techniques to analyze the mathematical properties of existing games. In 2024, Quanta contributor Steve Nadis reported on new work by AI researchers that inverts this approach. The researchers devised a new game that a large language model like ChatGPT can play against itself, tailoring the rules and rewards so that winning the game made the model's outputs more consistent and reliable. Thirty years after game theory and computer science came together, their relationship is still evolving. | 
