Using machine learning to understand complex auctions

Using a new machine learning algorithm, a team at the Technical University of Munich (TUM) has succeeded in analyzing complex markets and their equilibrium strategies. Until now, such analyses were limited to very simple auction markets. The new numerical method opens up new possibilities for economic theory and new applications as in wireless spectrum auctions, among others.

Life is a game – at least from the perspective of game theory. This branch of mathematics provides tools for describing the behavior of actors in strategic interactions and computing optimal behavioral responses. Applications extend from board games such as chess to the analysis of international climate negotiations. An important subfield of game theory is auction theory, which is used in economic theory to model markets. Several Nobel Prizes in Economic Sciences have been awarded in this area, most recently to Robert Wilson and Paul Milgrom in 2020.

Auctions are based on the following principle: Bids are submitted by several parties seeking to purchase goods. The parties can take a strategic approach, for example by bidding less than they are willing to spend in order to maximize their profits. However, they must be prepared for the other parties to act strategically, too.

Equilibrium points for complex auctions calculated for the first time

An important concept for describing strategic behavior in auctions is the Bayes Nash equilibrium. In simple terms, this is the situation in which none of the parties could improve their expected utility by changing their strategy – a sort of optimal line. An equilibrium of this kind can be modeled as a system of differential equations which cannot be solved exactly in the case of more complex markets. Precise equilibrium strategies exist only for simple auctions, for example when the parties are bidding on only one good.

Martin Bichler, Professor of Decision Sciences and Systems at TUM, and his team have developed a new approach: “Machine learning is not yet widely used in auction theory. Using neural networks, we were able to compute equilibrium strategies for complex auction models that were previously unsolvable,” says Prof. Bichler.

Neural networks try to outbid each other

The new process – neural pseudogradient ascent (NPGA) – is based on several neural networks submitting competing bids and repeatedly adjusting their strategies after each round of bidding.  They ultimately reach a Bayes Nash equilibrium without having to solve the corresponding differential equations explicitly using conventional methods.

“For common auction models we can prove mathematically that the results of the NPGA method reliably converge to the equilibrium strategy,” says Martin Bichler. “We also showed in experiments that our process delivers extremely close approximations to equilibrium strategies for markets.”

Potential applications in theory and practice

Prof. Bichler hopes that the new algorithm will help economists to analyze more complex markets and their equilibria. But real-world applications are also conceivable: Since the mid-1990s, governments around the world have sold wireless spectrum through auctions. The Nobel laureates Robert Wilson and Paul Milgrom have developed auction formats for this purpose.

“Spectrum auctions are an exciting real-world example,” says Martin Bichler, who is the editor of a handbook on spectrum auction design and has also served as a consultant in such auctions. “NPGA can help to identify strategic issues in advance that could lead to undesirable results – for example a high likelihood of bidding strategies resulting in spectrum licenses being purchased by inefficient bidders. In this case, the organizers could opt for a different auction mechanism.  And conversely, the algorithm could also support bidders in developing their bidding strategies.”

Publication:

Bichler, M., Fichtl, M., Heidekrüger, S, Kohring, N., Sutterer, P. “Learning equilibria in symmetric auction games using artificial neural networks”. Nature Machine Intelligence (2021). DOI:10.1038/s42256-021-00365-4

Further information:

The procedure was developed by Martin Bichler in the DFG Reinhart Koselleck project (BI 1057/9-1).

The source code is available at https://github.com/heidekrueger/bnelearn

Contact:

Prof. Dr. Martin Bichler
Technical University of Munich
Chair of Decision Sciences and Systems
Tel: +49 (0) 89 289 - 17500
bichler@in.tum.de
www.tum.de