Achieving Hierarchy-Free Approximation for Bilevel Programs with Equilibrium Constraints

Jiayang Li, Jing Yu, Boyi Liu, Yu Nie, Zhaoran Wang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:20312-20335, 2023.

Abstract

In this paper, we develop an approximation scheme for solving bilevel programs with equilibrium constraints, which are generally difficult to solve. Among other things, calculating the first-order derivative in such a problem requires differentiation across the hierarchy, which is computationally intensive, if not prohibitive. To bypass the hierarchy, we propose to bound such bilevel programs, equivalent to multiple-followers Stackelberg games, with two new hierarchy-free problems: a $T$-step Cournot game and a $T$-step monopoly model. Since they are standard equilibrium or optimization problems, both can be efficiently solved via first-order methods. Importantly, we show that the bounds provided by these problems — the upper bound by the $T$-step Cournot game and the lower bound by the $T$-step monopoly model — can be made arbitrarily tight by increasing the step parameter $T$ for a wide range of problems. We prove that a small $T$ usually suffices under appropriate conditions to reach an approximation acceptable for most practical purposes. Eventually, the analytical insights are highlighted through numerical examples.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-li23ao, title = {Achieving Hierarchy-Free Approximation for Bilevel Programs with Equilibrium Constraints}, author = {Li, Jiayang and Yu, Jing and Liu, Boyi and Nie, Yu and Wang, Zhaoran}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {20312--20335}, 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/li23ao/li23ao.pdf}, url = {https://proceedings.mlr.press/v202/li23ao.html}, abstract = {In this paper, we develop an approximation scheme for solving bilevel programs with equilibrium constraints, which are generally difficult to solve. Among other things, calculating the first-order derivative in such a problem requires differentiation across the hierarchy, which is computationally intensive, if not prohibitive. To bypass the hierarchy, we propose to bound such bilevel programs, equivalent to multiple-followers Stackelberg games, with two new hierarchy-free problems: a $T$-step Cournot game and a $T$-step monopoly model. Since they are standard equilibrium or optimization problems, both can be efficiently solved via first-order methods. Importantly, we show that the bounds provided by these problems — the upper bound by the $T$-step Cournot game and the lower bound by the $T$-step monopoly model — can be made arbitrarily tight by increasing the step parameter $T$ for a wide range of problems. We prove that a small $T$ usually suffices under appropriate conditions to reach an approximation acceptable for most practical purposes. Eventually, the analytical insights are highlighted through numerical examples.} }
Endnote
%0 Conference Paper %T Achieving Hierarchy-Free Approximation for Bilevel Programs with Equilibrium Constraints %A Jiayang Li %A Jing Yu %A Boyi Liu %A Yu Nie %A Zhaoran Wang %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-li23ao %I PMLR %P 20312--20335 %U https://proceedings.mlr.press/v202/li23ao.html %V 202 %X In this paper, we develop an approximation scheme for solving bilevel programs with equilibrium constraints, which are generally difficult to solve. Among other things, calculating the first-order derivative in such a problem requires differentiation across the hierarchy, which is computationally intensive, if not prohibitive. To bypass the hierarchy, we propose to bound such bilevel programs, equivalent to multiple-followers Stackelberg games, with two new hierarchy-free problems: a $T$-step Cournot game and a $T$-step monopoly model. Since they are standard equilibrium or optimization problems, both can be efficiently solved via first-order methods. Importantly, we show that the bounds provided by these problems — the upper bound by the $T$-step Cournot game and the lower bound by the $T$-step monopoly model — can be made arbitrarily tight by increasing the step parameter $T$ for a wide range of problems. We prove that a small $T$ usually suffices under appropriate conditions to reach an approximation acceptable for most practical purposes. Eventually, the analytical insights are highlighted through numerical examples.
APA
Li, J., Yu, J., Liu, B., Nie, Y. & Wang, Z.. (2023). Achieving Hierarchy-Free Approximation for Bilevel Programs with Equilibrium Constraints. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:20312-20335 Available from https://proceedings.mlr.press/v202/li23ao.html.

Related Material