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

DOI10.1007/S13235-018-0283-5MaRDI QIDQ2292111zbMATH OpenOpenAlexFDO

Authors Cédric Langbort, Lichun 'Lucinda' Li

Publication date 3 February 2020

Published in Dynamic Games and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.02303

zbMATH Keywords

game theoryshadow vertex methoditerative computationgrowing action set

Mathematics Subject Classification ID

Noncooperative games (91A10) 2-person games (91A05) Algorithmic game theory and complexity (91A68)

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 solve the new LP with a new constraint efficiently. Considering the potentially huge number of constraints, which corresponds to the large size of the other player's action set, we use 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 shadow vertex method with relaxed assumption to make sure such method works well in our model, then analyze the probability that the old optimum remains optimal in the new LP, and finally provides the iterative shadow vertex method whose computational complexity is shown to be strictly less than that of shadow vertex method. The simulation results demonstrates our main results about the probability of re-computing the optimum and the computational complexity of the iterative shadow vertex method.

Recommendations

• On incremental approximate saddle-point computation in zero-sum matrix games
• Iteration in a subspace for solving matrix games
• On the characterization of saddle point equilibrium for security games with additive utility
• scientific article; zbMATH DE number 961683
• Randomized sampling for large zero-sum games

Cites work

• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3483788 (Why is no real title available?)
• scientific article; zbMATH DE number 706270 (Why is no real title available?)
• A dynamic near-optimal algorithm for online linear programming
• A multiple-choice secretary algorithm with applications to online auctions
• On incremental approximate saddle-point computation in zero-sum matrix games
• Online stochastic packing applied to display ad allocation
• Smoothed analysis of algorithms
• Some results in probabilistic geometry
• The Average number of pivot steps required by the Simplex-Method is polynomial
• The simplex method. A probabilistic analysis

Cited in

(3)

• On incremental approximate saddle-point computation in zero-sum matrix games
• Pareto-optimal security strategies as minimax strategies of a standard matrix game
• Convergence analysis of iterated best response for a trusted computation game

This page was built for publication: Iterative computation of security strategies of matrix games with growing action set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292111)