Enabling First-Order Gradient-Based Learning for Equilibrium Computation in Markets

Nils Kohring, Fabian Raoul Pieroth, Martin Bichler
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:17327-17342, 2023.

Abstract

Understanding and analyzing markets is crucial, yet analytical equilibrium solutions remain largely infeasible. Recent breakthroughs in equilibrium computation rely on zeroth-order policy gradient estimation. These approaches commonly suffer from high variance and are computationally expensive. The use of fully differentiable simulators would enable more efficient gradient estimation. However, the discrete allocation of goods in economic simulations is a non-differentiable operation. This renders the first-order Monte Carlo gradient estimator inapplicable and the learning feedback systematically misleading. We propose a novel smoothing technique that creates a surrogate market game, in which first-order methods can be applied. We provide theoretical bounds on the resulting bias which justifies solving the smoothed game instead. These bounds also allow choosing the smoothing strength a priori such that the resulting estimate has low variance. Furthermore, we validate our approach via numerous empirical experiments. Our method theoretically and empirically outperforms zeroth-order methods in approximation quality and computational efficiency.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-kohring23a, title = {Enabling First-Order Gradient-Based Learning for Equilibrium Computation in Markets}, author = {Kohring, Nils and Pieroth, Fabian Raoul and Bichler, Martin}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {17327--17342}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/kohring23a/kohring23a.pdf}, url = {https://proceedings.mlr.press/v202/kohring23a.html}, abstract = {Understanding and analyzing markets is crucial, yet analytical equilibrium solutions remain largely infeasible. Recent breakthroughs in equilibrium computation rely on zeroth-order policy gradient estimation. These approaches commonly suffer from high variance and are computationally expensive. The use of fully differentiable simulators would enable more efficient gradient estimation. However, the discrete allocation of goods in economic simulations is a non-differentiable operation. This renders the first-order Monte Carlo gradient estimator inapplicable and the learning feedback systematically misleading. We propose a novel smoothing technique that creates a surrogate market game, in which first-order methods can be applied. We provide theoretical bounds on the resulting bias which justifies solving the smoothed game instead. These bounds also allow choosing the smoothing strength a priori such that the resulting estimate has low variance. Furthermore, we validate our approach via numerous empirical experiments. Our method theoretically and empirically outperforms zeroth-order methods in approximation quality and computational efficiency.} }
Endnote
%0 Conference Paper %T Enabling First-Order Gradient-Based Learning for Equilibrium Computation in Markets %A Nils Kohring %A Fabian Raoul Pieroth %A Martin Bichler %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-kohring23a %I PMLR %P 17327--17342 %U https://proceedings.mlr.press/v202/kohring23a.html %V 202 %X Understanding and analyzing markets is crucial, yet analytical equilibrium solutions remain largely infeasible. Recent breakthroughs in equilibrium computation rely on zeroth-order policy gradient estimation. These approaches commonly suffer from high variance and are computationally expensive. The use of fully differentiable simulators would enable more efficient gradient estimation. However, the discrete allocation of goods in economic simulations is a non-differentiable operation. This renders the first-order Monte Carlo gradient estimator inapplicable and the learning feedback systematically misleading. We propose a novel smoothing technique that creates a surrogate market game, in which first-order methods can be applied. We provide theoretical bounds on the resulting bias which justifies solving the smoothed game instead. These bounds also allow choosing the smoothing strength a priori such that the resulting estimate has low variance. Furthermore, we validate our approach via numerous empirical experiments. Our method theoretically and empirically outperforms zeroth-order methods in approximation quality and computational efficiency.
APA
Kohring, N., Pieroth, F.R. & Bichler, M.. (2023). Enabling First-Order Gradient-Based Learning for Equilibrium Computation in Markets. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:17327-17342 Available from https://proceedings.mlr.press/v202/kohring23a.html.

Related Material