Dinkelbach-type algorithm for computing quantal stackelberg equilibrium
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00345735" target="_blank" >RIV/68407700:21230/20:00345735 - isvavai.cz</a>
Result on the web
<a href="https://www.ijcai.org/Proceedings/2020/0035.pdf" target="_blank" >https://www.ijcai.org/Proceedings/2020/0035.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Dinkelbach-type algorithm for computing quantal stackelberg equilibrium
Original language description
Stackelberg security games (SSGs) have been deployed in many real-world situations to optimally allocate scarce resource to protect targets against attackers. However, actual human attackers are not perfectly rational and there are several behavior models that attempt to predict subrational behavior. Quantal response is among the most commonly used such models and Quantal Stackelberg Equilibrium (QSE) describes the optimal strategy to commit to when facing a subrational opponent. Non-concavity makes computing QSE computationally challenging and while there exist algorithms for computing QSE for SSGs, they cannot be directly used for solving an arbitrary game in the normal form. We (1) present a transformation of the primal problem for computing QSE using a Dinkelbach's method for any general-sum normal-form game, (2) provide a gradient-based and a MILP-based algorithm, give the convergence criteria, and bound their error, and finally (3) we experimentally demonstrate that using our novel transformation, a QSE can be closely approximated several orders of magnitude faster.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
ISBN
978-0-9992411-6-5
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
246-253
Publisher name
International Joint Conferences on Artificial Intelligence Organization
Place of publication
—
Event location
Yokohama
Event date
Jul 11, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—