Cryptographic Game Theory

密码博弈论

• 批准号: 0551244
• 负责人: Silvio Micali
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-03-01 至 2010-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0551244&HistoricalAwards=false
• 关键词: Cryptographic; Game; Theory

This study bridges the theoretical constructs from Computer Science and Game theory. The first stage of the project consists of simulating normal-form mediated games by equivalent extensive-form games that do not rely on any mediators. Here equivalence means having the same equilibria and having the same correctness and privacy. Most of solutions to Mechanism Design problems involve a mediator (often a mechanism designer himself), who collects reports from (economic) agents, processes them, and reveals an outcome. In settings with incomplete information the mediator has to operate with private information, and thus, has to be trusted by the agents to do what he is supposed to.The issue of trust is closely related to privacy. Privacy of information is clearly a human desideratum, stemming from utilitarian concerns about future interactions, yet, somewhat surprisingly, it avoided attention of Game Theory. In Cryptography, on the other hand, the importance of privacy protection is well understood, and it is the major component of various security notions. In particular, the goal of Secure Function Evaluation (SFE) is to suggest a way that the players, each having a private input, by communicating back and forth, can evaluate a joint function on their inputs with the same correctness and privacy as in the ideal evaluation, where they report their inputs to the mediator who reveals the corresponding output. Having the same correctness and privacy means that even if there is a coalition of malicious players, who can freely communicate and coordinate their actions, what they can do and what they can learn about private information of the others in the real evaluation is the same as in the ideal evaluation. Existing SFEs are ideal, but cannot be used in simulating mediators of games, for a simple reason: they do not protect incentives, relying on honesty of non-malicious players (who have to follow their instructions blindly). This study develops an improved notion--rational SFE. The key technical component that is the foundation of this study is a simple ancient randomizing device--a ballot box.The second stage of the project investigates specific applications that depend on the precise control of information flows: (1) simulating mediators under a variety of players' participation conditions, including renegotiation; (2) manipulating a general class of cheap-talk ballot-box games that are developed in this study, particularly focusing on what players can achieve by coordinating instead of limiting what they can do; and (3) bargaining, auctioning and voting applications.In stage three of this study, the extensive form mediated games is formalized, with multiple rounds of mediated communication and multiple rounds of external information inflow. The goal is twofold: build infrastructure for repeated mechanism design, when it is known that multiple problems are to be solved simultaneously or sequentially; and build infrastructure for modular mechanism design, where a problem is to be solved separately, but with known implications to other related problems.Broader impacts: There are far-reaching practical implications of this cross-insemination of ideas between Cryptography and Game Theory. Mediators or intermediaries such as brokers, auctioneers, market makers, planners, government agencies facilitate transactions and in informational exchange. The results of this study are expected to inform and improve the roles of mediators and provide foundations for designing real-world mechanisms and institutions that substitute or augment existing mediators, particularly in issues of privacy, security and trust. This research also has a strong educational component, for the researchers will develop a new course on "Cryptographic Game Theory" that is expected to have multi-disciplinary appeal.

本研究将计算机科学和博弈论的理论架构联系起来。 该项目的第一阶段包括模拟正常形式介导的游戏等效的扩展形式的游戏，不依赖于任何调解人。 在这里，等效性意味着具有相同的均衡以及相同的正确性和隐私性。 大多数机制设计问题的解决方案都涉及一个中介（通常是机制设计者自己），他从（经济）代理人那里收集报告，处理它们，并揭示结果。 在信息不完全的情况下，中介者必须处理私人信息，因此，必须得到代理人的信任，才能做他应该做的事情。信任问题与隐私密切相关。 信息隐私显然是人类的迫切需要，源于对未来互动的功利主义关注，然而，有点令人惊讶的是，它避开了博弈论的关注。 另一方面，在密码学中，隐私保护的重要性是众所周知的，它是各种安全概念的主要组成部分。 特别是，安全功能评估（SFE）的目标是建议一种方式，每个玩家都有一个私人的输入，通过来回通信，可以评估他们的输入与理想评估中相同的正确性和隐私的联合功能，其中他们将他们的输入报告给中介谁揭示了相应的输出。 具有相同的正确性和隐私性意味着即使存在恶意玩家的联盟，他们可以自由地通信和协调他们的行动，在真实的评估中他们可以做什么以及他们可以了解到关于其他人的私人信息的内容与理想评估中的内容相同。 现有的SFE是理想的，但不能用于模拟游戏的中介，原因很简单：它们不保护激励机制，依赖于非恶意玩家的诚实（他们必须盲目地遵循他们的指示）。 本研究提出了一个改进的概念--理性SFE。 作为本研究基础的关键技术组件是一个简单的古代随机化设备--投票箱。该项目的第二阶段研究了依赖于信息流精确控制的具体应用：（1）在各种参与者的参与条件下模拟调解人，包括重新谈判;（2）操纵本研究中开发的一般类廉价谈话投票箱游戏，特别关注参与者通过协调而不是限制他们可以做什么来实现什么;（3）讨价还价、拍卖和投票的应用。在本研究的第三阶段，形式化了广泛形式的中介博弈，具有多轮中介沟通和多轮外部信息流入。 目标是双重的：当已知多个问题要同时或顺序解决时，为重复的机制设计建立基础设施;当一个问题要单独解决时，为模块化机制设计建立基础设施，但对其他相关问题有已知的影响。更广泛的影响：密码学和博弈论之间的这种思想交叉传播具有深远的实际意义。 中介人或中间人，如经纪人，拍卖人，做市商，规划师，政府机构促进交易和信息交流。 这项研究的结果预计将告知和改善调解人的作用，并为设计替代或加强现有调解人的现实世界机制和机构提供基础，特别是在隐私，安全和信任问题上。 这项研究也有很强的教育成分，研究人员将开发一个新的课程“密码博弈论”，预计将有多学科的吸引力。