Pith. sign in

REVIEW 3 major objections 5 minor 52 references

Transaction Fee Mechanism Design for Leaderless Blockchain Protocols

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Splitting transaction fees equally among all block producers makes the intended allocation a Pareto-dominant equilibrium and guarantees at least 63.2% of optimal welfare for leaderless blockchains.

desk verdict New and important model for multi-proposer TFMs with a clean mechanism and a 1-1/e guarantee, but the equilibrium-selection caveat is bigger than the paper lets on and several proofs need real work. read the letter →

arxiv 2505.17885 v2 pith:2TQFA6B5 submitted 2025-05-23 cs.GT

Pranav Garimidi , Lioba Heimbach , Tim Roughgarden This is my paper · ORCID
classification cs.GT MSC 91B2691A1805B35
keywords transactionfeemechanismleaderlessblockchainDAG-basedconsensusfirst-priceauctionwithequalsharingstrongBPICsubgameperfectequilibriumpriceofanarchywelfareapproximation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how a blockchain with many block producers, rather than a single leader, should charge and distribute transaction fees so that users and producers both behave well. It argues that a first-price auction in which every included transaction pays its bid and that payment is split equally among all block producers, called FPA-EQ, is strongly incentive-compatible for producers: the intended welfare-maximizing allocation is always a Nash equilibrium and Pareto dominates every other producer equilibrium. The paper proves that at any inclusion-rule-respecting subgame perfect equilibrium, expected welfare is at least $1 - 1/e \approx 63.2\%$ of the maximum possible, for arbitrary correlated user valuations, and that this bound is tight. It also proves that these compromises are unavoidable: no strongly producer-incentive-compatible mechanism with nontrivial welfare guarantees can be dominant-strategy truthful, and none can guarantee full efficiency. For the new generation of leaderless, DAG-based consensus protocols, this provides a concrete fee design with quantitative welfare guarantees.

What carries the argument

The central object is FPA-EQ, a transaction fee mechanism composed of a welfare-maximizing inclusion rule, a first-price confirmation and payment rule, and an equal-share distribution rule that gives every block producer $1/m$ of each included fee. The argument rests on two structural facts: feasible transaction sets form a matroid, so all welfare-maximizing allocations are equivalent and the intended allocation Pareto dominates all producer equilibria, establishing strong BPIC; and once producers are fixed to the intended allocation rule, the induced user game is a winner-pays-bid matroid auction, which is $(1 - 1/e, 1)$-smooth with private deviations. The smoothness price-of-anarchy theorem then converts this local deviation property into the global $63.2\%$ welfare floor.

What would settle it

To refute Theorem 3.4, exhibit a game structure, a valuation distribution, and an inclusion-rule-respecting subgame perfect equilibrium of FPA-EQ whose expected welfare is strictly below $(1 - 1/e)$ times the expected maximum; the tightness construction of Proposition 3.12 is the natural starting point. To refute Theorem 3.1, give a DSIC and strongly BPIC mechanism that nonetheless confirms transactions with positive probability on every positive valuation profile.

Watch

Extended reading notes

Core claim

The central claim is that FPA-EQ, built from the welfare-maximizing inclusion rule, the first-price payment rule, and equal sharing of each fee among all block producers, simultaneously solves the block-producer incentive problem and achieves near-optimal welfare in leaderless protocols. Theorem 3.4 states that for every game structure and every joint valuation distribution, every subgame perfect equilibrium in which block producers follow the intended Pareto-dominant allocation has expected welfare at least $1 - 1/e \approx 63.2\%$ of the first-best, and Proposition 3.12 gives a matching example, so the bound is tight. The proof first equates such equilibria with Bayes-Nash equilibria of winner-pays-bid matroid auctions, then uses the smoothness of those auctions to derive a price-of-anarchy bound. Corollaries extend the guarantee to all subgame perfect equilibria when block producers are symmetric, and to full efficiency when users are symmetric with i.i.d. valuations. The paper also shows the compromises are inherent: no strongly block-producer-incentive-compatible mechanism with nontrivial welfare guarantees can be dominant-strategy truthful for users, and none can guarantee optimal welfare at equilibrium.

Load-bearing premise

For every user bid vector, block producers coordinate on the intended inclusion-rule-respecting and Pareto-dominant Nash equilibrium rather than some other subgame-perfect equilibrium; the paper does not model how this coordination happens.

Editorial extensions

If this is right

  • The FPA-EQ mechanism gives a concrete deployable fee rule for multi-proposer protocols: include bids to maximize total fees and split each fee equally among all block producers.
  • Every inclusion-rule-respecting equilibrium, even with arbitrarily correlated user valuations, achieves at least $63.2\%$ of the maximum possible expected welfare, and no better constant is possible in the worst case.
  • When block producers are symmetric, the $63.2\%$ floor holds for every subgame perfect equilibrium, not only those that explicitly respect the inclusion rule.
  • When both block producers are symmetric and user valuations are i.i.d., every subgame perfect equilibrium of FPA-EQ achieves the maximum possible expected welfare.
  • Any strongly BPIC mechanism with nontrivial welfare guarantees cannot be DSIC, and no strongly BPIC mechanism can guarantee optimal welfare, so the bidding shading and the $63.2\%$ floor are unavoidable trade-offs in this design space.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The FPA-EQ rule can be read as a refinement of the pro-rata fee sharing already used in some DAG-based protocols: splitting each fee equally per block contributed, rather than by stake, makes the intended inclusion rule an equilibrium with a quantitative welfare guarantee.
  • Because the smoothness proof works for correlated valuations, the $63.2\%$ floor is prior-robust; a controlled auction experiment with correlated values could test whether the inclusion-rule-respecting equilibrium selection actually arises in practice.
  • An incomplete-information extension in which block producers do not know each other's feasible sets, which the paper explicitly leaves open, would determine whether the strong BPIC guarantee survives private information.
  • The same 'game within the game' modeling could be carried over to settings where producers also pursue maximal extractable value or censorship objectives, to check whether a similar welfare floor persists under broader producer preferences.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper initiates the study of transaction fee mechanisms (TFMs) for leaderless blockchain protocols, where multiple block producers (BPs) contribute to each block. It proposes an extensive-form game model with users and BPs, defines a strong BP incentive-compatibility property (strongly BPIC), and introduces the FPA-EQ mechanism: the welfare-maximizing inclusion rule with a first-price payment rule and equal sharing of fees among BPs. The main results are that FPA-EQ is strongly BPIC, that every inclusion-rule-respecting (IRR) subgame-perfect equilibrium has expected welfare at least 1 - 1/e ~ 63.2% of the maximum, that this bound is tight, and that one cannot have strong BPIC together with DSIC or with exact optimal welfare. The analysis draws on smoothness-based price-of-anarchy bounds for matroid auctions.

Significance. If the results are correct, this is the first systematic treatment of TFM design for multi-proposer protocols, a setting of practical relevance given the deployment of DAG-based consensus protocols. The FPA-EQ mechanism is simple and its welfare guarantee is obtained through a clean reduction to winner-pays-bid matroid auctions, bringing modern price-of-anarchy tools into the TFM literature. The paper is also honest about the main caveat: the 63.2% guarantee is proved only for IRR SPE, i.e., equilibria in which BPs coordinate on the intended allocation in every subgame. Since that equilibrium-selection assumption is not microfounded, and since the abstract states the guarantee without the IRR qualifier, the practical significance of the headline bound depends on whether the qualifier can be removed or whether the abstract is revised. The impossibility results are useful context. Overall, the paper is a solid contribution to a timely topic, but the proof gaps identified below are load-bearing and need to be addressed.

major comments (3)
  1. [Abstract; Section 3.3, Theorem 3.4 and Corollary 3.11] The abstract states that FPA-EQ 'guarantees at least a 63.2% fraction of the maximum-possible expected welfare at equilibrium' without qualification. The body, however, only proves this for inclusion-rule-respecting SPE (Theorem 3.4). Corollary 3.11 asserts that in the BP-symmetric setting every SPE is IRR via 'a simple exchange argument,' but no argument is supplied. Thus the unqualified claim in the abstract is not supported. Moreover, Section 2.6 gives only a BP-subgame Nash equilibrium, not a full SPE, so the paper neither proves that non-IRR SPE with welfare below 63.2% exist nor rules them out. The authors should either prove Corollary 3.11, resolve the existence question for non-IRR SPE, and state the abstract precisely, or explicitly qualify all headline claims as applying to IRR SPE.
  2. [Section 3.2, Proposition 3.3] The proof of Proposition 3.3 claims that every BP's payoff is proportional to the total amount paid by users (and hence to the sum of included bids). This ignores the definition in Section 2.1 that a BP's payoff is revenue from transactions other than its own minus payments it makes for shill transactions. Under FPA-EQ, if a BP includes its own shill transaction with bid s, it pays s but receives only s/m from the equal-share distribution, so its net payoff is not proportional to the sum of included bids. The proof must explicitly argue that shill inclusion is never strictly profitable for a deviating BP; as written, the derivation of strong BPIC is incomplete.
  3. [Section 3.3, Lemma 3.6] Lemma 3.6, which states that every IRR SPE of the FPA-EQ extensive-form game is user-outcome-equivalent to a Bayes-Nash equilibrium of a winner-pays-bid matroid auction, is the key step connecting the TFM game to the smoothness analysis. The proof is only a two-sentence sketch: it asserts that the IRR condition makes the induced allocation rule the welfare-maximizing matroid rule and that SPE conditions for users become BNE conditions. This is not immediate because the extensive-form game has sequential moves and information sets, so a formal argument is needed to show that unilateral deviations in the single-shot auction correspond exactly to deviations in the extensive-form game. Without a full proof of Lemma 3.6, Theorem 3.4 is not rigorously established.
minor comments (5)
  1. [Throughout] There are several typos: 'valaution' and 'TGM' in Lemma 3.6; 'winners-pay-bid' for 'winner-pays-bid' in the same paragraph; 'Fron' in the sentence after Proposition 3.5; 'insiting' in Section 3.1; and a missing phrase in Section 2.6: 'BPs that coordinate on the as demonstrated by Vickrey.'
  2. [Section 3.1, Theorem 3.2] The statement of Theorem 3.2 says 'expected welfare strictly less than the minimum possible,' but the surrounding discussion makes clear that the intended wording is 'maximum possible.' Please correct this.
  3. [Section 3.3, Proof of Lemma 3.10] The application of Proposition A.4 in the proof of Lemma 3.10 is too terse. To verify the inequality sum_{i in A*} t_i(b_{-i}) <= sum_i p_i(b), the reader must infer that Proposition A.4 is applied with weights w=b, so that A* is the auction's winner set under b, and with the independent set A taken to be the welfare-optimal set under v. This should be spelled out explicitly.
  4. [Section 3.3, Proposition 3.12] The proof says 'A calculation shows' without showing the calculation. The expected-welfare computation is short and should be included so the tightness claim is directly verifiable.
  5. [Section 2.2] The extensive-form model has users move sequentially but their information sets prevent them from observing earlier bids, effectively making the user stage simultaneous. This is a reasonable modeling choice, but it should be stated explicitly and justified, since readers may otherwise wonder why the order of user moves matters.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 63.2% welfare bound follows from an explicit smoothness argument whose parameters are derived, not fitted to the conclusion.

full rationale

FPA-EQ's welfare theorem is derived rather than assumed: Lemma 3.6 maps IRR SPEs of FPA-EQ to Bayes-Nash equilibria of winner-pays-bid matroid auctions, Lemma 3.10 proves these auctions satisfy (1-1/e,1)-smoothness with private deviations using the explicit deviation distribution with density 1/(v_i-x), and Theorem 3.9 converts smoothness into the expected-welfare bound. The smoothness parameters are produced by the integral of that distribution, not calibrated to the 63.2% target, and the tightness example independently computes the welfare of a constructed equilibrium. The PoA implication is cited to Lucier and Paes Leme (2011) and Roughgarden, Syrgkanis, and Tardos (2017); the former is external and the latter is a formalism of the same external theorem, so the presence of a co-author on one citation does not carry the argument. The impossibility theorems use Myerson's theorem and revenue equivalence, and the IRR equilibrium-selection restriction is an explicitly stated modeling premise rather than a conclusion smuggled into the assumptions. No equation in the paper reduces to its own input by construction.

Assumptions & free parameters 0 free parameters · 9 assumptions · 0 invented entities

The paper's central results rest on standard mechanism-design assumptions (quasi-linear utility, common prior, matroid structure of feasible allocations, Myerson and revenue equivalence theorems, and the smoothness framework). The most substantive domain assumption is that BPs coordinate on the Pareto-dominant equilibrium. There are no fitted free parameters and no invented entities.

assumptions (9)
  • domain assumption Users have quasi-linear utilities, valuations are private, and bids are nonnegative.
    Standard mechanism design setup, stated in Section 2.1.
  • domain assumption Valuations are drawn from a common prior D, which may be correlated across users.
    Needed for Bayes-Nash equilibrium and the welfare guarantee; stated in Section 2.1.
  • domain assumption Block producers maximize net payoff: revenue from others' transactions minus payments for their own shill transactions.
    Stated in Section 2.1, but sometimes ignored later, e.g., in the proof of Proposition 3.3.
  • standard math The feasible sets of transactions that can be included in a feasible allocation form a matroid over the user set.
    Proved in Proposition A.2 via transversal matroid theory; used in Proposition 3.3 and Lemma 3.10.
  • standard math Myerson's characterization of DSIC mechanisms (monotone allocation, payment equals critical value) applies.
    Invoked in Appendix A.2 to prove Theorem 3.1.
  • standard math Revenue equivalence holds for Bayes-Nash equilibria of auctions where losers pay zero.
    Invoked in Appendix A.3 (Lemma A.6).
  • standard math Smoothness of an auction implies a price-of-anarchy bound for all Bayes-Nash equilibria (Theorem 3.9).
    Quoted from Lucier and Paes Leme [22] and Roughgarden, Syrgkanis, and Tardos [30].
  • domain assumption Block producers can coordinate on the Pareto-dominant (inclusion-rule-respecting) Nash equilibrium in every subgame.
    Essential for the welfare guarantee in Theorem 3.4; the paper notes this assumption and leaves its microfoundation to future work.
  • domain assumption Block producers have complete information about user bids and about each other's feasible transaction sets when choosing blocks.
    Stated in Section 2.2 (footnote 3); acknowledged as a limitation and possible future direction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Transaction Fee Mechanism Design for Leaderless Blockchain Protocols." pith.science (2026). https://pith.science/paper/2TQFA6B5

@misc{pith2026250517885,
  author       = {Pith},
  title        = {Pith review of: Transaction Fee Mechanism Design for Leaderless Blockchain Protocols},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2TQFA6B5}},
  note         = {Machine review of arXiv:2505.17885}
}
read the original abstract

We initiate the study of transaction fee mechanism design for blockchain protocols in which multiple block producers contribute to the production of each block. Our contributions include: - We propose an extensive-form (multi-stage) game model to reason about the game theory of multi-proposer transaction fee mechanisms. - We define the strongly BPIC property to capture the idea that all block producers should be motivated to behave as intended: for every user bid profile, following the intended allocation rule is a Nash equilibrium for block producers that Pareto dominates all other Nash equilibria. - We propose the first-price auction with equal sharing (FPA-EQ) mechanism as an attractive solution to the multi-proposer transaction fee mechanism design problem. We prove that the mechanism is strongly BPIC and guarantees at least a 63.2% fraction of the maximum-possible expected welfare at equilibrium. - We prove that the compromises made by the FPA-EQ mechanism are qualitatively necessary: no strongly BPIC mechanism with non-trivial welfare guarantees can be DSIC, and no strongly BPIC mechanism can guarantee optimal welfare at equilibrium.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 42 canonical work pages

  1. [1]

    Arun, B., Li, Z., Suri-Payer, F., Das, S., Spiegelman, A.: Shoal++: High throughput dag bft can be fast! arXiv preprint arXiv:2405.20488 (2024)

    arXiv 2024

  2. [2]

    arXiv preprint arXiv:2310.14821 (2023)

    Babel, K., Chursin, A., Danezis, G., Kokoris-Kogias, L., Sonnino, A.: Mysticeti: Low-latency dag consensus with fast commit path. arXiv preprint arXiv:2310.14821 (2023)

    arXiv 2023

  3. [3]

    In: Böhme, R., Kiffer, L

    Bahrani, M., Garimidi, P., Roughgarden, T.: Transaction fee mechanism design in a post-mev world. In: Böhme, R., Kiffer, L. (eds.) 6th Conference on Advances in Financial Technologies, AFT 2024, September 23-25, 2024, Vienna, Austria. LIPIcs, vol. 316, pp. 29:1–29:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024). https://doi.org/10.4230/LIPICS...

    doi:10.4230/lipics.aft.2024.29 2024

  4. [4]

    Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech

    Baird, L.: The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep34, 9–11 (2016)

    work page 2016

  5. [5]

    Buchman, E.: Tendermint: Byzantine fault tolerance in the age of blockchains. Ph.D. thesis, University of Guelph (2016)

    work page 2016

  6. [6]

    Buterin, V., Conner, E., Dudley, R., Slipper, M., Norden, I., Bakhta, A.: Eip-1559: Fee market change for eth 1.0 chain.https://github.com/ethereum/EIPs/blob/master/EIPS/eip-155 9.md (2024), accessed: 2024-10-10

    work page 2024

  7. [7]

    arXiv preprint arXiv:2402.09321 (2024)

    Chung, H., Roughgarden, T., Shi, E.: Collusion-resilience in transaction fee mechanism design. arXiv preprint arXiv:2402.09321 (2024)

    work page arXiv 2024

  8. [8]

    In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    Chung, H., Shi, E.: Foundations of transaction fee mechanism design. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 3856–3899. SIAM (2023)

    work page 2023

Show all 52 references
  1. [9]

    In: Proceedings of the Seventeenth European Conference on Computer Systems

    Danezis, G., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A.: Narwhal and tusk: a dag-based mempool and efficient bft consensus. In: Proceedings of the Seventeenth European Conference on Computer Systems. pp. 34–50 (2022)

    2022

  2. [10]

    In: Proceedings of the 3rd ACM Conference on Advances in Financial Technologies

    Ferreira, M.V.X., Moroz, D.J., Parkes, D.C., Stern, M.: Dynamic posted-price mechanisms for the blockchain transaction-fee market. In: Proceedings of the 3rd ACM Conference on Advances in Financial Technologies. pp. 86–99 (2021) 17

    2021

  3. [11]

    In: Bonneau, J., Weinberg, S.M

    Fox, E., Pai, M.M., Resnick, M.: Censorship resistance in on-chain auctions. In: Bonneau, J., Weinberg, S.M. (eds.) 5th Conference on Advances in Financial Technologies, AFT 2023, October 23-25, 2023, Princeton, NJ, USA. LIPIcs, vol. 282, pp. 19:1–19:20. Schloss Dagstuhl - Lei...

    2023 doi

  4. [12]

    MIT press (1991)

    Fudenberg, D., Tirole, J.: Game Theory. MIT press (1991)

    1991

  5. [13]

    arXiv preprint arXiv:2210.07793 (2022)

    Gafni, Y., Yaish, A.: Greedy transaction fee mechanisms for (non-) myopic miners. arXiv preprint arXiv:2210.07793 (2022)

    2022 arXiv

  6. [14]

    arXiv preprint arXiv:2402.08564 (2024)

    Gafni, Y., Yaish, A.: Barriers to collusion-resistant transaction fee mechanisms. arXiv preprint arXiv:2402.08564 (2024)

    2024 arXiv

  7. [15]

    In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies

    Gkagol, A., Leśniak, D., Straszak, D., Świętek, M.: Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 214–228 (2019)

    2019

  8. [16]

    In: Proceedings of the 15th ACM conference on Economics and Computation

    Hartline, J., Hoy, D., Taggart, S.: Price of Anarchy for Auction Revenue. In: Proceedings of the 15th ACM conference on Economics and Computation. pp. 693–710 (2014)

    2014

  9. [17]

    In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

    Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: All you need is dag. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. pp. 165–175 (2021)

    2021

  10. [18]

    arXiv preprint arXiv:2205.09174 (2022)

    Keidar, I., Naor, O., Poupko, O., Shapiro, E.: Cordial miners: Fast and efficient consensus for every eventuality. arXiv preprint arXiv:2205.09174 (2022)

    2022 arXiv

  11. [19]

    Academic press (2009)

    Krishna, V.: Auction Theory. Academic press (2009)

    2009

  12. [20]

    ACM Transactions on Economics and Computation10(1), 1–31 (2022)

    Lavi, R., Sattath, O., Zohar, A.: Redesigning bitcoin’s fee market. ACM Transactions on Economics and Computation10(1), 1–31 (2022)

    2022

  13. [21]

    In: Proceedings of the 3rd ACM Advances in Financial Technologies (2021)

    Leonardos, S., Monnot, B., Reijsbergen, D., Skoulakis, S., Piliouras, G.: Dynamical analysis of the EIP-1559 Ethereum fee market. In: Proceedings of the 3rd ACM Advances in Financial Technologies (2021)

    2021

  14. [22]

    In: Proceedings of the 12th ACM Conference on Electronic Commerce

    Lucier, B., Paes Leme, R.: GSP Auctions with Correlated Types. In: Proceedings of the 12th ACM Conference on Electronic Commerce. pp. 71–80 (2011)

    2011

  15. [23]

    arXiv preprint arXiv:2310.06335 (2023)

    Malkhi, D., Stathakopoulou, C., Yin, M.: Bbca-chain: One-message, low latency bft consensus on a dag. arXiv preprint arXiv:2310.06335 (2023)

    2023 arXiv

  16. [24]

    In: 4th International Conference on Blockchain Economics, Security and Protocols

    Malkhi, D., Szalachowski, P.: Maximal extractable value (mev) protection on a dag. In: 4th International Conference on Blockchain Economics, Security and Protocols. p. 1 (2023)

    2023

  17. [25]

    Nakamoto, S.: A peer-to-peer electronic cash system (2008)

    2008

  18. [26]

    Nisan, N.: Serial monopoly on blockchains (2023)

    2023

  19. [27]

    Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, USA (2006) 18

    2006

  20. [28]

    arXiv preprint arXiv:2012.00854 (2020)

    Roughgarden, T.: Transaction Fee Mechanism Design for the Ethereum Blockchain: An Eco- nomic Analysis of EIP-1559. arXiv preprint arXiv:2012.00854 (2020)

    2020 arXiv

  21. [29]

    ACM SIGecom Exchanges19(1), 52–55 (2021), full version athttps://arxiv.org/abs/2106.01340

    Roughgarden, T.: Transaction Fee Mechanism Design. ACM SIGecom Exchanges19(1), 52–55 (2021), full version athttps://arxiv.org/abs/2106.01340

    2021 arXiv

  22. [30]

    Journal of Artificial Intelligence Research59, 59–101 (2017)

    Roughgarden, T., Syrgkanis, V., Tardos, E.: The Price of Anarchy in Auctions. Journal of Artificial Intelligence Research59, 59–101 (2017)

    2017

  23. [31]

    arXiv preprint arXiv:2209.14462 (2022)

    Shi, E., Chung, H., Wu, K.: What can cryptography do for decentralized mechanism design. arXiv preprint arXiv:2209.14462 (2022)

    2022 arXiv

  24. [32]

    Cryptology ePrint Archive (2024)

    Shrestha, N., Shrothrium, R., Kate, A., Nayak, K.: Sailfish: Towards improving latency of dag-based bft. Cryptology ePrint Archive (2024)

    2024

  25. [33]

    arXiv preprint arXiv:2306.03058 (2023)

    Spiegelman, A., Arun, B., Gelashvili, R., Li, Z.: Shoal: Improving dag-bft latency and robust- ness. arXiv preprint arXiv:2306.03058 (2023)

    2023 arXiv

  26. [34]

    In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

    Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L.: Bullshark: Dag bft protocols made practical. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. pp. 2705–2718 (2022)

    2022

  27. [35]

    arXiv preprint arXiv:2209.05633 (2022)

    Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L.: Bullshark: the partially synchronous version. arXiv preprint arXiv:2209.05633 (2022)

    2022 arXiv

  28. [36]

    Sui Foundation: Sui Consensus Architecture.https://docs.sui.io/concepts/sui-archite cture/consensus (2024), accessed: 2024-10-09

    2024

  29. [37]

    Syrgkanis, V.: Efficiency of Mechanisms in Complex Markets. Ph.D. thesis, Cornell University (2014)

    2014

  30. [38]

    In: Proceedings of the 45th annual ACM Symposium on Theory of Computing

    Syrgkanis, V., Tardos, E.: Composable and efficient mechanisms. In: Proceedings of the 45th annual ACM Symposium on Theory of Computing. pp. 211–220 (2013)

    2013

  31. [39]

    https://ethresear.ch/t/fork-choice-enforce d-inclusion-lists-focil-a-simple-committee-based-inclusion-list-proposal/19870 (2024)

    Thomas, Barnabe, Francesco, Julian: Fork-choice enforced inclusion lists (focil): A simple committee-based inclusion list proposal. https://ethresear.ch/t/fork-choice-enforce d-inclusion-lists-focil-a-simple-committee-based-inclusion-list-proposal/19870 (2024)

    2024

  32. [40]

    The Journal of finance 16(1), 8–37 (1961)

    Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance 16(1), 8–37 (1961)

    1961

  33. [41]

    Wood, G.: Ethereum: A secure decentralised generalised transaction ledger.https://ethere um.github.io/yellowpaper/paper.pdf (2014), accessed: 2024-10-10

    2014

  34. [42]

    In: Guruswami, V

    Wu, K., Shi, E., Chung, H.: Maximizing miner revenue in transaction fee mechanism design. In: Guruswami, V. (ed.) 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA. LIPIcs, vol. 287, pp. 98:1–98:23. Schlos...

    2024

  35. [43]

    Yakovenko, A.: Multiple concurrent leaders.https://x.com/aeyakovenko/status/1810222 589991583922 (2024), accessed: 10, 11, 2024

    2024

  36. [44]

    In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (2020)

    Yao, A.C.C.: An incentive analysis of some Bitcoin fee designs. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (2020)

    2020

  37. [45]

    Cryptology ePrint Archive, Paper 2024/1496 (2024),https://eprint.iacr.org/2024/1496

    Zhang, J., Kate, A.: No fish is too big for flash boys! frontrunning on DAG-based blockchains. Cryptology ePrint Archive, Paper 2024/1496 (2024),https://eprint.iacr.org/2024/1496

    2024

  38. [46]

    Zhao, Z., Chen, X., Zhou, Y.: Bayesian-Nash-incentive-compatible mechanism for blockchain transaction fee allocation. arXiv preprint arXiv:2209.13099 (2022) A Supplementary Material for Section 3 A.1 Review of Relevant Matroid Theory The matroid structure of feasible allocatio...

    2022 arXiv

  39. [47]

    (Downward closure) IfA′ ∈ Iand A ⊆ A′, then A ∈ I

  40. [48]

    revenue covering

    (Exchange property) If A, A′ ∈ Iwith |A′| > |A|, then there exists x ∈ A′ \ A such that A ∪ {x} ∈ I. For a game structure(I, J,S), call a subsetA ⊆ I of transactionsfeasibleif there exists a feasible allocation (B1, . . . , Bm) that includes precisely the transactions inA. Pro...

  41. [49]

    Suppose in I1 that bidder 2, wheneverv2 > 3 4, chooses a random sample a ∼ Uniform([0, 100]) and then plays σ′ 2(a) instead of σ2(v2)

    Deviation of bidder 2 in instanceI1. Suppose in I1 that bidder 2, wheneverv2 > 3 4, chooses a random sample a ∼ Uniform([0, 100]) and then plays σ′ 2(a) instead of σ2(v2). Call this strategy ˜σ2(·) If σ is indeed a BNE inI1, this deviation cannot increase bidder 2’s expected u...

  42. [50]

    For σ to remain an equilibrium, we must therefore have Pr x σ1(v1), σ′ 2(a) = 2 < 1 25

    Under σ, bidder 2’s expected utility is Ev1 u2 σ1(v1), σ2( 7 8 ) = Pr v1 < 7 8 × 7 16 < 1 200 , By deviating to the ˜σ2 by sampling a and playing σ′ 2(a), bidder 2’s expected utility when v2 = 7 8 is Ev1,a u2 σ1(v1), σ′ 2(a) = Pr x σ1(v1), σ′ 2(a) = 2 × 1 8 . For σ to remain a...

  43. [51]

    Next, suppose in I2 that bidder 1, wheneverv1 > 1 2, samples b ∼ Uniform([0, 100]) and plays σ1(b) from instance I1

    Deviation of bidder 1 in instanceI2. Next, suppose in I2 that bidder 1, wheneverv1 > 1 2, samples b ∼ Uniform([0, 100]) and plays σ1(b) from instance I1. From the probability bound above, whenever v1 > 1 2 the probability that bidder 1 wins againstσ′ 2(v2) is at least 24

  44. [52]

    In particular, at v1 = 3 4, bidder 1’s expected utility from this deviation is at least 3 4 − 1 2 × 24 25 = 6 25 , which is substantially larger than the at most 1 100 expected utility bidder 1 achieves under playing σ′ 1, contradicting σ′ being a Bayes–Nash equilibrium. 23 Si...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.