Loading...
Please wait, while we are loading the content...
Similar Documents
Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory (1994)
| Content Provider | CiteSeerX |
|---|---|
| Author | Lipton, Richard J. Young, Neal E. |
| Description | Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses uniformly from a multiset of pure strategies of size logarithmic in the number of pure strategies available to the opponent. Thus, for exponentially large games, for which even representing an optimal mixed strategy can require exponential space, there are nearoptimal, linear-size strategies. These strategies are easy to play and serve as small witnesses to the approximate value of the game. |
| File Format | |
| Language | English |
| Publisher Date | 1994-01-01 |
| Publisher Institution | In Proc. of the 26th Ann. ACM Symp. on Theory of Computing |
| Access Restriction | Open |
| Subject Keyword | Size Logarithmic Optimal Mixed Strategy Small Witness Approximate Value Near-optimal Mixed Strategy Simple Strategy Exponential Space Pure Strategy Linear-size Strategy Complexity Theory Large Game Min-max Theorem Guarantee Large Zero-sum Game Von Neumann Zero-sum Matrix Game |
| Content Type | Text |
| Resource Type | Article |
