Document Open Access Logo

Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria

Authors Nicola Basilico, Stefano Coniglio, Nicola Gatti, Alberto Marchesi

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.31.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Nicola Basilico
Stefano Coniglio
Nicola Gatti
Alberto Marchesi

Cite As Get BibTex

Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.31

Abstract

We study the problem of computing an equilibrium in leader-follower games with a single leader and multiple followers where, after the leader’s commitment to a mixed strategy, the followers play simultaneously in a noncooperative way, reaching a Nash equilibrium. We tackle the problem from a bilevel programming perspective. Since, given the leader’s strategy, the followers’ subgame may admit multiple Nash equilibria, we consider the cases where the followers play either the best (optimistic) or the worst (pessimistic) Nash equilibrium in terms of the leader’s utility. For the optimistic case, we propose three formulations which cast the problem into a single level mixed-integer nonconvex program. For the pessimistic case, which, as we show, may admit a supremum but not a maximum, we develop an ad hoc branch-and-bound algorithm. Computational results are reported and illustrated.

Subject Classification

Keywords
  • Stackelberg games; Nash equilibria; Game theory; Bilevel and nonlinear programming; Branch-and-bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. E. Amaldi, A. Capone, S. Coniglio, and L. G. Gianoli. Network optimization problems subject to max-min fair flow allocation. IEEE COMMUN LETT, 17(7):1463-1466, 2013. Google Scholar
  2. B. An, J. Pita, E. Shieh, M. Tambe, C. Kiekintveld, and J. Marecki. Guards and Protect: Next generation applications of security games. ACM SIGecom Exchanges, 10(1):31-34, 2011. Google Scholar
  3. E. Balas. Disjunctive programming: Properties of the convex hull of feasible points. DISCRETE APPL MATH, 89(1):3-44, 1998. Google Scholar
  4. N. Basilico, S. Coniglio, and N. Gatti. Methods for Finding Leader-Follower Equilibria with Multiple Followers: (Extended Abstract). In Proc. of AAMAS, pages 1363-1364. International Foundation for Autonomous Agents and Multiagent Systems, 2016. Google Scholar
  5. A. Caprara, M. Carvalho, A. Lodi, and G.J. Woeginger. Bilevel knapsack with interdiction constraints. INFORMS J COMPUT, 28(2):319-333, 2016. Google Scholar
  6. V. Conitzer and D. Korzhyk. Commitment to correlated strategies. In Proc. of AAAI, 2011. Google Scholar
  7. V. Conitzer and T. Sandholm. Computing the optimal strategy to commit to. In ACM EC, pages 82-90, 2006. Google Scholar
  8. V. Conitzer and T. Sandholm. New complexity results about nash equilibria. GAME ECON BEHAV, 63(2):621-641, 2008. Google Scholar
  9. C. Kiekintveld, M. Jain, J. Tsai, J. Pita, F. Ordóñez, and M. Tambe. Computing optimal randomized resource allocations for massive security games. In Proc. of AAMAS, pages 689-696, 2009. Google Scholar
  10. M. Labbé and A. Violin. Bilevel programming and price setting problems. ANN OPER RES, 240(1):141-169, 2016. Google Scholar
  11. S. Leyffer and T. Munson. Solving multi-leader-common-follower games. OPTIM METHOD SOFTW, 25(4):601-623, 2010. Google Scholar
  12. Z.-Q. Luo, J.-S. Pang, and D. Ralph. Mathematical programs with equilibrium constraints. Cambridge University Press, 1996. Google Scholar
  13. J. Matuschke, S.T. McCormick, G. Oriolo, B. Peis, and M. Skutella. Protection of flows under targeted attacks. OPER RES LETT, 45(1):53-59, 2017. Google Scholar
  14. E. Nudelman, J. Wortman, Y. Shoham, and K. Leyton-Brown. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In Proc. of AAMAS, pages 880-887. IEEE Computer Society, 2004. Google Scholar
  15. T. Sandholm, A. Gilpin, and V. Conitzer. Mixed-Integer Programming Methods for Finding Nash Equilibria. In Proc. of AAAI, pages 495-501, 2005. Google Scholar
  16. Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundations. Cambridge University Press, 2008. Google Scholar
  17. B. von Stengel and S. Zamir. Leadership games with convex strategy sets. GAME ECON BEHAV, 69:446-457, 2010. Google Scholar
  18. A.B. Zemkoho. Solving ill-posed bilevel programs. SET-VALUED ANAL, 24(3):423-448, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact