  In this paper we show that, using only mild assumptions, previously proposed
multidimensional blockchain fee markets are essentially optimal, even against
worst-case adversaries. In particular, we show that the average welfare gap
between the following two scenarios is at most $O(1/\sqrt{T})$, where $T$ is
the length of the time horizon considered. In the first scenario, the designer
knows all future actions by users and is allowed to fix the optimal prices of
resources ahead of time, based on the designer's oracular knowledge of those
actions. In the second, the prices are updated by a very simple algorithm that
does not have this oracular knowledge, a special case of which is similar to
EIP-1559, the base fee mechanism used by the Ethereum blockchain. Roughly
speaking, this means that, on average, over a reasonable timescale, there is no
difference in welfare between 'correctly' fixing the prices, with oracular
knowledge of the future, when compared to the proposed algorithm. We show a
matching lower bound of $\Omega(1/\sqrt{T})$ for any implementable algorithm
and also separately consider the case where the adversary is known to be
stochastic.
