Game-Theoretically Fair Distributed Sampling

Cleve’s celebrated result (STOC’86) showed that a strongly fair multi-party coin-toss is impossible against majority-sized coalitions. Recently, however, a fascinating line of work studied a relaxed fairness notion called game-theoretic fairness, which guarantees that no coalition should be incentivized to deviate from the prescribed protocol. A sequence of works has explored the feasibility of game-theoretic fairness for two-sided coin-toss, and demonstrated feasibility in the dishonest majority setting under standard cryptographic assumptions. However, this line of work only focused on uniform two-sided coin-toss or leader election. In this work, we initiate the comprehensive study of game-theoretic fairness for multi-party sampling from general distributions. In particular, for the case of m-sided uniform coin-toss we give a nearly complete characterization of the regime in which game-theoretic fairness is feasible. Interestingly, contrary to standard fairness notions in cryptography, the composition of game-theoretically fair two-sided coin-toss protocols does not necessarily yield game-theoretically fair multi-sided coins. To circumvent this, we introduce new techniques compatible with game-theoretic fairness. In particular, we give the following results: