Price of Locality in Permutation Mastermind: Are TikTok influencers Chaotic Enough?
Pith reviewed 2026-05-16 11:15 UTC · model grok-4.3
The pith
Local strategies in permutation Mastermind require quadratic guesses instead of the O(n log n) bound available without the restriction.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the permutation Mastermind game the optimal number of guesses for ℓ_k-local strategies is quadratic in n, in contrast to the O(n log n) queries that suffice when consecutive guesses may differ arbitrarily. For the stricter w_k-local variant the same quadratic lower bound holds. Deciding whether a target number of guesses suffices is NP-hard for ℓ_3-local strategies yet solvable in randomized polynomial time for the ℓ_2-local case.
What carries the argument
ℓ_k-local strategies, in which any two consecutive guesses differ in at most k positions, together with the feedback that returns only the number of exact position matches.
If this is right
- Any strategy obeying the locality restriction must use Θ(n²) guesses in the worst case.
- For ℓ_3-local strategies the decision problem of whether a given number of guesses suffices is NP-hard.
- For ℓ_2-local strategies the same decision problem admits a randomized polynomial-time algorithm.
- The O(n log n) upper bound known for unrestricted strategies cannot be achieved under locality.
Where Pith is reading between the lines
- Players who change only a few entries between turns are paying a quadratic price that grows rapidly with n.
- Relaxing locality only for a few steps might restore near-linear performance while still resembling human play.
- The same locality penalty may appear in other guessing games whose feedback is limited to position matches.
Load-bearing premise
The secret remains a fixed permutation and each guess receives feedback consisting solely of the count of exact position matches.
What would settle it
A concrete counter-example would be an explicit ℓ_1-local strategy that identifies every secret permutation of n=100 using fewer than 4000 guesses.
read the original abstract
In the permutation Mastermind game, the goal is to uncover a secret permutation $\sigma^\star \colon [n] \to [n]$ by making a series of guesses $\pi_1, \ldots, \pi_T$ which must also be permutations of $[n]$, and receiving as feedback after guess $\pi_t$ the number of positions $i$ for which $\sigma^\star(i) = \pi_t(i)$. While the existing literature on permutation Mastermind suggests strategies in which $\pi_t$ and $\pi_{t+1}$ might be widely different permutations, a resurgence in popularity of this game as a TikTok trend shows that humans (or at least TikTok influencers) use strategies in which consecutive guesses are very similar. For example, it is common to see players attempt one transposition at a time and slowly see their score increase. Motivated by these observations, we study the theoretical impact of two forms of "locality" in permutation Mastermind strategies: $\ell_k$-local strategies, in which any two consecutive guesses differ in at most $k$ positions, and the even more restrictive class of $w_k$-local strategies, in which consecutive guesses differ in a window of length at most $k$. We show that, in broad terms, the optimal number of guesses for local strategies is quadratic, and thus much worse than the $O(n \lg n)$ guesses that suffice for non-local strategies. We also show NP-hardness of the satisfiability version for $\ell_3$-local strategies, whereas in the $\ell_2$-local variant the problem admits a randomized polynomial algorithm.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper examines the permutation Mastermind game, where guesses are permutations and feedback is the number of exact position matches. It introduces two locality restrictions: ℓ_k-local strategies (consecutive guesses differ in at most k positions) and w_k-local strategies (differ in a window of length at most k). The central claims are that optimal local strategies require Θ(n²) guesses in the worst case—contrasting with the O(n log n) bound for unrestricted strategies—and that the decision version is NP-hard for ℓ_3-local but admits a randomized polynomial-time algorithm for ℓ_2-local.
Significance. If the quadratic separation and complexity results hold, the work quantifies the cost of locality in combinatorial search, directly motivated by observed human play patterns. The distinction between ℓ_2 and ℓ_3 cases, together with the explicit comparison to the known non-local bound, provides a clean contribution to the theory of adaptive search under constraints. The absence of free parameters or fitted constants in the stated bounds strengthens the result.
major comments (2)
- [§3–4 (lower-bound construction)] The quadratic lower bound for ℓ_k-local strategies (stated in the abstract and presumably proved in §3 or §4) is load-bearing for the main claim; the adversary argument must explicitly track how exact-match feedback interacts with the k-position difference constraint to force Ω(n²) queries. Without the full construction details, it is unclear whether the bound remains tight when k is fixed (e.g., k=2 or 3) or grows with n.
- [§5 (NP-hardness)] The NP-hardness reduction for ℓ_3-local satisfiability (abstract and §5) must preserve the locality constraint in the constructed permutation instances. The reduction sketch should specify how the 3-SAT clauses are encoded so that any satisfying assignment corresponds to a sequence of permutations differing in at most three positions; otherwise the hardness claim does not transfer.
minor comments (2)
- [Abstract and §1] The abstract uses “lg” for log base 2; the full text should adopt a consistent notation (log₂ or lg) throughout and define it on first use.
- [§2 (related work)] Clarify whether the O(n lg n) non-local upper bound is cited from prior work or reproved; if cited, add the reference in §2.
Simulated Author's Rebuttal
We thank the referee for the detailed and constructive report. The two major comments identify places where the manuscript would benefit from expanded explanations of the technical constructions. We will revise the paper accordingly to include fuller details on both the lower-bound adversary argument and the NP-hardness reduction while preserving the original claims.
read point-by-point responses
-
Referee: [§3–4 (lower-bound construction)] The quadratic lower bound for ℓ_k-local strategies (stated in the abstract and presumably proved in §3 or §4) is load-bearing for the main claim; the adversary argument must explicitly track how exact-match feedback interacts with the k-position difference constraint to force Ω(n²) queries. Without the full construction details, it is unclear whether the bound remains tight when k is fixed (e.g., k=2 or 3) or grows with n.
Authors: We agree that the current presentation of the lower bound would be strengthened by more explicit step-by-step tracking. In the revised manuscript we will expand the adversary construction in Sections 3 and 4 to show precisely how each exact-match answer, together with the restriction that consecutive permutations differ in at most k positions, forces the algorithm to incur an additional linear number of queries per “block” of the secret permutation. The argument is written for arbitrary fixed k (including k=2 and k=3) and yields Ω(n²) regardless of whether k remains constant or grows slowly with n, provided k=o(n); we will add a short remark clarifying this dependence. revision: yes
-
Referee: [§5 (NP-hardness)] The NP-hardness reduction for ℓ_3-local satisfiability (abstract and §5) must preserve the locality constraint in the constructed permutation instances. The reduction sketch should specify how the 3-SAT clauses are encoded so that any satisfying assignment corresponds to a sequence of permutations differing in at most three positions; otherwise the hardness claim does not transfer.
Authors: We appreciate the request for a clearer description of the reduction. In the revised Section 5 we will give an explicit encoding that maps each 3-SAT variable to a small set of positions in the permutation and each clause to a triple of allowable transpositions. We will prove that (i) every transition between consecutive permutations differs in at most three positions, (ii) a satisfying assignment yields a valid ℓ_3-local sequence that “resolves” all clauses, and (iii) conversely any such sequence corresponds to a satisfying assignment. This will make the locality preservation fully rigorous. revision: yes
Circularity Check
No significant circularity
full rationale
The derivation chain rests on explicit combinatorial reductions from the defined ℓ_k-local and w_k-local constraints (consecutive permutations differing in ≤k positions or a window of length k) together with the exact-match feedback model. The quadratic upper and lower bounds for local strategies are obtained via direct counting and adversary arguments that do not invoke fitted parameters, self-referential definitions, or load-bearing self-citations. The O(n lg n) non-local bound is cited from prior independent literature, and the NP-hardness result for ℓ_3-local satisfiability plus the randomized poly-time algorithm for ℓ_2-local are established by separate reductions that remain independent of the target guess-complexity statements.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The feedback after each guess is exactly the number of positions i where σ*(i) = π(i).
- standard math Permutations of [n] exist and can be compared position-wise.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.