The Query Complexity of a Permutation-Based Variant of Mastermind

Abstract

We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair $(z,\ddot{I}€)$ which consists of a binary string $z\in \{0,1{\}}^n$ and a permutation $\ddot{I}€$ of $[n]$. The secret must be unveiled by asking queries of the form $x\in \{0,1{\}}^n$. For each such query, we are returned the score \[ f_{z,π}(x):= \max \{ i \in [0..n]\mid \forall j \leq i: z_{π(j)} = x_{π(j)}\}\,;\] i.e., the score of $x$ is the length of the longest common prefix of $x$ and $z$ with respect to the order imposed by $\ddot{I}€$. The goal is to minimize the number of queries needed to identify $(z,\ddot{I}€)$. This problem originates from the study of black-box optimization heuristics, where it is known as the \textsc{LeadingOnes} problem. In this work, we prove matching upper and lower bounds for the deterministic and randomized query complexity of this game, which are $\hat{I}˜(n\log n)$ and $\hat{I}˜(n\log \log n)$, respectively.

Full version of a result previously announced in 2013. Accepted subject to minor revision at Discrete Applied Mathematics