Game Theory and Mathematical Economics Research Seminar: Zero-Knowledge Mechanisms - Yannai A. Gonczarowski

Wed, 27/10/2021
See also: seminars
Elath Hall, 2nd floor, Feldman Building, Edmond Safra  Campus
Yannai A. Gonczarowski , Harvard University

Speaker: Yannai A. Gonczarowski , Harvard University
Topic: Zero-Knowledge Mechanisms: Trust without Transparency, an *Un*revelation Principle, and Preliminary Applications
(Joint work with Ran Canetti and Amos Fiat)
Place: Elath Hall, 2nd floor, Feldman Building, Edmond Safra  Campus
Time: Sunday, October 17, 2021 at 16:00 p.m.

Refreshments available at 15:45 p.m.


Abstract: In a mechanism design setting, 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.

Yannai A. Gonczarowski is an Assistant Professor of Economics and of Computer Science at Harvard University—the first faculty member at Harvard to have ever been appointed to both of these departments. Interested in both economic theory and theoretical computer science, Yannai harnesses approaches, aesthetics, and techniques traditionally originating in computer science to derive economically meaningful insights. Yannai received his PhD from the Departments of Math and CS, and the Center for the Study of Rationality, at the Hebrew University of Jerusalem, where he was advised by Sergiu Hart and Noam Nisan. Yannai is also a professionally-trained opera singer, having acquired a bachelor’s degree and a master’s degree in Classical Singing at the Jerusalem Academy of Music and Dance. Yannai's doctoral dissertation was recognized with several awards, including the 2018 Michael B. Maschler Prize of the Israeli Chapter of the Game Theory Society and the ACM SIGecom Doctoral Dissertation Award for 2018. For the design and implementation of the National Matching System for Gap-Year Programs in Israel, he was awarded the Best Paper Award at MATCH-UP'19 and the inaugural INFORMS AMD Michael H. Rothkopf Junior Researcher Paper Prize (first place) for 2020. Yannai is also the recipient of the inaugural ACM SIGecom Award for Best Presentation by a Student or Postdoctoral Researcher at EC'18. His first textbook, "Mathematical Logic through Python" (Gonczarowski and Nisan), which introduces a new approach to teaching the material of a basic Logic course to Computer Science students, tailored to the unique intuitions and strengths of this cohort of students, is forthcoming in Cambridge University Press.