Table of Links Abstract and 1. Introduction Abstract and 1. Introduction Related Work


Preliminaries
3.1 TFMs: Desirable Properties
3.2 Groves’ Redistribution Mechanism (RM)


IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index


Transaction Fee Redistribution Mechanism (TFRM)


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


R2-TFRM: Robust and Rational TFRM


Conclusion and References Related Work Related Work Related Work Preliminaries
3.1 TFMs: Desirable Properties
3.2 Groves’ Redistribution Mechanism (RM) Preliminaries Preliminaries 3.1 TFMs: Desirable Properties 3.1 TFMs: Desirable Properties 3.2 Groves’ Redistribution Mechanism (RM) 3.2 Groves’ Redistribution Mechanism (RM) IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index Transaction Fee Redistribution Mechanism (TFRM) Transaction Fee Redistribution Mechanism (TFRM) Transaction Fee Redistribution Mechanism (TFRM) R-TFRM: A TFRM Robust to Miner Manipulation
6.1 R-TFRM: Analyzing Impact of Miner Manipulation on Rebate and Miner Revenue R-TFRM: A TFRM Robust to Miner Manipulation R-TFRM: A TFRM Robust to Miner Manipulation 6.1 R-TFRM: Analyzing Impact of Miner Manipulation on Rebate and Miner Revenue 6.1 R-TFRM: Analyzing Impact of Miner Manipulation on Rebate and Miner Revenue R2-TFRM: Robust and Rational TFRM R2-TFRM: Robust and Rational TFRM R2-TFRM: Robust and Rational TFRM Conclusion and References Conclusion and References Conclusion and References A. Proofs for Results from Section 4 and 5 A. Proofs for Results from Section 4 and 5 B. Proofs for Results from Section 6 B. Proofs for Results from Section 6 C. Proofs for Results from Section 7 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. Individual Rationality (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. Other Properties. 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]. Redistribution Mechanisms anonymous 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. Rebate Function. 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. Authors:
(1) Sankarshan Damle, IIIT, Hyderabad, Hyderbad, India (sankarshan.damle@research.iiit.ac.in);
(2) Manisha Padala, IISc, Bangalore, Bangalore, India (manishap@iisc.ac.in);
(3) Sujit Gujar, IIIT, Hyderabad, Hyderbad, India (sujit.gujar@iiit.ac.in). Authors: Authors: (1) Sankarshan Damle, IIIT, Hyderabad, Hyderbad, India (sankarshan.damle@research.iiit.ac.in); (2) Manisha Padala, IISc, Bangalore, Bangalore, India (manishap@iisc.ac.in); (3) Sujit Gujar, IIIT, Hyderabad, Hyderbad, India (sujit.gujar@iiit.ac.in). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

What Makes a Transaction Fee Mechanism Rational and Efficient?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Ways to Measure Privacy Risks in Text Data

Designing Fairer, Cheaper Blockchain Fee Systems

The Game Theory Behind Blockchain Fee Models

Limits of Fair Rebate Mechanisms in Blockchain Transactions

Protecting Rebates from Miner Games with R-TFRM

5 Ways to Measure Privacy Risks in Text Data

Designing Fairer, Cheaper Blockchain Fee Systems

The Game Theory Behind Blockchain Fee Models

Limits of Fair Rebate Mechanisms in Blockchain Transactions

Protecting Rebates from Miner Games with R-TFRM

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps