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