Patience of matrix games

DOI10.1016/j.dam.2013.05.008zbMath1285.91005arXiv1206.1751MaRDI QIDQ2444536

Vladimir V. Podolskii, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, 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 matrices; matrix games; nonnegative inverse

Mathematics Subject Classification ID

91A05: 2-person games

05B20: Combinatorial aspects of matrices (incidence, Hadamard, etc.)

91A60: Probabilistic games; gambling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Perceptrons of large weight
• Anti-Hadamard matrices
• How easy is local search?
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Easy and difficult objective functions for max cut
• The complexity of solving reachability games using value and strategy iteration
• The maximum determinant of an \(n\times{}n\) lower Hessenberg (0,1) matrix
• Simple strategies for large zero-sum games with applications to complexity theory
• Simple Local Search Problems that are Hard to Solve
• Weights of Exact Threshold Functions
• On the Hardness of Decoding the Gale–Berlekamp Code
• On the Size of Weights for Threshold Gates
• Exact algorithms for solving stochastic games