Patience of matrix games

DOI10.1016/J.DAM.2013.05.008MaRDI QIDQ2444536zbMATH OpenOpenAlexFDO

Authors Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Vladimir V. Podolskii, Elias P. Tsigaridas

Publication date 10 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

ill-conditioned matricesmatrix gamesnonnegative inverse

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) 2-person games (91A05) Probabilistic games; gambling (91A60)

Abstract: For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for nxn win-lose-draw games (i.e. (-1,0,1) matrix games) nonzero probabilities smaller than n^{-O(n)} are never needed. We also construct an explicit nxn win-lose game such that the unique optimal strategy uses a nonzero probability as small as n^{-Omega(n)}. This is done by constructing an explicit (-1,1) nonsingular nxn matrix, for which the inverse has only nonnegative entries and where some of the entries are of value n^{Omega(n)}.

Recommendations

• scientific article; zbMATH DE number 148968
• Algebraic solutions for matrix games
• On the optimal strategy in a random game
• scientific article; zbMATH DE number 165563
• On the prabability of existence of pure equilibria in matrix games

Cites work

• Anti-Hadamard matrices
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Easy and difficult objective functions for max cut
• Exact algorithms for solving stochastic games
• How easy is local search?
• scientific article; zbMATH DE number 3128726 (Why is no real title available?)
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 3202585 (Why is no real title available?)
• scientific article; zbMATH DE number 3062449 (Why is no real title available?)
• On the Hardness of Decoding the Gale–Berlekamp Code
• On the Size of Weights for Threshold Gates
• Perceptrons of large weight
• Simple Local Search Problems that are Hard to Solve
• Simple strategies for large zero-sum games with applications to complexity theory
• The maximum determinant of an \(n\times{}n\) lower Hessenberg (0,1) matrix
• Weights of exact threshold functions

Cited in

(3)

• Multi-player matrix games
• Pfaffians and strategies for integer choice games
• Tricks on a multi-stage matrix game

This page was built for publication: Patience of matrix games

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