Neural Network Algorithm Generates Groundbreaking Analysis of Complex Auction Models
Finding the equilibria of various auctions can be a complicated task and isn’t always achievable by standard analysis. The equilibria of an auction refer to outcomes of that auction that come to be when bidders make bids using strategies they have no incentive to deviate from, i.e. equilibrium strategies. Strategies that generate a Nash equilibrium (which is the result of the optimal move a bidder can make in a given circumstance) under all circumstances are called dominant strategies, and are examples of equilibrium strategies. It is possible to find equilibria in auctions that have dominant strategies through standard methods, as these equilibria can be considered the Nash equilibria. In class we learned of one such example: the second-price single-item auction. In a second-price single-item auction, bidding one’s value produces a Nash equilibrium for all situations and is therefore a dominant strategy even when other bidders’ values/bids are private. Because there is no incentive for the bidder to deviate from this strategy, simulating an auction where bidders use this strategy would produce an equilibrium result, and it is easy to find.
However, in games that don’t have dominant strategies, the equilibrium strategies (and consequently the equilibria) are much tougher to decipher. One such example of an auction that falls into this group is the first-price single-item auction; the optimal bid to make is dependent on the moves that other bidders make, so there does not exist a dominant strategy to this type of auction. In these types of auctions, a bidder’s equilibrium strategy must be derived by finding the Bayesian Nash equilibrium, which is the optimal strategy a bidder should follow given consideration of the optimal strategies that other bidders in the auction will follow. Finding equilibrium strategies and local equilibria in these types of auctions is complicated and not always possible through standard analysis. Furthermore, finding the equilibrium values for multi-item auctions (save specific cases) isn’t very well understood.
But recently, a group of researchers at the Technical University of Munich have developed a machine learning algorithm that circumvents these complications in finding equilibria by using reinforcement learning techniques on neural networks. Instead of finding the local equilibria of auctions by finding the Nash equilibrium or Bayesian Nash equilibrium, the algorithm implements neural networks as strategies, runs the strategies against themselves, updates the strategies until they provide optimal value, and then simulates the auction result using these strategies. In short, the algorithm effectively “learns” its own equilibrium strategies by playing against itself many times, and uses these equilibrium strategies to find equilibrium values for the auction. This method has been found to work extremely well; when looking at the results the algorithm gives on auctions with known equilibria (which were found by calculating the Bayesian Nash equilibria) they are extremely close!
As can be seen by the graph above for this first-bid one-item auction, given the valuation of the item for a bidder, the bid predictions by the algorithm (denoted NPGA) closely resemble the the bids calculated by finding the Bayesian Nash equilibrium (BNE). These results show promise that the algorithm can properly approximate auctions with unknown equilibria. This algorithm could be useful by showing sellers previously not-well-understood auction formats whose results would best suit their needs, giving more diversity to the auction formats available to them. It could also provide insight to researchers about equilibria of complex auctions, allowing for further analysis of these auctions.
LINK: https://techxplore.com/news/2021-09-machine-technique-local-equilibria-symmetric.html