Skip to main content
SpringerLink
Log in

A Bridge Between Bilevel Programs and Nash Games

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our “uneven” horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our “uneven” horizontal model, in some sense, lies between the vertical bilevel model and a “pure” horizontal game.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235–256 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Dempe, S.: Foundations of Bilevel Programming. Springer Science & Business Media, New York (2002)

    MATH  Google Scholar 

  3. Dempe, S.: Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52(3), 333–359 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dempe, S., Zemkoho, A.: The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math. Program. 138(1–2), 447–473 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  5. Stackelberg, H.V.: Marktform und Gleichgewicht. Springer, Berlin (1934)

    Google Scholar 

  6. Aussel, D., Correa, R., Marechal, M.: Electricity spot market with transmission losses. Management 9(2), 275–290 (2013)

    MathSciNet  MATH  Google Scholar 

  7. Hu, M., Fukushima, M.: Existence, uniqueness, and computation of robust Nash equilibria in a class of multi-leader-follower games. SIAM J. Optim. 23(2), 894–916 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  8. Zemkoho, A.: Solving ill-posed bilevel programs. Set-Valued Var. Anal. 24(3), 423–448 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dempe, S., Mordukhovich, B., Zemkoho, A.: Sensitivity analysis for two-level value functions with applications to bilevel programming. SIAM J. Optim. 22(4), 1309–1343 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  10. Dempe, S., Dutta, J., Mordukhovich, B.: New necessary optimality conditions in optimistic bilevel programming. Optimization 56(5–6), 577–604 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Dempe, S., Zemkoho, A.: The generalized Mangasarian–Fromowitz constraint qualification and optimality conditions for bilevel programs. J. Optim. Theory Appl. 148(1), 46–68 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  12. Ye, J.: Constraint qualifications and KKT conditions for bilevel programming problems. Math. Oper. Res. 31(4), 811–824 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bard, J.: An algorithm for solving the general bilevel programming problem. Math. Oper. Res. 8(2), 260–272 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dempe, S., Franke, S.: Solution algorithm for an optimistic linear Stackelberg problem. Comput. Oper. Res. 41, 277–281 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Dempe, S., Franke, S.: On the solution of convex bilevel optimization problems. Comput. Optim. Appl. 63(3), 685–703 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  16. Lin, G.H., Xu, M., Ye, J.: On solving simple bilevel programs with a nonconvex lower level program. Math. Program. 144(1–2), 277–305 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  17. Mitsos, A., Lemonidis, P., Barton, P.: Global solution of bilevel programs with a nonconvex inner program. J. Global Optim. 42(4), 475–513 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Outrata, J.: On the numerical solution of a class of Stackelberg problems. Zeitschrift für Operations Research 34(4), 255–277 (1990)

    MathSciNet  MATH  Google Scholar 

  19. Solodov, M.: An explicit descent method for bilevel convex optimization. J. Convex Anal. 14(2), 227 (2007)

    MathSciNet  MATH  Google Scholar 

  20. Vicente, L., Calamai, P.: Bilevel and multilevel programming: a bibliography review. J. Global Optim. 5(3), 291–306 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  21. Xu, M., Ye, J.: A smoothing augmented Lagrangian method for solving simple bilevel programs. Comput. Optim. Appl. 59(1–2), 353–377 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  22. Outrata, J.: A note on the usage of nondifferentiable exact penalties in some special optimization problems. Kybernetika 24(4), 251–258 (1988)

    MathSciNet  MATH  Google Scholar 

  23. Ye, J., Zhu, D.: New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM J. Optim. 20(4), 1885–1905 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85(1), 107–134 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  25. Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17(1), 259–286 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  26. Luo, Z.Q., Pang, J.S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)

    Book  MATH  Google Scholar 

  27. Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program. 131(1–2), 37–48 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  28. Dreves, A., Facchinei, F., Kanzow, C., Sagratella, S.: On the solution of the KKT conditions of generalized Nash equilibrium problems. SIAM J. Optim. 21(3), 1082–1108 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  29. Facchinei, F., Lampariello, L.: Partial penalization for the solution of generalized Nash equilibrium problems. J. Global Optim. 50(1), 39–57 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  30. Facchinei, F., Lampariello, L., Sagratella, S.: Recent advancements in the numerical solution of generalized Nash equilibrium problems. Quaderni di Matematica-Volume in ricordo di Marco D’Apuzzo 27, 137–174 (2012)

    MathSciNet  Google Scholar 

  31. Facchinei, F., Sagratella, S.: On the computation of all solutions of jointly convex generalized Nash equilibrium problems. Optim. Lett. 5(3), 531–547 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  32. Pang, J.S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. CMS 2, 21–56 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  33. Sagratella, S.: Computing all solutions of nash equilibrium problems with discrete strategy sets. SIAM J. Optim. 26(4), 2190–2218 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  34. Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. Ann. Oper. Res. 175(1), 177–211 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  35. Dorsch, D., Jongen, H.T., Shikhman, V.: On intrinsic complexity of Nash equilibrium problems and bilevel optimization. J. Optim. Theory Appl. 159(3), 606–634 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  36. Lampariello, L., Sagratella, S.: It is a matter of hierarchy: a Nash equilibrium problem perspective on bilevel programming. Department of Computer, Control and Management Engineering, Sapienza University of Rome, Technical report (2015)

  37. Allende, G., Still, G.: Solving bilevel programs with the KKT-approach. Math. Program. 138(1–2), 309–332 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  38. Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Berlin (2003)

    MATH  Google Scholar 

  39. Nabetani, K., Tseng, P., Fukushima, M.: Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints. Comput. Optim. Appl. 48(3), 423–452 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  40. Aussel, D., Sagratella, S.: Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality. Math. Methods Oper. Res. 85(1), 3–18 (2017)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The work of S. Sagratella has been partially supported by Avvio alla Ricerca 2015 Sapienza University of Rome, under Grant 488. The authors wish to thank one referee for his suggestions and comments that improved the quality of the paper.

Author information

Authors and Affiliations

  1. Department of Business Studies, Roma Tre University, Via D’Amico 77, 00145, Rome, Italy

    Lorenzo Lampariello

  2. Department of Computer, Control and Management Engineering Antonio Ruberti, Sapienza University of Rome, Via Ariosto 25, 00185, Rome, Italy

    Simone Sagratella

Authors
  1. Lorenzo Lampariello
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Simone Sagratella
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lorenzo Lampariello.

Additional information

Communicated by Negash G. Medhin.

Appendix

Appendix

Proof (Proposition 4.1)

Preliminarily, we show that

$$\begin{aligned} \displaystyle \bigcup _{b_1 \in B} \varPi _1^\mathrm{Vertical}(b_1) \ni \varPi _1^\mathrm{Vertical}. \end{aligned}$$
(34)

Let \((\widehat{q}^1, \widehat{q}^2)\) be a solution of the vertical model. With \(\widehat{b}_1 := a_1(\widehat{q}^1) \in B,\) we have \(S(\widehat{q}^1) = S_{\widehat{b}_1}\). Then, in turn, since \((\widehat{q}^1, \widehat{q}^2)\) is optimal for the parameterized vertical model with \(b_1 = \widehat{b}_1\), (34) holds.

In view of the previous result and since, by (33), \(\varPi _1^\mathrm{Uneven}(b_1) = \varPi _1^\mathrm{Vertical}(b_1)\), we also have

$$\begin{aligned} \displaystyle \bigcup _{b_1 \in B} \varPi _1^\mathrm{Uneven}(b_1) \ni \varPi _1^\mathrm{Vertical}. \end{aligned}$$
(35)

Thanks to [39, Theorem 3.6], \(\bigcup _{b_1 \in B} \varPi _1^\mathrm{Horizontal}(b_1) = \varPi _1^\mathrm{Horizontal}\), and, in turn,

$$\begin{aligned} \displaystyle \sup _{b_1 \in B} \max \{ \varPi _1^\mathrm{Horizontal}(b_1) \}= & {} \sup \left\{ \displaystyle \bigcup _{b_1 \in B} \max \left\{ \varPi _1^\mathrm{Horizontal}(b_1) \right\} \right\} \\= & {} \sup \left\{ \displaystyle \bigcup _{b_1 \in B} \varPi _1^\mathrm{Horizontal}(b_1) \right\} = \sup \left\{ \varPi _1^\mathrm{Horizontal} \right\} . \end{aligned}$$

Therefore, in view of (32) and (33),

$$\begin{aligned} \displaystyle \sup _{b_1 \in B} \varPi _1^\mathrm{Uneven}(b_1) \le \varPi _1^\mathrm{Vertical}, \end{aligned}$$

and the assertion follows by (35). \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lampariello, L., Sagratella, S. A Bridge Between Bilevel Programs and Nash Games. J Optim Theory Appl 174, 613–635 (2017). https://doi.org/10.1007/s10957-017-1109-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-017-1109-0

Keywords

Mathematics Subject Classification

Search

Navigation