Positional Games and Random Structures--A mathematical paradox

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

Every ``theory'' of games concentrates on one particularaspect of games, and ignores the rest.Traditional Game Theory (J. von Neumann, J. Nash, etc.)focuses on the lack of complete information(e.g., card games like Poker).Games of complete information, like Chess, Go, Checkers, andTic-Tac-Toe, are ignored by the traditional theory.Here the investigator develops a new branch of game theory.He focuses on ``Tic-Tac-Toe like games'' (officially called Positional Games),a large and imortant class of games of ``complete information'',and develops a ``fake probability theory''.In fact, the investigator continues his on-going researchstarted in the prior proposals.The basic challenge of games of ``complete information''is to handle the ``combinatorial chaos''.To analyze a position (say in Chess, or in multi-dimensionalTic-Tac-Toe), one has to examine all of its options, and all theoptions of these options, and all the options of the options of theseoptions, and so on. Theexhaustive search through the ``game-tree''takes enormous amount of time.One way to make up for the lack of timeis to study the random walk on the game-tree,that is, to study the randomized game where both players play randomly.The most surprising part of the proposalis how the probabilistic analysis of the randomized game is converted,via potential arguments, into an explicit (deterministic) optimal strategy.The investigator calls it a ``mathematical paradox'' for good reason.Game Theory is about perfect players, and it is verysurprising that a play between random generators(``dumb players'') has anything to do with a play between perfectplayers! In contrast to ``Poker and randomness'', which is a naturalcombination (see e.g. the role of ``bluffing''), ``Tic-Tac-Toe and randomness''sounds like a very strange mismatch. The justification of thismismatch requires a long technical explanation.The theoretical significance of the proposal is thatit brings the remote subjects of ProbabilityTheory, Combinatorics, and Game Theory close to each otherin a novel, unexpected way.