What Makes a Transaction Fee Mechanism Rational and Efficient?

Table of Links

Abstract and 1. Introduction

2. Related Work

3. Preliminaries

   3.1 TFMs: Desirable Properties

   3.2 Groves’ Redistribution Mechanism (RM)

4. IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index

5. Transaction Fee Redistribution Mechanism (TFRM)

6. R-TFRM: A TFRM Robust to Miner Manipulation

   6.1 R-TFRM: Analyzing Impact of Miner Manipulation on Rebate and Miner Revenue

7. R2-TFRM: Robust and Rational TFRM

8. Conclusion and References

A. Proofs for Results from Section 4 and 5

B. Proofs for Results from Section 6

C. Proofs for Results from Section 7

3.1 TFMs: Desirable Properties

We now define the relevant incentive properties of a TFM (from [14, 33]). We begin by defining Individual Rationality.

Individual Rationality (IR). To incentivize participation, mechanism designers also focus on IR.

As we show later, ensuring UIC while minimizing transaction fees in a TFM is challenging. Hence, we focus on the incentive compatibility of a ‘restricted’ set of users whose transactions are included in the block. We define restricted UIC (RUIC), which states that for all the included users, reporting truthfully is IC irrespective of what the remaining included users report.

Other Properties. Outside of these common TFM properties, we also define additional properties, namely allocative efficiency (AE) and weakly/strongly budget balance (WBB/SBB) next.

3.2 Groves’ Redistribution Mechanism (RM)

Towards minimizing the user cost in a TFM, we employ Redistribution Mechanisms (RMs) [25]. In RM, the agents are charged VCG payments and the money is redistributed back to agents while ensuring UIC. The redistribution is decided by constructing an appropriate rebate function, 𝑔 : b → R. We desire rebate functions that ensure maximum rebate (or, equivalently, minimize the transaction fees in TFM). To utilize an RM as a TFM, we require that it satisfies UIC/RUIC and (ex-post) IR for the users and the miner. An RM is IR for users when each user’s overall payment, including the rebate, provides a non-negative utility. Likewise, we say that an RM is IR for the miner when the total rebate is less than the payment (transaction fees) received. We also want the RM to be anonymous [20].

Note that, an anonymous rebate function may still result in different redistribution payments to different users as the input to the function may be arbitrarily different.

Rebate Function. We aim to design an appropriate rebate function for an anonymous RM such that incentive properties from Section 3.1 hold. The rebate function must also redistribute most of the payments (VCG payments) as possible to minimize the user cost. We begin by providing the following characterization for designing UIC rebate functions.

The rebate function is UIC if the rebate for a user𝑖 is independent of its own bid. In general, it could take any form. E.g., the linear rebate function is defined as,

The fraction of VCG payment redistributed, given a rebate function, depends on the input bids. Thus, we study the worst-case and average-case performance of the rebate functions.

E.g., Guo and Conitzer [20] propose Worst-case Optimal (WCO), a mechanism that uniquely maximizes the worst-case RI (among all RMs that are deterministic, anonymous, and satisfy UIC, AE, and IR) when the items are homogeneous with unit demand [20, Theorem 1]. In the blockchain, we assume the availability of 𝑘 confirmation slots, and any user equally values transaction confirmation at every slot. Moreover, each transaction only requires one slot for confirmation. Thus, this is a homogeneous setting with unit demand.