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.
