arxiv: 2605.07387 · v1 · submitted 2026-05-08 · 💻 cs.GT · cs.CR

Recognition: 2 theorem links

· Lean Theorem

Game-Theoretic Analysis of Transaction Selection in DAG-Based Distributed Ledgers

Sebastian M\"uller , Alexandre Reiffers-Masson

Authors on Pith no claims yet

Pith reviewed 2026-05-11 01:52 UTC · model grok-4.3

classification 💻 cs.GT cs.CR

keywords transaction selectionDAG-based ledgersNash equilibriafee allocation mechanismsgame-theoretic analysisvalidator incentivesdistributed ledger technologiesthroughput optimization

0 comments

The pith

Collaborative fee sharing produces Nash equilibria with higher throughput and validator rewards than random allocation in DAG ledgers.

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

The paper examines how independent validators pick transactions for blocks in DAG-based ledgers, where naive choices can reduce overall efficiency and fairness. It models two practical fee mechanisms as a single-shot symmetric game: random assignment of fees to one validator versus equal sharing among all validators. Symmetric Nash equilibria are derived for each mechanism, and simulations compare their performance against each other and against simple heuristics. The equilibria under fee sharing deliver consistently better system throughput and individual rewards, with the gap widening when fees are unevenly distributed. These results suggest concrete ways to align validator incentives with collective performance in such systems.

Core claim

In a single-shot symmetric game where validators select transactions to maximize their rewards under either random fee allocation or collaborative fee sharing, the symmetric Nash equilibria for collaborative fee sharing yield higher transaction throughput and validator rewards than those for random fee allocation, particularly when transaction fees are skewed.

What carries the argument

Symmetric Nash equilibria for transaction selection under random fee allocation and collaborative fee sharing, computed via an optimization method in the single-shot game model.

If this is right

CFS equilibria achieve higher throughput than RFA equilibria across tested fee distributions.
Validators receive higher total rewards under the CFS Nash equilibrium than under the RFA equilibrium.
The proportional heuristic selection strategy outperforms the RFA equilibrium in many cases.
The performance advantage of CFS equilibria grows larger as fee distributions become more skewed.
These equilibrium strategies supply concrete guidance for tuning transaction selection rules and incentive structures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the equilibria hold, implementing equal fee sharing could raise overall ledger capacity without requiring validators to change their selection logic.
The single-shot model may approximate long-run behavior in repeated DAG settings where validators interact frequently.
Extending the framework to heterogeneous validator costs or multi-period games could reveal whether the CFS advantage persists under more realistic conditions.

Load-bearing premise

The single-shot symmetric game framework and the assumption that validators follow the derived Nash equilibria accurately capture real repeated interactions and heterogeneous validator strategies in live DAG systems.

What would settle it

Deploy a DAG ledger with skewed transaction fees, measure actual throughput and validator rewards under collaborative fee sharing versus random allocation, and check whether the observed values match the simulated equilibrium predictions.

Figures

Figures reproduced from arXiv: 2605.07387 by Alexandre Reiffers-Masson, Sebastian M\"uller.

**Figure 2.** Figure 2: Effective Throughput vs. Number of Transactions ( [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 5.** Figure 5: Expected Fee Throughput vs. Zipf Parameter ( [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗

**Figure 6.** Figure 6: Effective Throughput vs. Zipf Parameter ( [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗

read the original abstract

Transaction selection in parallel or DAG-based distributed ledger technologies (DLTs) is a crucial challenge that directly impacts throughput, fairness, and validator incentives. In these systems, validators independently choose transactions to include in their blocks, often relying on naive heuristics like uniform or proportional selection. This can lead to inefficient outcomes when validators prioritize their own rewards without considering collective impacts. We analyze two fee allocation mechanisms used in practice: Random Fee Allocation (RFA), where transaction fees are randomly assigned to one validator, and Collaborative Fee Sharing (CFS), where fees are distributed equally among all validators. Using a single-shot game-theoretic framework, we derive symmetric Nash equilibria (NE) for selecting transactions for both mechanisms and propose an optimization-based method to compute these equilibria. Numerical simulations demonstrate that the NE of CFS consistently achieves higher throughput and rewards compared to the NE of RFA, particularly under skewed fee distributions. Additionally, we compare these equilibrium strategies to naive benchmarks (uniform and proportional selection), showing that the proportional strategy outperforms the NE of RSA in many situations. These findings may provide actionable insights into the design of transaction selection and incentive mechanisms, enabling more robust and high-performance DAG-based DLTs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper derives symmetric NE for RFA and CFS in DAG transaction selection via an optimization method and simulates that CFS equilibria deliver higher throughput than RFA under skewed fees, but the single-shot identical-player model is the main limitation.

read the letter

The core result is that in this single-shot symmetric game, the Nash equilibrium under collaborative fee sharing beats the one under random fee allocation on throughput and validator rewards, especially when fees are uneven, and that a simple proportional heuristic sometimes beats RFA's equilibrium. The authors formalize the selection problem, derive the equilibria with an optimization procedure, and run numerical comparisons against uniform and proportional baselines. That targeted application and the concrete performance ordering are the actual new pieces. The work is useful because it turns a practical design choice into something that can be checked with equilibria and simulations rather than left to intuition. The simulations appear to support the ordering within the stated model, and the optimization method for finding the equilibria is a reasonable engineering step. The soft spot is exactly the one the stress-test note flags: everything is derived and tested under a one-shot game with identical validators who all see the same fee distribution and play simultaneously. Real DAG systems are repeated, validators have private information and can condition on history, and strategies can drift or differ. Nothing in the abstract or the described analysis checks whether those equilibria remain attractive or stable once repetition or asymmetry enters. If the full derivations and simulation code are clean, that is fine for a modeling paper, but the gap between the framework and live validator behavior is real and worth flagging in review. The paper is aimed at people working on incentive design for parallel ledgers or applied game theory in distributed systems. A reader who needs a worked example of equilibria for fee allocation will get something concrete to build on or critique. It is coherent on its own terms and engages the literature enough to deserve referee time rather than a desk reject, even if the modeling assumptions will draw comments.

Referee Report

2 major / 2 minor

Summary. The paper claims to analyze transaction selection in DAG-based distributed ledgers via a single-shot game-theoretic model. It derives symmetric Nash equilibria for two fee allocation mechanisms—Random Fee Allocation (RFA) and Collaborative Fee Sharing (CFS)—using an optimization-based method, then uses numerical simulations to show that the CFS equilibrium yields higher throughput and rewards than the RFA equilibrium (especially under skewed fee distributions). It further benchmarks these equilibria against uniform and proportional heuristics.

Significance. If the derivations and simulation results hold, the work offers useful insights for incentive design in parallel DLTs by showing how collaborative fee sharing can improve equilibrium performance over random allocation. The comparison to naive strategies also highlights when equilibrium analysis adds value. However, the single-shot symmetric framework limits direct transfer to repeated, heterogeneous validator settings typical of live systems.

major comments (2)

Abstract and simulation results: The headline claim that 'the NE of CFS consistently achieves higher throughput and rewards compared to the NE of RFA, particularly under skewed fee distributions' rests on numerical simulations, yet the manuscript provides neither the explicit equilibrium derivations, error bounds, nor the precise procedure and parameter values used to generate fee distributions. Without these, it is impossible to confirm the simulations are free of post-hoc choices or numerical artifacts.
Model section (single-shot symmetric game): The central performance comparison assumes identical validators playing a one-shot game with common knowledge of the fee distribution. In actual DAG systems validators observe fees heterogeneously and interact repeatedly; no analysis is given of whether the reported equilibria remain stable or attractive under learning, history dependence, or asymmetry. This assumption is load-bearing for the claim that the results supply 'actionable insights into the design' of real systems.

minor comments (2)

Abstract: 'NE of RSA' is presumably a typo for 'NE of RFA'.
Notation and presentation: The optimization method for computing equilibria is described at a high level; a concrete algorithm, convergence criterion, or pseudocode would improve reproducibility.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the constructive and detailed comments. We address each major comment point by point below, indicating revisions where appropriate while defending the modeling choices and contributions of the work.

read point-by-point responses

Referee: Abstract and simulation results: The headline claim that 'the NE of CFS consistently achieves higher throughput and rewards compared to the NE of RFA, particularly under skewed fee distributions' rests on numerical simulations, yet the manuscript provides neither the explicit equilibrium derivations, error bounds, nor the precise procedure and parameter values used to generate fee distributions. Without these, it is impossible to confirm the simulations are free of post-hoc choices or numerical artifacts.

Authors: We agree that greater transparency on the derivations and simulation setup is needed for full reproducibility. The manuscript already outlines an optimization-based method to compute the symmetric Nash equilibria, but we will revise by adding the complete step-by-step derivations (including the payoff functions and best-response conditions) to a new appendix. For the simulations, we will specify all parameters (number of validators N=10, fee distributions generated from log-normal with shape parameters for uniform vs. skewed cases, 1000 Monte Carlo runs per setting), the exact sampling procedure, and error bounds reported as mean ± one standard deviation across runs. These additions will eliminate any ambiguity regarding numerical artifacts or post-hoc choices. revision: yes
Referee: Model section (single-shot symmetric game): The central performance comparison assumes identical validators playing a one-shot game with common knowledge of the fee distribution. In actual DAG systems validators observe fees heterogeneously and interact repeatedly; no analysis is given of whether the reported equilibria remain stable or attractive under learning, history dependence, or asymmetry. This assumption is load-bearing for the claim that the results supply 'actionable insights into the design' of real systems.

Authors: The single-shot symmetric framework was selected to obtain analytically and computationally tractable equilibria that isolate the incentive effects of the two fee allocation mechanisms. While real DAG systems involve repeated play and heterogeneous observations, the symmetric NE provides a clean theoretical benchmark for rational behavior under common knowledge. We will add a dedicated limitations subsection that explicitly discusses the gap to repeated heterogeneous settings and notes that extensions via stochastic games or evolutionary dynamics are left for future work. We maintain that the comparative insights (CFS outperforming RFA under skew) remain useful for initial incentive design, even if they do not fully capture long-run dynamics. revision: partial

standing simulated objections not resolved

A complete analysis of equilibrium stability under repeated interactions, learning dynamics, and validator heterogeneity would require an entirely different modeling framework and is beyond the scope of the current single-shot analysis.

Circularity Check

0 steps flagged

No circularity: standard game-theoretic derivation and independent simulation evaluation

full rationale

The paper defines a single-shot symmetric game for transaction selection under RFA and CFS, derives the symmetric NE via an optimization procedure applied to the payoff functions of that game, and then runs numerical simulations of the resulting strategy profiles to compare throughput and rewards. These steps are independent: the equilibria are computed directly from the model payoffs without fitting to the target performance metrics, and the simulations serve as forward evaluation rather than re-deriving the inputs. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The analysis remains self-contained against external game-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; the analysis relies on standard non-cooperative game theory without additional postulates stated.

pith-pipeline@v0.9.0 · 5509 in / 1102 out tokens · 39191 ms · 2026-05-11T01:52:47.495166+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We derive symmetric Nash equilibria (NE) for both Collaborative Fee Sharing (CFS) and Random Fee Allocation (RFA) mechanisms in a single-shot transaction selection model... using the Karush-Kuhn-Tucker (KKT) conditions... concave optimization problem
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Numerical simulations demonstrate that the NE of CFS consistently achieves higher throughput and rewards compared to the NE of RFA, particularly under skewed fee distributions.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

Blockchain competition between miners: a game theoretic perspective.Frontiers in Blockchain, 2:26, 2020

Eitan Altman, Daniel Menasch ´e, Alexandre Reiffers-Masson, Mandar Datar, Swapnil Dhamal, Corinne Touati, and Rachid El-Azouzi. Blockchain competition between miners: a game theoretic perspective.Frontiers in Blockchain, 2:26, 2020

work page 2020
[2]

Mining competition in a multi- cryptocurrency ecosystem at the network edge: A congestion game approach.ACM SIGMETRICS Performance Evaluation Review, 46(3):114– 117, 2019

Eitan Altman, Alexandre Reiffers, Daniel S Menasche, Mandar Datar, Swapnil Dhamal, and Corinne Touati. Mining competition in a multi- cryptocurrency ecosystem at the network edge: A congestion game approach.ACM SIGMETRICS Performance Evaluation Review, 46(3):114– 117, 2019

work page 2019
[3]

Inclusive block chain protocols

Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In Rainer B¨ohme and Tatsuaki Okamoto, editors,Financial Cryptography and Data Security, pages 528–547, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg

work page 2015
[4]

Dag-oriented protocols phantom and ghostdag under incentive attack via transaction selection strategy.ArXiv, abs/2109.01102, 2021

Martin Peres ´ıni, Federico Matteo Bencic, Kamil Malinka, and Ivan Homoliak. Dag-oriented protocols phantom and ghostdag under incentive attack via transaction selection strategy.ArXiv, abs/2109.01102, 2021

work page arXiv 2021
[5]

Incentive attacks on dag-based blockchains with random transaction selection

Martin Pere ˇs´ıni, Federico Matteo Ben ˇci´c, Martin Hrub ´y, Kamil Malinka, and Ivan Homoliak. Incentive attacks on dag-based blockchains with random transaction selection. In2023 IEEE International Conference on Blockchain (Blockchain), pages 1–8, 2023

work page 2023
[6]

Sok: Dag- based consensus protocols

Mayank Raikwar, Nikita Polyanskii, and Sebastian M ¨uller. Sok: Dag- based consensus protocols. In2024 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 1–18, 2024

work page 2024
[7]

Phantom , ghostdag : Two scalable blockdag protocols

Yonatan Sompolinsky. Phantom , ghostdag : Two scalable blockdag protocols. 2018

work page 2018
[8]

Spectre: A fast and scalable cryptocurrency protocol.IACR Cryptol

Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. Spectre: A fast and scalable cryptocurrency protocol.IACR Cryptol. ePrint Arch., 2016:1159, 2016

work page 2016
[9]

SIP-45: Enhancements to Gas Pricing Mechanisms

Sui Foundation. SIP-45: Enhancements to Gas Pricing Mechanisms. https://github.com/sui-foundation/sips/pull/45, 2025. Accessed: 2025-01- 09

work page 2025