License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.31
URN: urn:nbn:de:0030-drops-76249
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7624/
Go to the corresponding LIPIcs Volume Portal


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

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

pdf-format:
LIPIcs-SEA-2017-31.pdf (0.5 MB)


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.

BibTeX - Entry

@InProceedings{basilico_et_al:LIPIcs:2017:7624,
  author =	{Nicola Basilico and Stefano Coniglio and Nicola Gatti and Alberto Marchesi},
  title =	{{Bilevel Programming Approaches to the Computation of Optimistic and Pessimistic Single-Leader-Multi-Follower Equilibria}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7624},
  URN =		{urn:nbn:de:0030-drops-76249},
  doi =		{10.4230/LIPIcs.SEA.2017.31},
  annote =	{Keywords: Stackelberg games; Nash equilibria; Game theory; Bilevel and nonlinear programming; Branch-and-bound}
}

Keywords: Stackelberg games; Nash equilibria; Game theory; Bilevel and nonlinear programming; Branch-and-bound
Seminar: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 03.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI