That would hold for basefee = 110 and max fees 120, 115, 112?

This is what would merit closer inspection, because I don’t think it’s necessarily true for “a wide range”. In fact, the more power-law-ish the fee max distribution is the more I suspect this is an issue, since it means there is more premium to extract at the tail. In EIP-1559 at least this attack surface doesn’t exist.

If the base fee is 110 and max fees are 120, 115, 1112, it means that min and max premiums are about 1.8% and 9% of the base fee which is assuming the variation in premium (1.8-9%) is such that the highest bid is 5 times the lowest one, even after removing the top 5% overpayment. On the other hand, suppose everyone bids somewhere between x% to y% over the base fee. The median premium would be around (x+y)/4%. You want (x+y)/4 < x in order to get everyone on board which is equivalent to y < 3x. Moreover, y is computed after removing the top 5% overpayment so that is to say you want the 95th percentile less than 3 times the minimum which is almost always true in real-world data (even remains true if replacing 3 times with 2 times).

Median is in no way sensitive to the tail and fully stable even if we don’t truncate the top 5% tail. The median of a heavy-tailed distribution such as exponential distribution is especially super robust even more than others.

This is one of my questions: why do you believe this will remain true under your mechanism? The fact that it is true now seems to hinge more on the fact that the current system is all-pay so (non-MEV) users try to bid as little as possible. If your mechanism intends to reveal preferences of users by making it incentive compatible to reveal their value as max fee, this is no longer true if you assume user preferences are power-law distributed.

What I meant is that the fatter the tail is, the more incentive for a miner to stuff or strategically not include transactions in their block. Suppose you have three transactions with max fees 10, 10 and 100 (assume basefee residual). If I have space to include them all, from the point of view of social welfare I should, but I’d be quite better off not to include the first two. I understand that you believe this is a contrived example, but it doesn’t change the qualitative result that this attack surface exists. Finding evidence for why in practice this doesn’t matter would be necessary for this proposal to be considered for inclusion imo

Let’s assume that the max fee bids are exponentially distributed on the interval [(1+a)basefee, infinity] with rate parameter lambda. The premium will have an exponential distribution with rate parameter 2lambda. The median will be a/2 + ln(2)/(2lambda). It suffices to have a > a/2 + ln(2)/(2lambda) that is to say a > ln(2)/lambda. If a is for example 2% then lambda can be as low as 1/3, which is very heavy-tailed, and everything still works fine.

I don’t want to repeat myself, talking about the robustness of the median, so let me ask your opinion about another point, which I didn’t want to bring up at first, just to keep things simple. Do you agree that this incentive and attack you are talking about is a consequence of the asymmetry between the base fee and the premium? That is the miner doesn’t care about including more transactions because he won’t get any portion of the base fee. In sharp contrast, he gets 100% of the premium. My previous path-dependence attack is also incentivized because miners like to drive the fee into zero and fall back to the first-price auction mechanism. Why do you think this asymmetry is essential?

I don’t, actually in my example of the three transactions I’ve even discarded basefee as relevant for the discussion. Is it the case that the miner improves their payoff by including only the 100 max fee transaction under the median premium rule, instead of all three? (assume basefee is 0)

The attack is a consequence of allowing the miner to decide what the median of the premiums are by strategically including transactions, so in effect, deciding what the gas price of a block is. It’s not the case in 1559, if you don’t include a transaction, you simply lose out on its revenue, it doesn’t change the price for other included transactions. I understand the median of a particular value distribution is robust to small deviations of the distribution, but it’s besides the point, because the miner has full power to enforce the median premium by selecting judiciously which transactions to include.

Again the assumption of basefee = 0 and max fee = 10, 10, 100 breaks things, because I am assuming that premium is an order of magnitude smaller. However, if you assume basefee = 100, then my point is that x% of 3*110 corresponding to the case that the miner includes all three of them is bigger than x% of 200 correspondings to the case that he only includes the first one. Now, x% can be as low as 1% if we want to have the same burning effect as EIP-1559.