Winner’s curse applies in common value auctions (the value of the item is the same but imprecisely known to all bidders). This is a private value auction, where bidders have different values because their compute overhead is different (and known ahead of time).
An English auction (open first-price ascending, this proposal) is pareto-optimal (and equivalent to a Vickrey auction (sealed second-price)), incentivising bidders to bid their true value (less the information value of bids).
Edit: There does appear to be some uncertainty regarding L1 fees.
I propose a gas rebate (funded by base-fee), which refunds L1 fees for submitting proofs.