Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010192415 | QA269 B33 2008 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Traditional game theory has been successful at developing strategy in games of incomplete information: when one player knows something that the other does not. But it has little to say about games of complete information, for example, tic-tac-toe, solitaire and hex. The main challenge of combinatorial game theory is to handle combinatorial chaos, where brute force study is impractical. In this comprehensive volume, József Beck shows readers how to escape from the combinatorial chaos via the fake probabilistic method, a game-theoretic adaptation of the probabilistic method in combinatorics. Using this, the author is able to determine the exact results about infinite classes of many games, leading to the discovery of some striking new duality principles. Available for the first time in paperback, it includes a new appendix to address the results that have appeared since the book's original publication.
Reviews 1
Choice Review
This is an excellent, extensive, and readable review of combinatorial game theory. In an enjoyable introductory chapter, Beck (Rutgers Univ.) very clearly explains what he will and will not do in the book. He distinguishes three kinds of games, and devotes the work to one type, games of complete information that do not fall apart into simple subgames during play. Well-known games of this kind include chess, checkers, and tic-tac-toe. (The other two kinds of games, i.e., games of incomplete information, like poker, and games of complete information that do fall apart into simple subgames, like Nim, are discussed in an equally enjoyable appendix). In the main part of the book, the author introduces the concept of weak win and strong draw, explains game-theoretic first, second, and higher moments, and game-theoretic independence. The monograph, though not a textbook, was written with classroom instruction in mind, so there are many places when the author indicates that the student should figure out the next step before reading further. The book, which is very hard to put down, ends with an extremely helpful dictionary and list of open problems. Summing Up: Essential. Upper-division undergraduates through researchers/faculty. M. Bona University of Florida
Table of Contents
| Preface |
| A summary of the book in a nutshell |
| Part A Weak Win and Strong Draw |
| 1 Win vs. weak win |
| 2 The main result: exact solutions for infinite classes of games |
| Part B Basic Potential Technique - Game-Theoretic First and Second Moments |
| 3 Simple applications |
| 4 Games and randomness |
| Part C Advanced Weak Win - Game-theoretic Higher Moment |
| 5 Self-improving potentials |
| 6 What is the biased meta-conjecture, and why is it so difficult? |
| Part D Advanced Strong Draw - Game-theoretic Independence |
| 7 BigGame-SmallGame decomposition |
| 8 Advanced decomposition |
| 9 Game-theoretic lattice-numbers |
| 10 Conclusion |
| Complete list of open problems |
| What kind of games? A dictionary |
| Dictionary of the phrases and concepts |
| Appendix A Ramsey numbers |
| Appendix B Hales-Jewett theorem: Shelah's proof |
| Appendix C A formal treatment of positional games |
| Appendix D An informal introduction to game theory |
| References |
