Game-Theoretic Variance

点击翻译按钮获取中文摘要

The investigator outlines how to continue his work started in the prior proposal to develop a new, probabilistic approach to positional games (i.e. combinatorial board games). The straightforward way to analyze a position is to examine all of its options and all the options of these options and all the options of the options of these options and so on. The obvious difficulty of this exhaustive search through the game-tree is that it takes enormous amount of time. An attempt to make up for the lack of time is to study the random walk on the game-tree, i.e. the randomized game where both players play randomly. The basic idea is that the statistical analysis of the randomized game can be efficiently converted via potential arguments into deterministic optimal strategies. It is basically a game-theoretic adaptation of the so-called Probabilistic Method in Combinatorics ("Erdos theory") applied to hopelessly complicated games where the exact methods fail to work. It is very surprising how this ``desperate'' attempt turns out to be successful for large, interesting classes of positional games. Carrying out the program sketched in his prior proposal the investigator have developed a "game theoretic second moment method" for fair games, and applied it to solve long-standing open problems in graph and hypergraph games. Another great success was his work toward "game-theoretic independence" (i.e. game theoretic Lovasz Local Lemma). In this direction the investigator achieved an important partial result, which led to the solution of the long-standing Hales-Jewett conjecture about the multi-dimensional Tic-Tac-Toe game. In this new proposal the investigator aims for a biased generalization of his game-theoretic second moment method, which would create a breakthrough in "game-theoretic random graph theory". Also the investigator wants to continue his work to prove a perfect game-theoretic analogue of the probabilistic Lovasz Local Lemma.Traditional game theory focuses on games of incomplete information. The traditional theory provided good insights to Economics, and many areas of social science (Management, Military Strategy, etc.). One can expect at least as many new applications from a successful theory of games of complete information. Positional games, i.e. 2-player "pure conflict" games of skill like Chess and Go, form the most natural and interesting subclass of games of complete information. An extremely exciting aspect of studying positional games is that they give unique insight to how human intelligence works. It concerns fundamental questions like whether human understanding is a computational or non-computational process. Or more specific problems like to understand why (say) Go playing computer programs are nowhere close to the best human players. In contrast to Go, the best Chess-playing programs have reached the level of human Grandmasters. Game-playing computer programs examine millions of positions before deciding what to do next. On the other hand, even the best Grandmasters do not search more than 50 positions per move. In human Chess and particularly in human Go pattern recognition plays a far more important role than search. How to supply this human knowledge to a computer is a puzzle that no one has solved yet. A more concrete theoretical significance of this proposal is that it brings the seemingly separated subjects of Probability Theory, Combinatorics, and Game Theory closer to each other in an unexpected way.