A Complete Characterization of Game-Theoretic Fair Coin Toss

PRESIDENT’S POSTDOC FELLOWSHIP PROGRAM CANDIDATE

Zoom link

Abstract: Coin toss has been extensively studied in the cryptography literature, and the traditional notion of fairness requires that no corrupted coalition can cause any non-negligible bias. In this case, it is well-understood that fairness is impossible against a corrupted majority.

In this talk, I will introduce a relaxed notion called game-theoretic fairness, which guarantees that no coalition can gain benefit by deviating. We give a complete characterization of the regime in which game-theoretic fair coin toss is possible, by providing a matching upper and lower bound on the size of the coalition we can tolerate. At the end of the talk, I will briefly introduce how game-theoretic fairness can be generalized to broader randomness generation tasks.

Bio:  Ke Wu is a Ph.D. candidate at Carnegie Mellon University, advised by Elaine Shi. Her research focused on combining cryptography and game theory to model incentives and design incentive-compatible mechanisms. Before joining CMU, she completed her MS in CS in 2017 at Johns Hopkins University, where she worked with Xin Li on coding theory. Prior to that, she graduated from Fudan University with a BA in Math in 2016.