1
$\begingroup$

Given $n$, let $\mathcal{R}$ be a set of pairs $(\rho,A)$ where $A\subseteq n, \rho\in 2^A$. Consider the following game between A and B.

At each round $t$, A enumerates an $m\in n$ (that has not been enumerated before) and B presents a $i_m\in 2$. Let $A[t]$ denote the set of $m$'s A has enumerated by round $t$ and $\rho[t]\in 2^{A[t]}$ denote the string $m\mapsto i_m$. A wins at round $t$ if $(\rho[t],A[t])\in \mathcal{R}$.

Question: Is there some general criterion on $\mathcal{R}$ ensuring A wins (with $|A|<n$ where $A$ is the set of $m$ A enumerated during the game)? For example: for every $\rho\in 2^n$, there are "many" $A\subseteq n$ such that $(\rho\upharpoonright A, A)\in \mathcal{R}$.

$\endgroup$
1
  • 1
    $\begingroup$ What do you mean by A wins? You only defined "wins at round $t$". Are there multiple rounds? When does the game end? $\endgroup$
    – BeB
    Commented Jan 22, 2021 at 10:18

0

You must log in to answer this question.