September 14, 2021 feature
A machine learning technique that can learn local equilibria in symmetric auction games
Over the past few decades, computer scientists have been exploring the potential of applying game theory and artificial intelligence (AI) tools to chess, the abstract strategy board game go, or other games. Another valuable use of game theory is in the economic sciences, particularly as a framework to explain strategic interactions in markets and the resulting outcomes.
One of the most common theoretical constructs designed to enable the application of game theory in economics is auction theory. Auction theory is an application of game theory that specifically describes how different bidders may act in auction markets.
When applying auction theory to real or realistic markets with multiple items on sale and with value interdependencies, however, calculating equilibrium bidding strategies for auction games can be challenging. In game theory, the Bayesian Nash equilibrium (BNE) occurs when no player (or bidder) can improve their chosen strategy after they considered their opponent's choices.
The BNE is considered a stable outcome of a game or auction and can serve as a prediction for the outcome, yet it is far harder to calculate for auctions compared to finite complete-information games such as rock-paper-scissors. This is because opponents' values and bids are continuous.
Past studies have introduced several numerical techniques that could be used to learn equilibria in auction games. These methods are either based on calculations of pointwise best responses in the strategy space or on iteratively solving subgames. Their use was largely restricted to simple single-object auctions.
Researchers at Technical University of Munich have recently developed a new machine learning technique that can be used to learn local equilibria in symmetric auction games. This technique, introduced in a paper published in Nature Machine Intelligence, works by representing strategies as neural networks and then applying policy iteration based on gradient dynamics while a bidder is playing against himself.
"Just last year, the Nobel Prize in Economic Sciences was awarded to Paul Milgrom and Bob Wilson for their work on auction theory and design," Martin Bichler, one of the researchers who carried out the study, told TechXplore. "Early work by Nobel Prize laureate William Vickrey led to game-theoretical equilibrium strategies for simple single-object auctions, which are based on the solution to differential equations. Unfortunately, more complex multi-object auctions have turned out very challenging to solve and equilibrium bidding strategies are known only for very specific cases."
Bichler and his colleagues have been conducting research related to auction theory and exploring its applications for several years now. In their recent study, they specifically set out to develop a technique based on artificial neural networks and self-play that can automatically learn equilibrium bidding strategies in auctions.
"We proved that our method converges with the equilibrium strategy in a wide variety of auction models with standard assumptions," Bichler said. "This allows us to develop equilibrium solvers that compute equilibrium bidding strategies for various types of auction models numerically, which was not possible so far."
When the researchers tested their technique, they found that the BNEs it approximated coincided with the analytically derived equilibrium, whenever it was available. The estimated error was also very low in cases where the analytical equilibrium is unknown. In the future, the tool they developed could thus be used to investigate the efficiency of auctions and determine what bidding strategies one may expect will emerge in equilibrium.
In addition to its significant contribution to the study of auction theory, the technique created by Bichler and his colleagues could be a highly valuable tool for auctioneers, as it could help them to select auction formats and bidders to develop their bidding strategies. For instance, it might prove useful during spectrum auctions, which are used by regulators worldwide to distribute the rights to transmit signals over specific bands of the electromagnetic spectrum to different mobile network providers.
"We first adapted the standard learning process in neural networks (gradient descent) to handle the discontinuities of utility functions in our auction models," Bichler said. "Secondly, we could prove that the method converges to equilibrium in auctions with only a mild set of assumptions. This is interesting because equilibrium learning of this sort does not converge in general in games."
In their future studies, Bichler and his colleagues would like to test their technique on different scenarios and ensure that it generalizes well. In addition, they plan to develop tools that can automatically compute equilibria in a wider variety of game theory-related problems, reaching beyond symmetric auction games.
© 2021 Science X Network