Iterative computation of security strategies in matrix games with growing action set

Lichun Li, Cedric Langbort

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper considers a multi-stage matrix game in which one player (minimizer) generates a new action at every stage. Our objective is to find a computationally efficient way to compute the responding strategy of the other player (maximizer) to achieve the maxmin value of the matrix game at the current stage. Since the maxmin problem can be transformed to an LP problem, shadow vertex simplex method is considered. Noticing that our LP model violates the non-degeneracy assumption in shadow vertex method, we make a relaxed non-degeneracy assumption, prove that the necessary and sufficient condition of a shadow vertex still holds with the relaxed non-degeneracy assumption, and hence assure that shadow vertex method is still an efficient method in our case. Based on these result, the iterative shadow vertex method is presented. Instead of starting the search from the original shadow vertex, the iterative shadow vertex method starts the search from the previously visited feasible shadow vertex with the largest objective value. Our simulation results demonstrate the iterative shadow vertex method has much fewer average pivot steps compared with the regular shadow vertex method.

Original languageEnglish (US)
Title of host publication2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages6205-6210
Number of pages6
ISBN (Electronic)9781509028733
DOIs
StatePublished - Jan 18 2018
Event56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia
Duration: Dec 12 2017Dec 15 2017

Publication series

Name2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
Volume2018-January

Other

Other56th IEEE Annual Conference on Decision and Control, CDC 2017
CountryAustralia
CityMelbourne
Period12/12/1712/15/17

ASJC Scopus subject areas

  • Decision Sciences (miscellaneous)
  • Industrial and Manufacturing Engineering
  • Control and Optimization

Fingerprint Dive into the research topics of 'Iterative computation of security strategies in matrix games with growing action set'. Together they form a unique fingerprint.

Cite this