Iterative Computation of Security Strategies of Matrix Games with Growing Action Set

Lichun Li () and Cedric Langbort ()
Additional contact information
Lichun Li: FAMU-FSU College of engineering
Cedric Langbort: University of Illinois at Urbana-Champaign

Dynamic Games and Applications, 2019, vol. 9, issue 4, No 4, 942-964

Abstract: Abstract This paper studies how to efficiently update the saddle-point strategy, or security strategy of one player in a matrix game when the other player develops new actions in the game. It is well known that the saddle-point strategy of one player can be computed by solving a linear program. Developing a new action will add a new constraint to the existing LP. Therefore, our problem becomes how to efficiently solve the new LP with a new constraint. Considering the potentially huge number of constraints, which corresponds to the large size of the other player’s action set, we use the shadow vertex simplex method, whose computational complexity is lower than linear with respect to the size of the constraints, as the basis of our iterative algorithm. We first rebuild the main theorems in the shadow vertex method with a relaxed non-degeneracy assumption to make sure such a method works well in our model, then analyze the probability that the old optimum remains optimal in the new LP, and finally provide the iterative shadow vertex method whose average computational complexity is shown to be strictly less than that of the shadow vertex method. The simulation results demonstrate our main results about the probability of re-computing the optimum and the computational complexity of the iterative shadow vertex method.

Keywords: Game theory; Growing action set; Iterative computation; Shadow vertex method (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13235-018-0283-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:9:y:2019:i:4:d:10.1007_s13235-018-0283-5

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-018-0283-5

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().