💻 computer science

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

This paper employs a game-theoretic framework to demonstrate that a Collaborative Fee Sharing mechanism yields superior throughput and validator rewards compared to Random Fee Allocation and naive selection heuristics in DAG-based distributed ledgers by deriving optimal transaction selection strategies at Nash equilibrium.

Original authors: Sebastian Müller, Alexandre Reiffers-Masson

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sebastian Müller, Alexandre Reiffers-Masson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling digital marketplace where a group of independent workers (called validators) are competing to pack a limited number of items (called transactions) into their own delivery trucks (called blocks). Each item has a price tag (a fee) attached to it. The goal is to pack as many high-value items as possible to earn the most money, but there's a catch: if two workers pack the exact same item, it creates a "traffic jam" or a collision. In this system, a collision wastes space and money because the item only needs to be delivered once.

This paper uses game theory (the study of strategic decision-making) to figure out the smartest way for these workers to pick their items without talking to each other. The authors compare two different ways the system pays out the fees when collisions happen.

Here is the breakdown of their findings using simple analogies:

The Two Payment Rules

The researchers tested two different "house rules" for how the money is split when multiple workers pick the same item:

The "Lucky Winner" Rule (Random Fee Allocation - RFA):
- How it works: If three workers pick the same expensive item, only one of them gets the full prize, chosen completely at random. The other two get nothing.
- The Analogy: Imagine a raffle. If you and two friends all buy a ticket for the same prize, only one of you wins the jackpot. The others walk away empty-handed.
- The Result: This creates a "race to the top." Everyone tries to grab the most expensive items first, hoping to be the lucky winner. However, this leads to massive collisions. Everyone fights for the same few high-value items, leaving many cheaper items untouched and wasting a lot of truck space on duplicates.
The "Potluck" Rule (Collaborative Fee Sharing - CFS):
- How it works: If at least one worker picks an item, the fee for that item is split equally among all the workers, regardless of who actually picked it.
- The Analogy: Imagine a potluck dinner. If someone brings a dish, everyone at the table gets a serving. It doesn't matter who brought it; everyone shares the meal.
- The Result: This changes the strategy completely. Since you get paid even if someone else picks the item, you don't need to fight as hard for the expensive ones. You are happy to pick a mix of items. This reduces the traffic jams (collisions) because workers naturally spread out to cover more ground.

The "Smart" Strategy (Nash Equilibrium)

In game theory, a Nash Equilibrium is a state where everyone is playing their best possible move, given what everyone else is doing. No one can get richer by changing their strategy alone.

The authors used math to calculate exactly how a rational worker should pick items under both rules. They found that:

Under the "Potluck" (CFS) rule: The smartest strategy leads to a system that collects the most total money (fee throughput) and includes a good variety of items. It's the most efficient way to run the marketplace.
Under the "Lucky Winner" (RFA) rule: The smartest strategy leads to a chaotic scramble. While it might seem fair to let people choose freely, the math shows it actually results in less total money collected and a lot of wasted space on duplicate items.

The Surprising Twist: "Proportional" vs. "Smart"

The paper also looked at a "naive" strategy that people might use without doing complex math: Proportional Selection. This is where a worker picks items based on how expensive they are (picking the $100 item 10 times more often than the $10 item).

The Finding: In the "Lucky Winner" (RFA) scenario, this simple "Proportional" strategy actually performs better than the complex, mathematically perfect "Smart" strategy.
Why? The "Smart" strategy in the RFA game gets so bogged down in trying to avoid collisions that it becomes too cautious. The simple "Proportional" approach is just aggressive enough to grab value without overthinking the math.

The Bottom Line

If you want maximum profit and efficiency: Use the Collaborative Fee Sharing (CFS) rule. It encourages workers to cooperate (even without talking) and fills the trucks with a diverse, high-value load.
If you use the "Lucky Winner" (RFA) rule: The system is inherently inefficient. Even the smartest players end up in a traffic jam. In this specific case, a simple "pick based on price" rule is actually a better shortcut than trying to calculate the perfect game-theoretic strategy.

The authors conclude that for future digital ledgers (like the ones used in cryptocurrencies), designing the payment rules to encourage sharing (CFS) is far superior to designing them to encourage a free-for-all race (RFA).

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

Problem Statement
In DAG-based distributed ledger technologies (DLTs), multiple validators propose blocks concurrently to improve throughput. However, this parallelism introduces the challenge of transaction collisions, where multiple validators select the same transaction, leading to inefficiencies as redundant inclusions do not increase system utility. Current systems often rely on naive heuristics for transaction selection, such as uniform or proportional selection, without rigorously analyzing whether these strategies constitute Nash equilibria (NE) under specific fee allocation mechanisms. Furthermore, the interaction between fee distribution models and validator incentives in a decentralized, non-cooperative setting remains under-examined. This paper addresses the gap by deriving the symmetric mixed Nash equilibria for transaction selection strategies under two distinct fee allocation mechanisms and evaluating their performance against naive benchmarks.

Methodology
The authors model the transaction selection process as a single-shot game (myopic model) involving $N$ validators and a finite pool of $m$ transactions with varying fees. Each validator selects a subset of $b$ transactions to include in their block. The study focuses on two fee allocation mechanisms:

Random Fee Allocation (RFA): If multiple validators include a transaction, the fee is randomly assigned to exactly one of them. This mechanism is typical of Proof-of-Work (PoW) systems with total ordering (e.g., GHOSTDAG).
Collaborative Fee Sharing (CFS): If at least one validator includes a transaction, the fee is distributed equally among all $N$ validators. This mechanism is more typical of Byzantine Fault Tolerance (BFT)-like protocols.

The authors employ a game-theoretic framework to derive symmetric Nash equilibria. They first establish a general theoretical result (Theorem IV.1) characterizing the NE using a strictly decreasing function $f(p)$ representing the expected share of rewards. Recognizing that directly inverting $f(p)$ for RFA is computationally intensive, the paper proposes an efficient optimization-based approach using the Karush-Kuhn-Tucker (KKT) conditions. This transforms the equilibrium derivation into a concave optimization problem solvable via projected gradient descent.

The performance of the derived equilibria is evaluated numerically against two naive benchmarks:

Random Transaction Selection (RTS): Uniform selection.
Proportional Transaction Selection (PTS): Selection probability proportional to transaction fees.

Metrics include Effective Transaction Throughput (expected number of unique transactions included) and Effective Fee Throughput (total expected rewards collected). Simulations utilize a Zipf-like fee distribution to model skewed fee structures.

Key Contributions

Derivation of Symmetric Nash Equilibria: The paper provides the first explicit derivation of symmetric mixed Nash equilibria for both RFA and CFS models in a single-shot transaction selection game.
Efficient Computation Method: The authors introduce a concave optimization framework using KKT conditions to compute these equilibria efficiently, overcoming the computational intractability of direct inversion methods, particularly for the RFA model.
Comparative Performance Analysis: Through numerical simulations, the study demonstrates that the NE of the Collaborative Fee Sharing (CFS) mechanism consistently achieves higher fee throughput and rewards compared to the NE of Random Fee Allocation (RFA), especially under skewed fee distributions.
Benchmarking Naive Strategies: The analysis reveals that while CFS-NE is optimal for fee revenue, the Proportional Transaction Selection (PTS) heuristic often outperforms the RFA-NE in terms of rewards. In scenarios where CFS is not feasible (e.g., permissionless PoW systems), PTS serves as a robust alternative that can approach the performance of the RFA equilibrium.

Results
Numerical evaluations under varying parameters (number of transactions, maximum fee, and fee skewness) yield the following insights:

Fee Throughput: The CFS equilibrium consistently maximizes fee throughput across all tested scenarios. The PTS strategy also performs well, significantly outperforming the RFA equilibrium. Conversely, the RFA equilibrium often yields lower fee throughput than even the uniform (RTS) strategy.
Transaction Throughput: A trade-off exists between fee maximization and transaction diversity. The uniform strategy (RTS) achieves the highest effective transaction throughput by minimizing collisions through even probability distribution. However, this comes at the cost of lower fee throughput. The CFS equilibrium, while maximizing fees, results in the lowest effective transaction throughput because validators concentrate on high-fee transactions, leading to higher collision rates for those specific items.
Impact of Skewness: As fee distributions become more skewed (higher Zipf parameter), the performance gap widens. CFS and PTS maintain superior fee throughput, while RFA struggles, highlighting its inefficiency in handling diverse fee structures.

Significance and Claims
The paper claims that its findings provide actionable insights for the design of transaction selection and incentive mechanisms in DAG-based DLTs. By characterizing the Nash equilibria, the authors demonstrate that intuitive strategies (like uniform selection) are not always optimal and that the choice of fee allocation mechanism fundamentally alters validator behavior and system performance.

Specifically, the work suggests that:

CFS is superior for revenue: If the primary goal is maximizing fee revenue, CFS with its corresponding equilibrium strategy is the most effective mechanism.
RFA has inherent inefficiencies: The RFA mechanism, common in PoW systems, leads to equilibria that can be outperformed by simple heuristics like proportional selection, indicating a misalignment between individual incentives and collective welfare in such designs.
Practical Heuristics: For protocols where CFS is not feasible (e.g., due to the lack of a known validator set in permissionless environments), proportional selection offers a valuable heuristic that approximates the equilibrium performance of RFA without requiring complex equilibrium computation.

The authors maintain a modest scope, acknowledging that the study is limited to a single-shot model with static fees and homogeneous latencies. They note that extending this analysis to multi-round, sequential games with dynamic fees and heterogeneous network conditions remains a necessary step for real-world applicability. The paper does not propose new protocol implementations but rather provides a theoretical and numerical foundation for evaluating existing and future incentive structures.

The Two Payment Rules

The "Smart" Strategy (Nash Equilibrium)

The Surprising Twist: "Proportional" vs. "Smart"

The Bottom Line

More like this