🔢 mathematics

Asymptotic Analysis for Pure Dominated Strategy in Random Games

This paper introduces the concept of *q-Portion* dominated strategies to establish sharp asymptotic thresholds for the existence of large-scale strategic elimination in random games, while also proposing an efficient, distribution-free algorithm for detecting such strategies.

Original authors: Xihao Song

Published 2026-08-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xihao Song

Original paper licensed under CC BY 4.0 (https://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

In the study of strategic decision-making, a fundamental concept is the idea of a "dominated strategy." Imagine a person facing a menu of choices where one option is guaranteed to yield a worse outcome than another, no matter what the other people involved decide to do. In such a case, a rational person would simply discard the inferior option. This process of elimination is a cornerstone of game theory, a field that models how individuals interact when their outcomes depend on one another. For decades, researchers have understood that in small, simple scenarios, finding and removing these bad choices is straightforward. However, the real world often presents decision-makers with overwhelming complexity, involving thousands of possible actions and rapidly changing conditions where exact outcomes are impossible to predict. To make sense of this chaos, scientists often turn to "random games," a mathematical model where the potential rewards for every choice are drawn from a distribution, simulating an environment of pure uncertainty. The central question for modern researchers is whether this process of elimination remains useful when the number of choices becomes massive, or if the sheer volume of options makes the concept of a "bad choice" disappear into statistical noise.

A researcher has investigated this question, moving beyond the traditional focus on finding a single bad choice to ask a more practical question: in a game with thousands of strategies, can we eliminate a significant fraction of them at once? The study introduces a new perspective called "q-portion dominated strategies." Instead of looking for just one strategy that is worse than another, the researcher asked whether a non-trivial chunk of the available options—say, ten percent or twenty percent—could be identified as inferior and removed in a single step. They analyzed large random games where the number of strategies for each player grows very large, and the rewards for every combination of choices are determined by chance. Their work reveals that the answer depends entirely on the balance between the number of choices available to the players. If the number of strategies for one player grows too slowly relative to the other, the game remains too balanced, and almost no strategies can be eliminated. However, if one player has a vastly larger set of options than the other, the mathematics shifts dramatically, making it almost certain that a large portion of the weaker strategies will be dominated by a single, superior option.

The researcher established precise thresholds that determine when this large-scale elimination becomes possible. They found that if the number of strategies for one player grows at a rate that is roughly proportional to the logarithm of the other player's strategies, the probability of finding any dominated strategies drops to zero. In these balanced, large-scale environments, the "curse of dimensionality" takes over; the sheer number of possible scenarios makes it statistically unlikely that one choice will consistently outperform another across the board. Consequently, the classic method of simplifying a game by removing bad choices becomes ineffective. However, the study also identified a different regime where the game becomes unbalanced. When one player's strategy space expands much faster than the other's, the probability that a large fraction of strategies are dominated converges to one. In these scenarios, the researcher proved that a single strong strategy can dominate a whole block of weaker ones, allowing for a massive reduction in complexity. This finding is significant because it suggests that in highly unbalanced competitive environments, decision-makers can still rely on the logic of elimination to simplify their choices, even when the total number of options is enormous.

To make these theoretical insights useful for real-world computation, the researcher also developed a new method for detecting these dominated strategies. The standard approach to checking if one strategy is worse than another involves comparing every single outcome of one choice against every outcome of another, a process that becomes painfully slow as the number of choices increases. The new algorithm proposed in the paper uses a simple shortcut based on the highest and lowest possible rewards for each strategy. Before performing any detailed comparisons, the method first identifies the best-case and worst-case outcomes for every option. If the worst possible outcome of one strategy is still better than the best possible outcome of another, the inferior strategy is immediately identified as dominated without needing to check the middle ground. Conversely, if the ranges of their outcomes overlap in a specific way, the method can often rule out dominance without a full comparison. The researcher demonstrated that this approach allows the computer to skip the detailed, element-by-element comparison for roughly half of all the pairs it checks. While the theoretical worst-case speed of the algorithm remains the same as older methods, the practical speedup is substantial because it avoids unnecessary work in the majority of cases. Furthermore, the way this new method accesses data is more efficient for modern computer processors, reducing the time spent waiting for information to be retrieved from memory.

The study concludes by mapping out the landscape of strategic elimination in large random games. It confirms that in balanced, large-scale games, the hope of finding dominated strategies is largely unfounded, and the game remains complex and resistant to simplification. However, in unbalanced scenarios, the rules change, and large-scale pruning becomes not only possible but probable. The research provides a unified view that connects the classical idea of eliminating a single bad choice with the modern reality of managing vast decision spaces. By defining the exact conditions under which a large fraction of strategies can be discarded, the work offers both a theoretical boundary for when simplification is possible and a practical tool for achieving it. The findings suggest that while the complexity of the modern world often defies simple reduction, there are specific structural imbalances where rational decision-makers can still find clarity by identifying and removing the weakest links in their chain of options.

Technical Summary: Asymptotic Analysis for Pure Dominated Strategy in Random Games

Problem Statement
This paper investigates the asymptotic existence and prevalence of strictly dominated strategies in large two-player random games. In such games, payoffs are drawn independently and identically from a given distribution. The study addresses three core challenges:

Theoretical Existence: Determining the sharp asymptotic thresholds for the existence of a nontrivial fraction ( $q$ -portion) of dominated strategies as the strategy spaces ( $M$ for the row player, $N$ for the column player) grow to infinity.
Relation to Classical Results: Clarifying how these thresholds relate to the classical question of whether any strictly dominated strategy exists, specifically testing conjectures by Alon, Rudov, and Yariv (2021) regarding sharp transitions in dominance probabilities.
Computational Efficiency: Developing a practical, distribution-free algorithm to detect dominated strategies that improves upon the standard $O(M^2N)$ brute-force approach by exploiting payoff extrema.

Methodology
The analysis relies on probabilistic methods and asymptotic analysis within the framework of random games (Goldman 1957).

Definitions: The paper introduces $q$ -Portion dominated strategies, defined as a subset of size $\lceil qM \rceil$ where every strategy in the subset is strictly dominated by some other strategy.
Probabilistic Bounds:
- Negative Results: The non-existence of $q$ -portion dominated strategies is established using binomial coefficient approximations.
- Positive Results: The existence of such strategies is proven using Chernoff bounds. The analysis separates events into the existence of "weak" rows (all entries below a threshold) and "strong" rows (all entries above a threshold).
Distribution Parameter ( $\rho$ ): The results are parameterized by $\rho$ , the reciprocal of the probability that one randomly drawn payoff exceeds another ( $\rho = [P(X_s > X_{s'})]^{-1}$ ). For non-atomic distributions, $\rho=2$ ; for distributions with atoms, $\rho > 2$ .
Algorithmic Approach: The proposed algorithm (Algorithm 2) utilizes a preprocessing step to compute the minimum and maximum of each payoff vector. It then applies logical checks based on the ordering of these extrema to determine dominance without full element-wise comparison.

Key Contributions and Results

1. Asymptotic Thresholds for $q$ -Portion Dominance
The paper establishes sharp conditions governing the existence of a $q$ -portion of dominated strategies:

Non-Existence Regime: If $N \geq M / (\ln M)^\alpha$ for some $\alpha > 0$ , the probability that a $q$ -portion of strategies is dominated converges to zero as $M, N \to \infty$ . This holds even if $N$ grows linearly or faster relative to $M$ .
Existence Regime: If $M \gg (N / (1 - \delta - q))^N$ for some $\delta > 0$ , the probability that a $q$ -portion of strategies is dominated (specifically by a single strategy) converges to one.
Structural Insight: The positive result is a strong structural statement, showing that a nontrivial fraction of strategies can be eliminated in a single step of strict dominance when the game is sufficiently unbalanced.

2. Confirmation of Conjectures on Single-Strategy Dominance
The paper confirms the conjecture by Alon, Rudov, and Yariv (2021) regarding the existence of any strictly dominated strategy:

There exists a threshold function $f(N) \in \Theta(\ln N)$ such that as $M, N \to \infty$ with $M$ growing within a specific range relative to $f(N)$ (e.g., $M > f(N)$ but not excessively large), the probability that a game contains no dominated strategy approaches one.
Specifically, for uniformly distributed payoffs, if the growth rate of $M$ lies within $[(2+\delta)\log_2(N), 2N^{2+\delta}]$ , the probability of a strictly dominated strategy approaches zero. Consequently, dominance solvability converges to zero in this regime.
Phase Transitions: The paper delineates distinct regions based on the relative growth of $M$ $M$ and $N$ $N$ :
- When $M$ grows moderately relative to $N$ (above the logarithmic threshold but below exponential), the probability of a strictly dominated strategy approaches zero, meaning such strategies are effectively absent.
- When $M$ grows sufficiently faster than $N$ (e.g., $M \gg (N/(1-\delta-q))^N$ ), dominated strategies become almost certain (probability of existence $\to 1$ ).
- Intermediate zones exist where the probability remains bounded away from 0 and 1.

3. Algorithmic Improvement (Algorithm 2)
The paper proposes a distribution-free algorithm that detects strictly dominated strategies more efficiently than brute-force search:

Mechanism: The algorithm precomputes the minimum and maximum of each strategy's payoff vector. It then checks pairwise relationships:
- If $\min(s_i) > \max(s_j)$ , $s_i$ strictly dominates $s_j$ .
- If $\max(s_i) > \max(s_j) > \min(s_j) > \min(s_i)$ , no dominance exists between $s_i$ and $s_j$ .
Efficiency: Proposition 5 demonstrates that in the limit as $N \to \infty$ , approximately 50% of pairwise comparisons fall into the second category (no dominance) or the first (clear dominance), allowing the algorithm to skip full element-wise comparisons.
Complexity: While the worst-case time complexity remains $O(M^2N)$ , the algorithm achieves a constant-factor improvement in practice. It reduces the number of comparisons by roughly half on average and offers superior cache-friendliness by separating preprocessing (sequential memory access) from comparison (scalar lookups), reducing memory latency issues in large matrices.

Significance and Claims
The paper claims to provide a unified view of strategic elimination in large games by generalizing from single-strategy dominance to $q$ -portion dominance.

Theoretical: It clarifies the relationship between single-strategy elimination and large-scale strategic pruning, showing that while single dominated strategies may vanish in balanced large games (where $M$ and $N$ grow at comparable or moderate rates), significant portions of strategies can be eliminated in unbalanced regimes (where $M$ grows sufficiently faster than $N$ ).
Practical: The proposed algorithm offers a computationally efficient tool for identifying dominated strategies without requiring assumptions about the underlying payoff distribution. This is presented as a practical complement to elimination procedures in computational game theory, particularly when payoff matrices exceed processor cache capacities.
Scope: The author notes that the analysis is restricted to pure strategies and i.i.d. payoffs, with mixed-strategy dominance and non-i.i.d. settings identified as directions for future work. The paper does not claim to solve the general problem of finding the exact set of dominated strategies in all cases but rather provides asymptotic bounds and a more efficient heuristic for detection.

More like this