  In recent years, prominent blockchain systems such as Bitcoin and Ethereum
have experienced explosive growth in transaction volume, leading to frequent
surges in demand for limited block space, causing transaction fees to fluctuate
by orders of magnitude. Under the standard first-price auction approach, users
find it difficult to estimate how much they need to bid to get their
transactions accepted (balancing the risk of delay with a preference to avoid
paying more than is necessary).
  In light of these issues, new transaction fee mechanisms have been proposed,
most notably EIP-1559. A problem with EIP-1559 is that under market
instability, it again reduces to a first-price auction. Here, we propose
dynamic posted-price mechanisms, which are ex post Nash incentive compatible
for myopic bidders and dominant strategy incentive compatible for myopic
miners. We give sufficient conditions for which our mechanisms are stable and
approximately welfare optimal in the probabilistic setting where each time
step, bidders are drawn i.i.d. from a static (but unknown) distribution. Under
this setting, we show instances where our dynamic mechanisms are stable, but
EIP-1559 is unstable. Our main technical contribution is an iterative algorithm
that, given oracle access to a Lipschitz continuous and concave function $f$,
converges to a fixed point of $f$.
