Abstract and 1. Introduction

  1. Related Work

  2. Preliminaries

    3.1 TFMs: Desirable Properties

    3.2 Groves’ Redistribution Mechanism (RM)

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

  4. Transaction Fee Redistribution Mechanism (TFRM)

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

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

  6. R2-TFRM: Robust and Rational TFRM

  7. 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

4 IDEAL-TFRM: IMPOSSIBILITY OF ACHIEVING STRICTLY POSITIVE REDISTRIBUTION INDEX

Worst-case Rebate. Theorem 2 formally shows the impossibility of simultaneously guaranteeing UIC and minimizing transaction fees in Ideal-TFRM.

Theorem 2 (Ideal-TFRM Impossibility). If π‘Ÿ β˜… is an anonymous rebate function that satisfies Theorem 1, no Ideal-TFRM can guarantee a non-zero redistribution index (RI) in the worst case.

Proof Sketch. Informally, if the rebate function is anonymous (Definition 7) and the user with the highest valued transaction is confirmed and receives a positive rebate. Then, it is easy to show that there exists a different bid profile for which the last unconfirmed transaction must receive the same positive rebate. Therefore, the only way to ensure zero rebate for unconfirmed transactions is to also ensure zero rebate for every confirmed transaction. Thus, the worst-case RI is zero. See Appendix A.1 for the formal proof.

Training Details. We keep 𝑛 = 10 with number of confirmed transactions as π‘˜ = 7. For the optimizer, we choose a fixed learning rate πœ‚ = 5𝑒 βˆ’ 4. The batch size is 1000, and we train for 50,000 epochs.

We conclude that it is impossible to design a TFRM with a linear rebate function that is UIC (Theorem 1) and offers a non-zero rebate to any agent. Our experiments also highlight that this may also be unlikely for non-linear rebate functions. Therefore, the next section introduces the general TFRM framework, where we focus on restricted UIC.

5 TRANSACTION FEE REDISTRIBUTION MECHANISM (TFRM)

TFRM: RUIC. While the rebate function satisfies Theorem 1, note that TFRM is not UIC. E.g., users not part of the block may report 𝑏 > πœƒ to grab the additional rebate, as only confirmed bids pay the transaction fee. However, TFRM satisfies RUIC, i.e., it is UIC for agents included in the block to bid their true valuation. All included users, confirmed or not, are offered rebates implying that π‘˜ slots offered to 𝑛 users is equivalent to the allocation of π‘˜ resources among 𝑛 agents. Thus, by Theorem 1, TFRM is RUIC

We now show that in the presence of a strategic miner, the TFRM in Figure 2 results in net zero rebates to confirmed users.

Thus, designing TFRMs to minimize transaction fees may only work if made resilient to such strategic manipulations. Unlike RMs, TFRMs must quantify the rebate redistributed to the genuine users. Towards this, we define the following metric:

Authors:

(1) Sankarshan Damle, IIIT, Hyderabad, Hyderbad, India ([email protected]);

(2) Manisha Padala, IISc, Bangalore, Bangalore, India ([email protected]);

(3) Sujit Gujar, IIIT, Hyderabad, Hyderbad, India ([email protected]).

This paper is available on arxiv under CC BY 4.0 DEED license.

[4] Assigning future costs to transactions not confirmed, e.g., as in [8] (Section 2), may help overcome such manipulation. We leave the analysis for future work.