Computer Science Thesis Proposal

April 17, 2023 2:00pm — 3:30pm

Location:
In Person and Virtual - ET - Reddy Conference Room, Gates Hillman 4405 and Zoom

Speaker:
KE WU , Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://kewucs.com/

Game Theory Meets Cryptography: Decentralized Mechanism Design

Recent works of Roughgarden (EC’21) and Chung and Shi (SODA’23) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Several recent works showed that the transaction fee mechanism design fundamentally departs from the classical mechanism design. Specifically, Chung and Shi showed two main impossibility results that rule out the existence of a dream TFM. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, no matter whether the block size is finite or infinite. Second, assuming a finite block size, no nontrivial TFM can simultaneously provide incentive compatibility for any individual user and for any miner-user coalition.

In this thesis, we study the possible relaxations and the theoretical landscape of the transaction fee mechanisms under these relaxations.

Achieved results. In previous work, we explored the complete characterization of the following three dimensions of relaxation. 

1. MPC-assisted model. Besides today’s model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. We show that while cryptography is not a panacea, it indeed allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model. 
2. Approximate Incentive Compatibility. We also consider allowing the strategic players to gain no more than ε-more utility compared to behaving honestly. We prove several feasibility and infeasibility results in both the plain and MPC-assisted models. 
3. Reasonable-world assumption. We show that if we make a mildly stronger assumption assuming that we know a lower bound h on the number of honest users, and an upper bound d on the number of bids controlled by the coalition, we can circumvent the known limitations on miner revenue, and design auctions that generate optimal miner revenue.

Proposed Direction. While the relaxations above broaden the design space of transaction fee mechanisms and circumvent the previous impossibility results, it is still impossible to have a non-trivial, strict incentive-compatible mechanism for a finite block size when there are two or more users in the coalition. Therefore, we ask the following question: Are there any meaningful relaxed incentive compatibility notions that allow us to circumvent the impossibility  of finite block size when two or more users are in the coalition?

Thesis Committee:

In Person and Zoom Participation. See announcement.

Add event to Google
Add event to iCal