Yotam Gafni, Technion

Abstract

Decentralized cryptocurrencies rely on aligning the incentives of users and miners to operate correctly and offer a high QoS to users. Recent literature studies the mechanism design problem of the auction serving as a cryptocurrency's Transaction Fee Mechanism (TFM). We find that the non-myopic modeling of miners falls close to the well-known problem of online buffer management for packet switching. The main difference is that unlike packets, which are of a fixed size throughout their lifetime, in a financial environment user preferences (and therefore revenue extraction) may be time-dependent. We study the competitive ratio guarantees given a certain discount rate and show how existing methods from packet scheduling perform sub-optimally in the more general discounted setting. We find a novel, simple, memoryless, and competitively optimal deterministic algorithm for the semi-myopic case, as well as a randomized algorithm that achieves better performance than the best possible deterministic algorithm, for any discount rate.

See: https://theory.cs.rutgers.edu/theory_seminar