  Users bid in a transaction fee mechanism (TFM) to get their transactions
included and confirmed by a blockchain protocol. Roughgarden (EC'21) initiated
the formal treatment of TFMs and proposed three requirements: user incentive
compatibility (UIC), miner incentive compatibility (MIC), and a form of
collusion-resilience called OCA-proofness. Ethereum's EIP-1559 mechanism
satisfies all three properties simultaneously when there is no contention
between transactions, but loses the UIC property when there are too many
eligible transactions to fit in a single block. Chung and Shi (SODA'23)
considered an alternative notion of collusion-resilience, called
c-side-contract-proofness (c-SCP), and showed that, when there is contention
between transactions, no TFM can satisfy UIC, MIC, and c-SCP for any c at least
1. OCA-proofness asserts that the users and a miner should not be able to
"steal from the protocol." On the other hand, the c-SCP condition requires that
a coalition of a miner and a subset of users should not be able to profit
through strategic deviations (whether at the expense of the protocol or of the
users outside the coalition).
  Our main result is the first proof that, when there is contention between
transactions, no (possibly randomized) TFM in which users are expected to bid
truthfully satisfies UIC, MIC, and OCA-proofness. This result resolves the main
open question in Roughgarden (EC'21). We also suggest several relaxations of
the basic model that allow our impossibility result to be circumvented.
