Learning equilibria in symmetric auction games using artificial neural networks

Brown, N. & Sandholm, T. Superhuman AI for Multiplayer Poker. Science 365, 885-890 (2019).

MathSciNet Google Scholar article

Daskalakis, C., Ilyas, A., Syrgkanis, V. & Zeng, H. Training with optimism. Preprint at https://arxiv.org/abs/1711.00141 (2017).

Silver, D. et al. A general reinforcement learning algorithm that masters chess, shogi and Go through self-play. Science 362, 1140–1144 (2018).

MathSciNet Google Scholar article

Daskalakis, C., Goldberg, P. & Papadimitriou, C. The complexity of calculating a Nash equilibrium. SIAM J. Comput. 39, 195-259 (2009).

MathSciNet Google Scholar article

Brown, G. W in Analysis of production activity and allocation (ed. Koopmans, TC) 374-376 (Wiley, 1951).

Google Scholar

Zinkevich, M. On-line convex programming and generalized infinitesimal gradient ascension. In Proc. 20th International Conference on Machine Learning 928-936 (ICML, 2003).

Bowling, M. Convergence and no-regret in multiagent learning. In Advances in Neural Information Processing Systems 209-216 (NIPS, 2005).

Milgrom, PR & Weber, RJ A Theory of Bidding and Bidding. Econometrics 50, 1089-1122 (1982).

Klemperer, P. Auction theory: a guide to the literature. J. Econ. Surveys 13, 227-286 (1999).

Google Scholar article

Vickrey, W. Counter-Speculation, Auctions, and Competitive Closed Tenders. J. Finances 16, 8-37 (1961).

MathSciNet Google Scholar article

Krishna, V. Auction theory (Academic, 2009).

Bergemann, D. & Morris, S. Robust implementation in direct mechanisms. Rev. Econ. Stud. 76, 1175-1204 (2009).

MathSciNet Google Scholar article

Campo, S., Perrigne, I. & Vuong, Q. Asymmetry in first-price auctions with private affiliates. J. Appl. Econom. 18, 179-207 (2003).

Google Scholar article

Janssen, MC Reflections on the 2020 Memorial Nobel Prize for Paul Milgrom and Robert Wilson. Erasmus J. Philos. Econ. 13, 177-184 (2020).

Google Scholar

Heinrich, J. & Silver, D. Deep learning by reinforcing self-play in games with imperfect information. Preprint at https://arxiv.org/abs/1603.01121 (2016).

Lanctot, M. et al. A unified game theory approach for multi-agent reinforcement learning. In Proc. 31st International Conference on Neural Information Processing Systems (NIPS, 2017).

Brown, N., Lerer, A., Gross, S. & Sandholm, T. Minimization of deep counterfactual regrets. In Proc. 36th International Conference on Machine Learning 793-802 (PMLR, 2019).

Brown, N. & Sandholm, T. Superhuman AI for Multiplayer Poker. Science 365, 885-890 (2019).

MathSciNet Google Scholar article

Reeves, DM & Wellman, MP Computing equilibrium strategies in infinite sets of incomplete information. Proc. 20th Conference on Uncertainty in Artificial Intelligence (AUI, 2004).

Naroditskiy, V. & Greenwald, A. Using the iterated best response to find Bayes-Nash equilibria in auctions 1894-1895 (AAAI, 2007).

Rabinovich, Z., Naroditskiy, V., Gerding, EH & Jennings, NR Calculation of pure Bayesian-Nash equilibria in finite action and continuous type games. Artif. Inform. 195, 106-139 (2013).

MathSciNet Google Scholar article

Bosshard, V., Bünz, B., Lubin, B. & Seuken, S. Calculation of Bayes-Nash equilibria in combinatorial auctions with continuous value and action spaces. In Proc. 26th Joint International Conference on Artificial Intelligence 119-127 (IJCAI, 2017).

Bosshard, V., Bünz, B., Lubin, B. & Seuken, S. Calculation of Bayes-Nash equilibria in combinatorial auctions with verification. J. Artif. Inform. Res. 69, 531-570 (2020).

MathSciNet Google Scholar article

Feng, Z., Guruganesh, G., Liaw, C., Mehta, A. & Sethi, A. Convergence analysis of no-regret auction algorithms in repeat auctions. Preprint at https://arxiv.org/abs/2009.06136 (2020).

Li, Z. & Wellman, MP Evolutionary strategies for the approximate resolution of Bayesian games. In Proc. AAAI Conference on Artificial Intelligence Flight. 35, 5531-5540 (AAAI, 2021).

Cai, Y. & Papadimitriou, C. Concurrent Bayesian auctions and computational complexity. In Proc. 15th ACM Conference on Economics and Computing 895-910 (ACM, 2014).

Fudenberg, D. & Levine, DK Learning and Balance. Annu. Rev. Econ. 1, 385-420 (2009).

Google Scholar article

Jafari, A., Greenwald, A., Gondek, D. & Ercal, G. On No Regret Learning, Fictional Play and Nash Balance. Proc. 18th International Conference on Machine Learning 226-233 (ICML, 2001).

Stoltz, G. & Lugosi, G. Learning correlated equilibria in games with compact sets of strategies. Econ games. Behave yourself. 59, 187-208 (2007).

MathSciNet Google Scholar article

Hartline, J., Syrgkanis, V. & Tardos, E. No-Regret Learning in Bayesian Games. In Advances in Neural Information Processing Systems (eds Cortes, C. et al.) Vol. 28, 3061-3069 (NIPS, 2015); http://papers.nips.cc/paper/6016-no-regret-learning-in-bayesian-games.pdf

Foster, DJ, Li, Z., Lykouris, T., Sridharan, K. & Tardos, E. Learning in games: robustness of rapid convergence. In Advances in Neural Information Processing Systems 4734-4742 (NIPS, 2016).

Viossat, Y. & Zapechelnyuk, A. Dynamics without regret and fictitious play. J. Econ. Theory 148, 825-842 (2013).

MathSciNet Google Scholar article

Mazumdar, E., Ratliff, LJ & Sastry, SS On gradient learning in continuous games. SIMODS 2, 103-131 (2020).

MathSciNet Google Scholar

Dütting, P., Feng, Z., Narasimhan, H., Parkes, D. & Ravindranath, SS Optimal auctions through deep learning. In International Conference on Machine Learning 1706-1715 (PMLR, 2019).

Feng, Z., Narasimhan, H. & Parkes, DC Deep learning for revenue and budget optimized auctions. In Proc. 17th International Conference on Autonomous Agents and Multi-Agent Systems 354-362 (AAMAS, 2018).

Tacchetti, A., Strouse, D., Garnelo, M., Graepel, T. & Bachrach, Y. Neural architecture for the design of truthful and efficient auctions. Preprint at https://arxiv.org/abs/1907.05181 (2019).

Weissteiner, J. & Seuken, S. Iterative combinatorial auctions based on deep learning. In Proc. AAAI Conference on Artificial Intelligence Flight. 34, 2284-2293 (AAAI, 2020).

Morrill, D. et al. Retrospective and sequential rationality of the correlated game. Preprint at https://arxiv.org/abs/2012.05874 (2020).

Hartford, JS Deep Learning to Predict Human Strategic Behavior. doctorate thesis, Univ. British Columbia (2016).

Ghani, R. & Simmons, H. Predicting the final price of online auctions. In Proc. International Workshop on Data Mining and Adaptive Modeling Methods for Economics and Management (CiteSeer, 2004).

Zheng, S. et al. The AI ​​Economist: Improving equality and productivity through AI-driven tax policies. Preprint at https://arxiv.org/abs/2004.13332 (2020).

Goeree, JK & Lien, Y. On the impossibility of core selection auctions. Theoretical econ. 11, 41-52 (2016).

MathSciNet Google Scholar article

Bichler, M. & Goeree, JK Spectrum Auction Design Manual (Cambridge Univ. Press, 2017).

Debnath, L. et al. Introduction to Hilbert spaces with applications (Academic, 2005).

Bichler, M., Guler, K. & Mayer, S. Shared-Price Supply Auctions – Can Bayesian Equilibrium Strategies Predict Human Bidding Behavior in Multi-Object Auctions? Prod. Oper. To manage. 24, 1012-1027 (2015).

Google Scholar article

Ui, T. Bayesian nash equilibrium and variational inequalities. J. Maths. Econ. 63, 139-146 (2016).

MathSciNet Google Scholar article

Hornik, K. Capacities of approximation of multilayer feedforward networks. Neural networks 4, 251-257 (1991).

Google Scholar article

Wierstra, D. et al. Natural evolution strategies. J. Mach. To learn. Res. 15, 949-980 (2014).

MathSciNet MATH Google Scholar

Salimans, T., Ho, J., Chen, X., Sidor, S. & Sutskever, I. Evolutionary strategies as an evolutionary alternative to reinforcement learning. Preprint at https://arxiv.org/abs/1703.03864 (2017).

Benaím, M., Hofbauer, J. & Sorin, S. Perturbations of dynamical systems with defined values, with applications to game theory. Dyna. Games Appl. 2, 195-205 (2012).

MathSciNet Google Scholar article

Letcher, A. et al. Differentiable game mechanics. J. Mach. To learn. Res. 20, 1–40 (2019).

MathSciNet Google Scholar

Monderer, D. & Shapley, LS Potential games. Econ games. Behave yourself. 14, 124-143 (1996).

MathSciNet Google Scholar article

Bünz, B., Lubin, B. & Seuken, S. Designing payment rules by selection of kernels: a computer research approach. In Proc. ACM 2018 Conference on Economics and Computing 109 (ACM, 2018).

Ausubel, LM & Baranov, O. Nuclei selection auctions with incomplete information. Int. J. Game theory 49, 251-273 (2019).

Guler, K., Bichler, M. & Petrakis, I. Ascending combinatorial auctions with risk-averse bidders. Group decisions. To negotiate. 25, 609-639 (2016).

Google Scholar article

Jehiel, P., Meyer-ter-Vehn, M., Moldovanu, B. & Zame, WR The limits of ex post implementation. Econometrics 74, 585-610 (2006).

MathSciNet Google Scholar article

Daskalakis, C., Skoulakis, S. & Zampetakis, M. The complexity of constrained min-max optimization. In Pro. 53rd Annual ACM SIGACT Symposium on Computing Theory 1466-1478 (STOC, 2021).

Vorobeychik, Y., Reeves, DM & Wellman, MP Design of constrained automated mechanisms for infinite sets of incomplete information. In Proc. 23rd Conference on Uncertainty in Artificial Intelligence 400-407 (AUI, 2007).

Viqueira, EA, Cousins, C., Mohammad, Y. & Greenwald, A. Design of empirical mechanisms: design of mechanisms from data. In Proc. 35th conference on uncertainty in artificial intelligence 1094-1104 (PMLR, 2020).

Kingma, DP & Ba, J. Adam: a stochastic optimization method. Preprint at https://arxiv.org/abs/1412.6980 (2015).

Paszke, A. et al. Automatic differentiation in pytorch. In 31st Neural Information Processing Systems Conference (NIPS, 2017).

Heidekrüger, S., Kohring, N., Sutterer, S. & Bichler, M. bnelearn: a framework for learning balance in sealed auctions (Github, 2021); https://github.com/heidekrueger/bnelearn