zbMATH — the first resource for mathematics

Patience of matrix games. (English) Zbl 1285.91005
Summary: For matrix games we study how small nonzero probability must be used in optimal strategies. We show that for \(n\times n\) 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 \(n\times n\) 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 \(n\times n\) matrix, for which the inverse has only nonnegative entries and where some of the entries are of value \(n^{\Omega (n)}\).
91A05 2-person games
91A60 Probabilistic games; gambling
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
Full Text: DOI
[1] Alon, N.; Vũ, V. H., Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs, Journal of Combinatorial Theory, Series A, 79, 133-160, (1997) · Zbl 0890.05011
[2] Babai, L.; Hansen, K. A.; Podolskii, V. V.; Sun, X., Weights of exact threshold functions, (Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, Lecture Notes in Computer Science, vol. 6281, (2010), Springer), 66-77 · Zbl 1287.94129
[3] Ching, L., The maximum determinant of an \(n \times n\) lower Hessenberg \((0, 1)\) matrix, Linear Algebra and its Applications, 183, 147-153, (1993) · Zbl 0769.15008
[4] Everett, H., Recursive games, (Contributions to the Theory of Games Vol. III, Ann. Math. Studies, vol. 39, (1957), Princeton University Press), 67-78 · Zbl 0078.32802
[5] Faddeev, D. K.; Sominskii, I. S., Problems in higher algebra, (1965), W. H. Freeman, translated by J.L. Brenner · Zbl 0125.00702
[6] Ferguson, T. S., Game theory, (2011)
[7] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete mathematics: A foundation for computer science, (1994), Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA · Zbl 0836.00001
[8] Graham, R. L.; Sloane, N. J.A., Anti-Hadamard matrices, Linear Algebra and its Applications, 62, 113-137, (1984) · Zbl 0552.15010
[9] Hansen, K. A.; Ibsen-Jensen, R.; Miltersen, P. B., The complexity of solving reachability games using value and strategy iteration, (6th Int. Comp. Sci. Symp. in Russia, CSR, LNCS, (2011), Springer), 77-90 · Zbl 1330.68112
[10] Hansen, K. A.; Koucký, M.; Lauritzen, N.; Miltersen, P. B.; Tsigaridas, E. P., Exact algorithms for solving stochastic games: extended abstract, (Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, (2011), ACM), 205-214 · Zbl 1288.68120
[11] K.A. Hansen, M. Koucký, P.B. Miltersen, Winning concurrent reachability games requires doubly exponential patience, in: Proc. of IEEE Symp. on Logic in Comp. Sci., LICS, pp. 332-341.
[12] Håstad, J., On the size of weights for threshold gates, SIAM Journal on Discrete Mathematics, 7, 484-492, (1994) · Zbl 0811.68100
[13] Johnson, D. S.; Papadimitriou, C. H.; Yannakakis, M., How easy is local search?, Journal of Computer and System Sciences, 37, 79-100, (1988) · Zbl 0655.68074
[14] Krentel, M. W., Structure in locally optimal solutions (extended abstract), (30th Annual Symposium on Foundations of Computer Science, FOCS’89, (1989), IEEE Computer Society), 216-221
[15] Lipton, R. J.; Young, N. E., Simple strategies for large zero-sum games with applications to complexity theory, (Proceedings of the 26th Annual Symposium on the Theory of Computing, (1994), ACM Press), 734-740 · Zbl 1345.68175
[16] McCormick, S. T.; Rao, M.; Rinaldi, G., Easy and difficult objective functions for MAX cut, Mathematical Programming, 94, 459-466, (2003) · Zbl 1030.90130
[17] Podolskii, V. V., Perceptrons of large weight, Problems of Information Transmission, 45, 46-53, (2009) · Zbl 1171.68585
[18] Roth, R. M.; Viswanathan, K., On the hardness of decoding the gale-berlekamp code, IEEE Transactions on Information Theory, 54, 1050-1060, (2008) · Zbl 1311.94121
[19] Schäffer, A. A.; Yannakakis, M., Simple local search problems that are hard to solve, SIAM Journal on Computing, 20, 56-87, (1991) · Zbl 0716.68048
[20] Shapley, L. S.; Snow, R. N., Basic solutions of discrete games, (Contributions to the Theory of Games, Annals of Mathematics Studies, vol. 24, (1950), Princeton University Press), 27-35 · Zbl 0041.25403
[21] Sloane, N. J.A., Unsolved problems related to the covering radius of codes, (Cover, T. M.; Gopinath, B., Open Problems in Communication and Computation, (1987), Springer-Verlag), 51-56
[22] Spencer, J., Ten lectures on the probabilistic method, (1987), SIAM · Zbl 0703.05046
[23] von Neumann, J., Zur theorie der gesellschaftsspiele, Mathematische Annalen, 100, 295-320, (1928) · JFM 54.0543.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.