On sparse approximations to randomized strategies and convex combinations

DOI10.1016/0024-3795(94)90357-3zbMath0801.90074OpenAlexW2032716871MaRDI QIDQ1322876

Ingo Althöfer

Publication date: 9 May 1994

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(94)90357-3

zbMATH Keywords

computer chessmatrix gamesapproximation lemmauniform sampling spaces

Mathematics Subject Classification ID

Linear programming (90C05) 2-person games (91A05)

Related Items

New Limits to Classical and Quantum Instance Compression, A Selective Tour Through Congestion Games, Computing sparse approximations deterministically, Resolving Braess's paradox in random networks, Random bimatrix games are asymptotically easy to solve (a simple proof), On the hardness of network design for bottleneck routing games, Complexity limitations on one-turn quantum refereed games, On mutual concavity and strategically-zero-sum bimatrix games, Efficient methods for selfish network design, Empirical Distribution of Equilibrium Play and Its Testing Application, Arthur and Merlin as oracles, Selfish splittable flows and NP-completeness, Minimal zero norm solutions of linear complementarity problems, Well supported approximate equilibria in bimatrix games, Arthur and Merlin as Oracles, Inapproximability results for constrained approximate Nash equilibria, Approximating the existential theory of the reals, Approximate Equilibria for Strategic Two Person Games, Approximating the existential theory of the reals, A note on approximate Nash equilibria, Polynomial algorithms for approximating Nash equilibria of bimatrix games, Uniformly supported approximate equilibria in families of games, New algorithms for approximate Nash equilibria in bimatrix games, Escaping Braess's paradox through approximate Caratheodory's theorem, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria, On sparse approximations to randomized strategies and convex combinations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discrepancy of set-systems and matrices
• \(\epsilon\)-nets and simplex range queries
• ``Integer-making theorems
• On sparse approximations to randomized strategies and convex combinations
• On deterministic approximation of DNF
• Monte-Carlo approximation algorithms for enumeration problems
• Elimination of correlation in random codes for arbitrarily varying channels
• Probability Inequalities for Sums of Bounded Random Variables
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Elimination of Randomization in Certain Statistical Decision Procedures and Zero-Sum Two-Person Games
• Two methods of randomization in statistics and the theory of games