RI: Medium: Computation, Language, and Games

RI：媒介：计算、语言和游戏

• 批准号: 1703846
• 负责人: Joseph Halpern
• 金额: $ 117.66万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-06-15 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1703846&HistoricalAwards=false
• 关键词: RI; Medium; Computation; Language; Games

While game theory has been able to make useful predictions in many situations of interest, it is well known that, in many games of interest, the predictions of game theory are simply incorrect. This project focuses on one potential explanation: players' computational limitations. Game theory has assumed that all players are rational. In the literature, "rational" is taken to mean, among other things, that players can compute their beliefs and a best response to what they believe other players are doing. But such computations may not be so easy to perform. The project will still assume that players are rational, but will try to model explicitly the fact that people are computationally bounded and are affected by how games are framed/described in terms of language. It will then consider the consequences of assuming that people are playing rationally in the sense of doing the best that they can, subject to their computational limitations and how they describe their world. More specifically, the project will focus on three inter-related topics. 1) Taking computation into account in human behavior: The project will investigate how the formal models introduced in the PI's earlier work on games with computationally bounded players can be used to explain human behavior such as rational inattention, where people seem to ignore variables that seem relevant, and anomalies in human behavior in real-world deployments of game theory to applications such as security of wildlife and fisheries, forest protection, and drug interdiction. 2) Computational and language issues in dynamic games: Intuitively, as an agent does computation, his understanding of the game improves, his judgments of uncertainty becomes sharper, he may become aware of more options, and his utility function may change. The project will investigate approaches to modeling this process, including issues such as procrastination effects ("I'd rather start my diet tomorrow and eat the chocolate cake today than start my diet today"; if this reasoning is applied every day, the agent will never start his diet). 3) Cryptography and game theory: Modern cryptography can usefully be viewed as a game between resource-bounded agents. The project will investigate these connections, with the hope of being able to design better cryptographic protocols. One concrete outcome of the work will be better mechanisms for achieving desired outcomes. For example, understanding the effect of computational limitations on people's behavior may enable better mechanisms for preventing poaching. A particular focus area will be Bitcoin, which can be viewed as a game between resource-bounded miners.

虽然博弈论已经能够在许多感兴趣的情况下做出有用的预测，但众所周知，在许多感兴趣的博弈中，博弈论的预测是不正确的。这个项目集中在一个潜在的解释：玩家的计算限制。博弈论假设所有参与者都是理性的。在文献中，“理性”被认为是指，除其他外，参与者可以计算他们的信念和他们认为其他参与者正在做的事情的最佳反应。但这样的计算可能不那么容易执行。该项目仍将假设玩家是理性的，但将尝试明确建模的事实，即人是计算有限的，并受到游戏的语言框架/描述的影响。然后，它将考虑假设人们在尽可能做到最好的意义上理性博弈的后果，这取决于他们的计算限制以及他们如何描述他们的世界。更具体地说，该项目将侧重于三个相互关联的主题。 1)考虑到人类行为中的计算：该项目将研究如何在PI的早期工作中引入计算有限玩家的游戏的正式模型可以用来解释人类行为，例如理性疏忽，人们似乎忽略了似乎相关的变量，以及在现实世界中的人类行为异常博弈论部署到野生动物和渔业安全等应用中，森林保护和禁毒。2)动态博弈中的计算和语言问题：直觉上，当一个智能体进行计算时，他对博弈的理解会提高，他对不确定性的判断会变得更敏锐，他可能会意识到更多的选择，他的效用函数可能会改变。该项目将研究建模这一过程的方法，包括拖延效应等问题（“我宁愿明天开始节食，今天吃巧克力蛋糕，也不愿今天开始节食”;如果每天都应用这种推理，代理人将永远不会开始节食）。3)密码学和博弈论：现代密码学可以有效地被视为资源有限的代理之间的博弈。该项目将研究这些连接，希望能够设计出更好的加密协议。这项工作的一个具体成果将是建立更好的机制，以实现预期成果。例如，了解计算限制对人们行为的影响可能有助于更好地防止偷猎。一个特别关注的领域将是比特币，它可以被视为资源有限的矿工之间的游戏。

项目成果

Concurrently Composable Non-interactive Secure Computation

可并发组合的非交互式安全计算

• 发表时间: 2022
• 期刊: Asiacrypt 2022
• 作者: Andrew Morgan, Rafael Pass

From Type Spaces to Probability Frames and Back, via Language

通过语言从类型空间到概率框架并返回

• DOI: 10.4204/eptcs.251.6
• 发表时间: 2017
• 期刊: Electronic Proceedings in Theoretical Computer Science
• 作者: Bjorndahl, Adam;Halpern, Joseph Y.
• 通讯作者: Halpern, Joseph Y.

A Knowledge-Based Analysis of the Blockchain Protocol

区块链协议的基于知识的分析

• DOI: 10.4204/eptcs.251.22
• 发表时间: 2017
• 期刊: Electronic Proceedings in Theoretical Computer Science
• 作者: Halpern, Joseph Y.;Pass, Rafael
• 通讯作者: Pass, Rafael

Sequential Equilibrium in Computational Games

计算游戏中的顺序均衡

• DOI: 10.1145/3340232
• 发表时间: 2019
• 期刊: ACM Transactions on Economics and Computation
• 影响因子: 1.2
• 作者: Halpern, Joseph Y.;Pass, Rafael
• 通讯作者: Pass, Rafael

Bayesian games with intentions

有意图的贝叶斯博弈

• DOI: 10.1016/j.geb.2020.06.003
• 发表时间: 2020
• 期刊: Games and Economic Behavior
• 影响因子: 1.1
• 作者: Bjorndahl, Adam;Halpern, Joseph Y.;Pass, Rafael
• 通讯作者: Pass, Rafael