# 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.83755934,"math_prob":0.895623,"size":5263,"snap":"2023-40-2023-50","text_gpt3_token_len":1184,"char_repetition_ratio":0.102300815,"word_repetition_ratio":0.70435965,"special_character_ratio":0.2166065,"punctuation_ratio":0.13686535,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9807504,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-03T03:43:48Z\",\"WARC-Record-ID\":\"<urn:uuid:ee85ada2-4ae2-4fed-b2ab-24a1cd4ed1e1>\",\"Content-Length\":\"16538\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c434215f-8ab0-4408-a055-790cdbb51648>\",\"WARC-Concurrent-To\":\"<urn:uuid:8f244287-20bb-4ec1-a94a-2115698b3d2d>\",\"WARC-IP-Address\":\"185.199.109.153\",\"WARC-Target-URI\":\"https://proceedings.mlr.press/v202/li23ao.html\",\"WARC-Payload-Digest\":\"sha1:NCVX2LBYDFZS3ZUTQQUIVGEDDEY3VHWG\",\"WARC-Block-Digest\":\"sha1:W4RRUTNKSHFGLHPMCJQCWPINMMUABK36\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100484.76_warc_CC-MAIN-20231203030948-20231203060948-00386.warc.gz\"}"}