Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Dynamic Games and Applications 4/2019

08-09-2018

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

Authors: Lichun Li, Cedric Langbort

Published in: Dynamic Games and Applications | Issue 4/2019

Login to get access
share
SHARE

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.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Appendix
Available only for authorised users
Literature
1.
go back to reference Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper Res 62(4):876–890 MathSciNetCrossRef Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper Res 62(4):876–890 MathSciNetCrossRef
2.
go back to reference Başar T, Olsder GJ (1998) Dynamic noncooperative game theory. SIAM Başar T, Olsder GJ (1998) Dynamic noncooperative game theory. SIAM
3.
go back to reference Bopardikar SD, Langbort C (2016) On incremental approximate saddle-point computation in zero-sum matrix games. Automatica 69:150–156 MathSciNetCrossRef Bopardikar SD, Langbort C (2016) On incremental approximate saddle-point computation in zero-sum matrix games. Automatica 69:150–156 MathSciNetCrossRef
4.
go back to reference Borgwardt KH (1982) The average number of pivot steps required by the simplex-method is polynomial. Math Methods Oper Res 26(1):157–177 MathSciNetCrossRef Borgwardt KH (1982) The average number of pivot steps required by the simplex-method is polynomial. Math Methods Oper Res 26(1):157–177 MathSciNetCrossRef
5.
go back to reference Borgwardt KH (2012) The simplex method: a probabilistic analysis, vol 1. Springer, Berlin MATH Borgwardt KH (2012) The simplex method: a probabilistic analysis, vol 1. Springer, Berlin MATH
6.
go back to reference Dantzig G (2016) Linear programming and extensions. Princeton University Press, Princeton Dantzig G (2016) Linear programming and extensions. Princeton University Press, Princeton
7.
go back to reference Devanur NR, Hayes TP (2009) The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Proceedings of the 10th ACM conference on electronic commerce. ACM, pp 71–78 Devanur NR, Hayes TP (2009) The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Proceedings of the 10th ACM conference on electronic commerce. ACM, pp 71–78
9.
go back to reference Feldman J, Henzinger M, Korula N, Mirrokni V, Stein C (2010) Online stochastic packing applied to display ad allocation. In: European symposium on algorithms. Springer, 2010, pp 182–194 Feldman J, Henzinger M, Korula N, Mirrokni V, Stein C (2010) Online stochastic packing applied to display ad allocation. In: European symposium on algorithms. Springer, 2010, pp 182–194
11.
go back to reference Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp 630–631 Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp 630–631
12.
go back to reference Liebling TM, Henn R, Künzi H, Schubert H (1972) On the number of iterations of the simplex method. Methods Oper Res 2(ROSO–CONF–1972–001):248–264 Liebling TM, Henn R, Künzi H, Schubert H (1972) On the number of iterations of the simplex method. Methods Oper Res 2(ROSO–CONF–1972–001):248–264
13.
go back to reference Lindberg PO (1981) A note on random LP-problems. Department of Mathematics, Royal Institute of Technology, Stockholm Lindberg PO (1981) A note on random LP-problems. Department of Mathematics, Royal Institute of Technology, Stockholm
15.
go back to reference Schmidt WM (1968) Some results in probabilistic geometry. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 9(2):158–162 MathSciNetCrossRef Schmidt WM (1968) Some results in probabilistic geometry. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 9(2):158–162 MathSciNetCrossRef
16.
go back to reference Spielman DA, Teng SH (2004) Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J ACM: JACM 51(3):385–463 MathSciNetCrossRef Spielman DA, Teng SH (2004) Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J ACM: JACM 51(3):385–463 MathSciNetCrossRef
17.
go back to reference Tsai J, Yin Z, Kwak Jy, Kempe D, Kiekintveld C, Tambe M (2010) Urban security: game-theoretic resource allocation in networked physical domains. In: National conference on artificial intelligence (AAAI) Tsai J, Yin Z, Kwak Jy, Kempe D, Kiekintveld C, Tambe M (2010) Urban security: game-theoretic resource allocation in networked physical domains. In: National conference on artificial intelligence (AAAI)
Metadata
Title
Iterative Computation of Security Strategies of Matrix Games with Growing Action Set
Authors
Lichun Li
Cedric Langbort
Publication date
08-09-2018
Publisher
Springer US
Published in
Dynamic Games and Applications / Issue 4/2019
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-018-0283-5

Other articles of this Issue 4/2019

Dynamic Games and Applications 4/2019 Go to the issue

Premium Partner