  Decentralized cryptocurrencies are payment systems that rely on aligning the
incentives of users and miners to operate correctly and offer a high quality of
service to users. Recent literature studies the mechanism design problem of the
auction serving as a cryptocurrency's transaction fee mechanism (TFM). We
present a general framework that captures both myopic and non-myopic settings,
as well as different possible strategic models for users. Within this general
framework, when restricted to the myopic case, we show that while the mechanism
that requires a user to "pay-as-bid", and greedily chooses among available
transactions based on their fees, is not dominant strategy incentive-compatible
for users, it has a Bayesian-Nash equilibrium where bids are slightly shaded.
Relaxing this incentive compatibility requirement circumvents the impossibility
results proven by previous works, and allows for an approximately revenue and
welfare optimal, myopic miner incentive-compatible (MMIC), and
off-chain-agreement (OCA)-proof mechanism. We prove these guarantees using
different benchmarks, and show that the pay-as-bid greedy auction is the
revenue optimal Bayesian incentive-compatible, MMIC and 1-OCA-proof mechanism
among a large class of mechanisms. We move beyond the myopic setting explored
in the literature, to one where users offer transaction fees for their
transaction to be accepted, as well as report their urgency level by specifying
the time to live of the transaction, after which it expires. We analyze
pay-as-bid mechanisms in this setting, and show the competitive ratio
guarantees provided by the greedy allocation rule. We then present a
better-performing non-myopic rule, and analyze its competitive ratio. The above
analysis is stated in terms of a cryptocurrency TFM, but applies to other
settings, such as cloud computing and decentralized "gig" economy, as well.

Computer Science and Game Theory;Theoretical Economics