Every ``theory'' of games concentrates on one particular aspect 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, and Tic-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 research started 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-dimensional Tic-Tac-Toe), one has 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 exhaustive search through the ``game-tree'' takes enormous amount of time. One way to make up for the lack of time is 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 proposal is 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 very surprising that a play between random generators (``dumb players'') has anything to do with a play between perfect players! In contrast to ``Poker and randomness'', which is a natural combination (see e.g. the role of ``bluffing''), ``Tic-Tac-Toe and randomness''sounds like a very strange mismatch. The justification of this mismatch requires a long technical explanation. The theoretical significance of the proposal is that it brings the remote subjects of Probability Theory, Combinatorics, and Game Theory close to each other in a novel, unexpected way.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Type
Standard Grant (Standard)
Application #
0406597
Program Officer
Tomek Bartoszynski
Project Start
Project End
Budget Start
2004-06-01
Budget End
2007-05-31
Support Year
Fiscal Year
2004
Total Cost
$111,960
Indirect Cost
Name
Rutgers University
Department
Type
DUNS #
City
New Brunswick
State
NJ
Country
United States
Zip Code
08901