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

DOI10.1007/S13235-018-0283-5zbMATH Open1431.91010arXiv1711.02303OpenAlexW3028526625MaRDI QIDQ2292111FDOQ2292111

Authors: Cédric Langbort, Lichun 'Lucinda' Li 

Publication date: 3 February 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On incremental approximate saddle-point computation in zero-sum matrix games
• A multiple-choice secretary algorithm with applications to online auctions
• A Dynamic Near-Optimal Algorithm for Online Linear Programming
• Online stochastic packing applied to display ad allocation
• Smoothed analysis of algorithms
• Geometry of Online Packing Linear Programs
• The simplex method. A probabilistic analysis
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Title not available (Why is that?)
• Some results in probabilistic geometry

Cited In (1)

• Pareto-optimal security strategies as minimax strategies of a standard matrix 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)