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

ICES：大型：游戏中的计算、语言和意识

• 批准号: 1214844
• 负责人: Joseph Halpern
• 金额: $ 90万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1214844&HistoricalAwards=false
• 关键词: ICES; Large; Computation; Language; Awareness

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.

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

项目成果

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems

开放多智能体系统中规范监控的激励兼容机制

• DOI: 10.1613/jair.1.11214
• 发表时间: 2018
• 期刊: Journal of Artificial Intelligence Research
• 影响因子: 5
• 作者: Alechina, Natasha;Halpern, Joseph Y.;Kash, Ian A.;Logan, Brian
• 通讯作者: Logan, Brian