ICES: Large: Computation, Language, and Awareness in Games

很明显，在许多情况下，代理人（在博弈论的意义上）不会做出最佳反应，因为确定最佳反应应该是什么需要大量的努力。这并不会使代理人失去理性；棋手不能达到最佳状态时并不是非理性的。事实上，考虑到它们的计算限制，它们的反应可以被视为完全理性的。标准解决方案的概念，如纳什均衡没有明确考虑计算。在博弈论中考虑计算问题的重要性至少从西蒙的工作开始就得到了认可。pi已经开发了一个考虑计算的一般框架。玩家被视为选择了图灵机（TM）。每个TM M和输入都有一个复杂度。复杂度可以表示M在该输入上的运行时间或使用的空间；它也可以用来捕捉M本身的复杂性（例如，状态的数量），或者模拟寻找新策略来取代玩家已有策略的成本。该方法抓住了重要的直觉，并且可以处理许多众所周知的有问题的示例。此外，这种方法与加密协议安全性之间存在着深刻的联系。因此，从计算游戏的角度思考可以在安全方面带来新的见解和新的方法。这个项目的目标是更广泛地研究在博弈论中增加计算成本的影响。预计这将涉及语言、意识和密码学等问题。将讨论的主题包括以下内容：-将研究这种方法在多大程度上可以捕获安全计算的重要概念并提出新的概念。-在模型中，隐含地假设代理人“理解”与每个TM相关的成本，并“理解”最佳对策是什么。因此，如果复杂性是运行时间，代理知道（或至少有主观信念）每个TM的运行时间。但这些信念从何而来？显然，它们也必须被计算在内。因此，该模型将被扩展，以便它考虑计算信念和最佳响应的成本。这样做将迫使人们认真地考虑语言问题。-早期的模型只考虑普通形式的游戏。在宽泛形式的游戏中，计算成为游戏的明确组成部分。直觉上，当agent进行计算时，他对游戏的理解就会提高，他可能会意识到更多的选择。因此，在广泛形式博弈中的计算和意识之间应该有深刻的联系，这是一个最近在博弈论和计算机科学中引起大量关注的话题；这些将被探讨。-为了进一步理解语言的作用，将考虑语言选择、计算成本和合理性之间的相互作用。这一领域的进展可能会对博弈论和计算机科学的理论模型产生广泛的影响，并对博弈论在社会科学和安全和网络领域的应用产生广泛的影响，在这些领域，博弈论模型正变得越来越普遍。

It is intuitively clear that, in many situations, agents (in the sense of game theory) do not make a best response because determining what the best response should be would require a great deal of effort. This does not make agents irrational; chess players are not being irrational when they fail to play optimally. Indeed, their response could be viewed as perfectly rational, given their computational limitations. Standard solution concepts such as Nash equilibrium do not explicitly take computation into account. The importance of considering computational issues in game theory has been recognized since at least the work of Simon. The PIs have developed a general framework for taking computation into account. A player is viewed as choosing a Turing machine (TM). With each TM M and input is associated a complexity. The complexity can represent the running time of or space used by M on that input; it can also be used to capture the complexity of M itself (e.g., the number of states) or to model the cost of searching for a new strategy to replace one that the player already has. The approach captures important intuitions, and can deal with a number of well-known problematic examples. Moreover, there are deep connections between this approach and cryptographic protocol security. Thus, thinking in terms of computational games can lead to new insights and new approaches in security. The goal of this project is to investigate the implications of adding computational cost to game theory more broadly. This is expected to involve issues of language, awareness, and cryptography. Topics to be addressed include the following: - The extent to which this approach can capture important notions of secure computation and suggest new notions will be studied.- In the model, it is implicitly assumed that agents "understand" the costs associated with each TM and "understand" what the best response is. Thus, if the complexity is taken to be running time, agents know (or at least have subjective beliefs about) the running time of each TM. But where are these beliefs coming from? Clearly they, too, must be computed. Thus, the model will be extended so that it takes into account the cost of computing beliefs and best responses. Doing this will force consideration of issues of language in a serious way. - The earlier model considered only normal-form games. In extensive-form games, computation becomes an explicit part of the game. Intuitively, as the agent does computation, his understanding of the game improves, and he may become aware of more options. Thus, there should be deep connections between computation in extensive-form games and awareness, a topic that has attracted a great deal of recent attention in game theory and computer science; these will be explored.- To further understand the role of language, the interplay between the choice of language, computational cost, and rationality will be considered. Progress in this area could have broad impact on theoretical models in game theory and computer science, and on applications of game theory both to the social sciences and to more practical work in security and networks, where game-theoretic models are becoming more and more prevalent.