1
$\begingroup$

This question is inspired by a recent (imo bad) TV show in German television.

Given two finite sets $A$ and $B$ of same size (representing two groups of people) and a bijective map $m \colon A \to B$ which is unknown (representing a matching).

We also define an oracle $o \colon (A \to B) \to \mathbb N$ which yields for a bijective map $f \colon A \to B$ on how many elements $a \in A$ $f$ agrees with $m$.

Given the following algorithm:

r = 1
while True:
  Pick a bijective map f: A -> B
  c = o(f)
  if c == |A|:
    return r
  r = r + 1

What is the best strategy to pick $f$?


Additionally given a function

$$ check \colon A \times B \to \mathbb B, (a, b) \mapsto \begin{cases} True, & \text{if }m(a) = b \\ False, & \text{else}\end{cases} $$

that might be queried once while picking $f$ in the above algorithm. What's the best strategy now?

$\endgroup$
3
  • $\begingroup$ How do you measure the performance of an algorithm? Are you interested in worst case, average case, or some other measure? $\endgroup$ Sep 9 at 21:22
  • 3
    $\begingroup$ See this paper $\endgroup$
    – Steven
    Sep 9 at 21:27
  • $\begingroup$ In fact, the paper mentioned by Steven solves the static case, whereas OP seems to be interested in the adaptive case. $\endgroup$ Sep 10 at 9:08
3
$\begingroup$

Your question belongs to the genre of Mastermind puzzles.

In classical generalized Mastermind, the goal is to find a string $x \in \{1,\ldots,k\}^n$ using adaptive queries of the following type: given $y \in \{1,\ldots,k\}^n$, you are given the number of black pegs (number of positions $i$ such that $x_i = y_i$) and the number of white pegs (remove all positions counted by black pegs from both strings; if the number of pegs of color $c$ are $a_c,b_c$, respectively, then output $\sum_c \min(a_c,b_c)$). The goal is to minimize the worst-case number of queries.

In your case, $k = n$, the string $x$ has no repetitions, and you are only given access to the number of black pegs ("black-peg only"). In fact, in your setting, you can determine the number of white pegs from the number of black pegs (they sum to $n$), so the restriction to black pegs only is immaterial.

Since there are $2^{\Omega(n \log n)}$ many permutations and each query has $2^{O(\log n)}$ possible answers, there is a trivial $\Omega(n)$ lower bound on the worst-case number of queries. Martinsson and Su, Mastermind with a linear number of queries, give a matching algorithm which uses $O(n)$ queries.

Glazik, Jäger, Schiemann and Srivastav, Bounds for the static permutation Mastermind game, showed that if you have to choose all queries ahead of time, then $\Omega(n\log n)$ queries are required. Larcher, Martinsson and Steger, Solving static permutation Mastermind using $O(n\log n)$ queries, give a matching strategy which uses $O(n\log n)$ non-adaptive queries.

The information-theoretic lower bound in the adaptive setting implies that "most" permutations require $\Omega(n)$ queries, in the sense that any algorithm must use $\Omega(n)$ queries for at least a $p$-fraction of permutations, for any constant $p$. Therefore the average-case complexity is also $\Theta(n)$ in the adaptive setting. I don't know whether the lower bound in the static setting similarly extends.

It seems hopeless to determine the optimal strategy (except for small $n$), though perhaps it is possible to determine the leading term (rather than just its rate of growth). Your additional free query does not affect the asymptotics, and so has no effect on the results above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.