Yannai Gonczarowski - Harvard

Micro Theory Seminar
When Jan 28, 2022
from 02:30 PM to 04:30 PM
Where Zoom Link
Add event to calendar vCal
iCal

Yannai Gonczarowski from Harvard will present "Zero-Knowledge Mechanisms" Joint work with Ran Canetti and Amos Fiat

Abstract:

In a mechanism design setting (with private information and/or private actions), the mechanism designer chooses a mechanism to optimize some target function, and announces the mechanism. The fact that the mechanism is an "open book" incentivizes agents to participate: by inspection, they can verify properties of interest, such as incentive compatibility and individual rationality. However, inspecting the mechanism might also have the side effect of revealing to the agents—whether explicitly or implicitly—information that the mechanism designer may have actually preferred to conceal, such as her target function, or her private costs. Such information being revealed might have real cost (exogenous or endogenous) to the mechanism designer. Transparency, therefore, may turn out to be a double-edged sword.

 Using cryptographic tools such as zero-knowledge proofs, we present a general technique for a mechanism designer to endogenously commit to an undisclosed mechanism, while still proving its properties of interest, such as incentive compatibility and individual rationality, to agents, and at the end of the day proving that the mechanism was indeed run as planned, including that any random draws performed by the mechanism were fair. In a precise sense, agents learn nothing more about the mechanism than its outcome, and in fact, only its realized outcome if the mechanism is randomized.

 Preliminary applications include bargaining, negotiations, ad auctions, and more. Finally, using ideas from prior literature on cryptographic hiding of bids in auctions, we also present an extension that allows both the mechanism and the bids to remain private, in the form of a general *un*revelation principle, opening the door for a new layer of mechanism customization that we call "revelation design."

 No prior knowledge in cryptography will be assumed.

 

More information about this event…