Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games

The concept of leader-follower (or Stackelberg) equilibrium plays a central role in a number of real-world applications bordering on mathematical optimization and game theory. While the single-follower case has been investigated since the inception of bilevel programming with the seminal work of von...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Nicola Basilico, Stefano Coniglio, Nicola Gatti, Alberto Marchesi
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2020
Materias:	91A10 91A65 91A90 90C26 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/9a8ae5364eaf478ba261674b4a89e202
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:9a8ae5364eaf478ba261674b4a89e202
record_format	dspace
spelling	oai:doaj.org-article:9a8ae5364eaf478ba261674b4a89e2022021-12-02T05:00:33ZBilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games2192-440610.1007/s13675-019-00114-8https://doaj.org/article/9a8ae5364eaf478ba261674b4a89e2022020-03-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000058https://doaj.org/toc/2192-4406The concept of leader-follower (or Stackelberg) equilibrium plays a central role in a number of real-world applications bordering on mathematical optimization and game theory. While the single-follower case has been investigated since the inception of bilevel programming with the seminal work of von Stackelberg, results for the case with multiple followers are only sporadic and not many computationally affordable methods are available. In this work, we consider Stackelberg games with two or more followers who play a (pure or mixed) Nash equilibrium once the leader has committed to a (pure or mixed) strategy, focusing on normal-form and polymatrix games. As customary in bilevel programming, we address the two extreme cases where, if the leader’s commitment originates more Nash equilibria in the followers’ game, one which either maximizes (optimistic case) or minimizes (pessimistic case) the leader’s utility is selected. First, we show that, in both cases and when assuming mixed strategies, the optimization problem associated with the search problem of finding a Stackelberg equilibrium is NP-hard and not in Poly-APX unless P=NP. We then consider different situations based on whether the leader or the followers can play mixed strategies or are restricted to pure strategies only, proposing exact nonconvex mathematical programming formulations for the optimistic case for normal-form and polymatrix games. For the pessimistic problem, which cannot be tackled with a (single-level) mathematical programming formulation, we propose a heuristic black-box algorithm. All the methods and formulations that we propose are thoroughly evaluated computationally.Nicola BasilicoStefano ConiglioNicola GattiAlberto MarchesiElsevierarticle91A1091A6591A9090C26Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 8, Iss 1, Pp 3-31 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	91A10 91A65 91A90 90C26 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	91A10 91A65 91A90 90C26 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Nicola Basilico Stefano Coniglio Nicola Gatti Alberto Marchesi Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
description	The concept of leader-follower (or Stackelberg) equilibrium plays a central role in a number of real-world applications bordering on mathematical optimization and game theory. While the single-follower case has been investigated since the inception of bilevel programming with the seminal work of von Stackelberg, results for the case with multiple followers are only sporadic and not many computationally affordable methods are available. In this work, we consider Stackelberg games with two or more followers who play a (pure or mixed) Nash equilibrium once the leader has committed to a (pure or mixed) strategy, focusing on normal-form and polymatrix games. As customary in bilevel programming, we address the two extreme cases where, if the leader’s commitment originates more Nash equilibria in the followers’ game, one which either maximizes (optimistic case) or minimizes (pessimistic case) the leader’s utility is selected. First, we show that, in both cases and when assuming mixed strategies, the optimization problem associated with the search problem of finding a Stackelberg equilibrium is NP-hard and not in Poly-APX unless P=NP. We then consider different situations based on whether the leader or the followers can play mixed strategies or are restricted to pure strategies only, proposing exact nonconvex mathematical programming formulations for the optimistic case for normal-form and polymatrix games. For the pessimistic problem, which cannot be tackled with a (single-level) mathematical programming formulation, we propose a heuristic black-box algorithm. All the methods and formulations that we propose are thoroughly evaluated computationally.
format	article
author	Nicola Basilico Stefano Coniglio Nicola Gatti Alberto Marchesi
author_facet	Nicola Basilico Stefano Coniglio Nicola Gatti Alberto Marchesi
author_sort	Nicola Basilico
title	Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
title_short	Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
title_full	Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
title_fullStr	Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
title_full_unstemmed	Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
title_sort	bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games
publisher	Elsevier
publishDate	2020
url	https://doaj.org/article/9a8ae5364eaf478ba261674b4a89e202
work_keys_str_mv	AT nicolabasilico bilevelprogrammingmethodsforcomputingsingleleadermultifollowerequilibriainnormalformandpolymatrixgames AT stefanoconiglio bilevelprogrammingmethodsforcomputingsingleleadermultifollowerequilibriainnormalformandpolymatrixgames AT nicolagatti bilevelprogrammingmethodsforcomputingsingleleadermultifollowerequilibriainnormalformandpolymatrixgames AT albertomarchesi bilevelprogrammingmethodsforcomputingsingleleadermultifollowerequilibriainnormalformandpolymatrixgames
_version_	1718400843111202816

Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games

Ejemplares similares