Positional Games and Random Structures--A mathematical paradox

位置博弈与随机结构--一个数学悖论

• 批准号: 0406597
• 负责人: Jozsef Beck
• 金额: $ 11.2万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-06-01 至 2007-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0406597&HistoricalAwards=false
• 关键词: Positional; Games; Random; Structures; mathematical

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.

每一种博弈的“理论”都集中在博弈的一个特定方面，而忽略了其他方面。关注于缺乏完整信息（例如，传统的博弈论忽视了完全信息博弈，如国际象棋、围棋、扑克、井字棋等。本文发展了博弈论的一个新的分支，即“井字棋类博弈”。（正式称为位置游戏），一个大的和重要的一类游戏的“完全信息”，并开发了一个"假概率理论“。事实上，研究者继续着他在先前的提议中开始的正在进行的研究。"完全信息“博弈的基本挑战是处理"组合混沌”。分析一个位置（比如在国际象棋中，或者在多维的井字游戏中），一个人必须检查所有的选项，以及这些选项中的所有选项，以及这些选项中的所有选项，等等。在“博弈树”中的穷举搜索需要大量的时间。弥补时间不足的一个方法是研究博弈树上的随机游走，即，研究双方随机博弈的随机博弈。命题中最令人惊讶的部分是随机博弈的概率分析是如何转换的，研究者称之为“数学悖论”是有充分理由的。博弈论是关于完美的参与者的，而令人惊讶的是，随机生成者（“愚蠢的参与者”）之间的博弈与完美参与者之间的博弈有任何关系！与“扑克和随机性”这一自然组合（例如，“虚张声势”的作用）相反，“井字游戏和随机性”听起来像是一个非常奇怪的不匹配。这种不匹配的合理性需要很长的技术解释。该提案的理论意义在于，它以一种新颖、意想不到的方式使概率论、组合学和博弈论等遥远的学科相互接近。