Strategy investments in zero-sum games

被引：0

作者：

Garcia, Raul ^{[1
]}

Hosseinian, Seyedmohammadhossein ^{[2
]}

Pai, Mallesh ^{[3
]}

Schaefer, Andrew J. ^{[1
]}

机构：

[1] Rice Univ, Dept Computat Appl Math & Operat Res, Houston, TX 77005 USA

[2] Univ Cincinnati, Dept Mech & Mat Engn, Cincinnati, OH 45221 USA

[3] Rice Univ, Dept Econ, Houston, TX 77005 USA

来源：

OPTIMIZATION LETTERS | 2024年 / 18卷 / 08期

基金：

美国国家卫生研究院;

关键词：

Zero-sum games; Matrix games; Strategy investments; Mixed-integer linear programming;

D O I：

10.1007/s11590-024-02130-z

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We propose an extension of two-player zero-sum games, where one player may select available actions for themselves and the opponent, subject to a budget constraint. We present a mixed-integer linear programming (MILP) formulation for the problem, provide analytical results regarding its solution, and discuss applications in the security and advertising domains. Our computational experiments demonstrate that heuristic approaches, on average, yield suboptimal solutions with at least a 20% relative gap with those obtained by the MILP formulation.

引用

页码：1771 / 1789

页数：19

共 50 条

[31] Turnpike Theory for Dynamic Zero-Sum Games
Zaslavski, Alexander J.
VARIATIONAL AND OPTIMAL CONTROL PROBLEMS ON UNBOUNDED DOMAIN, 2014, 619 : 225 - 247
[32] The equivalence of linear programs and zero-sum games
Adler, Ilan
INTERNATIONAL JOURNAL OF GAME THEORY, 2013, 42 (01) : 165 - 177
[33] Zero-Sum Polymatrix Games: A Generalization of Minmax
Cai, Yang
Candogan, Ozan
Daskalakis, Constantinos
Papadimitriou, Christos
MATHEMATICS OF OPERATIONS RESEARCH, 2016, 41 (02) : 648 - 655
[34] Zero-sum Stochastic Games with Asymmetric Information
Kartik, Dhruva
Nayyar, Ashutosh
2019 IEEE 58TH CONFERENCE ON DECISION AND CONTROL (CDC), 2019, : 4061 - 4066
[35] Non-Archimedean zero-sum games
Cococcioni, Marco
Fiaschi, Lorenzo
Lambertini, Luca
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2021, 393
[36] Pure strategy equilibria in symmetric two-player zero-sum games
Peter Duersch
Jörg Oechssler
Burkhard C. Schipper
International Journal of Game Theory, 2012, 41 : 553 - 564
[37] The Design of ϵ-Optimal Strategy for Two-Person Zero-Sum Markov Games
Xie, Kaiyun
Xiong, Junlin
IEEE CONTROL SYSTEMS LETTERS, 2024, 8 : 2349 - 2354
[38] Randomized sampling for large zero-sum games
Bopardikar, Shaunak D.
Borri, Alessandro
Hespanha, Joao P.
Prandini, Maria
Di Benedetto, Maria D.
AUTOMATICA, 2013, 49 (05) : 1184 - 1194
[39] The Attractor of the Replicator Dynamic in Zero-Sum Games
Biggar, Oliver
Shames, Iman
INTERNATIONAL CONFERENCE ON ALGORITHMIC LEARNING THEORY, VOL 237, 2024, 237
[40] Evolving interpretable strategies for zero-sum games
Marino, Julian R. H.
Toledo, Claudio F. M.
APPLIED SOFT COMPUTING, 2022, 122

← 1 2 3 4 5 →