<p>This is the copy of my question at Mathoverflow: <a href="https://mathoverflow.net/questions/476867/some-game-with-a-boolean-function">https://mathoverflow.net/questions/476867/some-game-with-a-boolean-function</a>.</p>
<p>Let <span class="math-container">$f: \{0,1\}^{m + k} \to \{0,1\}^n$</span> be some function,</p>
<p>where <span class="math-container">$m = n \log n$</span>  and <span class="math-container">$k &lt; \log \log \log \log n$</span>.</p>
<p>Consider the following game between Alice and Bob that is determined by <span class="math-container">$f$</span>, <span class="math-container">$c_A$</span> (Alice's capital), <span class="math-container">$c_B$</span> (Bob's capital) and some vector <span class="math-container">$b \in \{0,1\}^n$</span>.</p>
<p>Consider Boolean variables <span class="math-container">$x_1, \ldots, x_m, y_1, \ldots, y_k$</span>.</p>
<p>Initially all this variables are set to <span class="math-container">$0$</span>. The  players can change the value of a variable from <span class="math-container">$0$</span> to <span class="math-container">$1$</span> by using their money. The cost of each such change is equal to <span class="math-container">$1$</span>.</p>
<p>Bob can change any variable, and Alice can change only <span class="math-container">$x_1, \ldots, x_m$</span>.</p>
<p>The goal of Bob is to make <span class="math-container">$f(x_1, \ldots, x_m, y_1, \ldots, y_k) = b$</span> and the  Alice's goal is the opposite.</p>
<p>A player makes his or her move iff the current value of <span class="math-container">$f$</span> does not correspond to his or her goal.</p>
<p>A player looses if he or she spends all his or her money and the current value of <span class="math-container">$f$</span> does not correspond to his or her goal.</p>
<p>Let <span class="math-container">$c_A:= \frac{m}{4}$</span> and <span class="math-container">$c_B:=\frac{m}{400}$</span>.</p>
<p><strong>Question</strong> Is it true that for every <span class="math-container">$f$</span> Alice has a winning strategy for all <span class="math-container">$b \in \{ 0,1\}^n$</span> except at most <span class="math-container">$\frac{2^n}{n}$</span> values (for large enough <span class="math-container">$n$</span>)?</p>
<p>Consider the case <span class="math-container">$k=0$</span>. In this case Alice has a winning strategy for all <span class="math-container">$b$</span> except at most <span class="math-container">$1$</span> value even if <span class="math-container">$c_A = c_B$</span>. Indeed, the players have equal opportunities and hence Bob cannot has winning strategy for different <span class="math-container">$b_1$</span> and <span class="math-container">$b_2$</span> (because Alice also can use one of them).</p>
<p>So, my question is if <span class="math-container">$k$</span> is some tiny function, can it dramatically change the situation?</p>
<p>Similar games were considered in <a href="https://www.sciencedirect.com/science/article/pii/S0890540112001472" rel="nofollow noreferrer">1</a> <a href="https://link.springer.com/chapter/10.1007/978-3-031-36978-0_9" rel="nofollow noreferrer">2</a>. My question is also related to some problem in Kolmogorov complexity.</p>

CC BY-SA 4.0
2024-09-23T19:24:16.040Z
Note that simultaneous cross-posting is generally prohibited... maybe check the rules of cs.theory to see if there are exceptions?
Neal Young
CC BY-SA 4.0
2024-09-24T10:20:18.703Z
The question has been on MO for quite some time with no answer, so it may be ok to repost it here, though the post on MO should at least link here to avoid duplication if it is not deleted. However, what does not make any sense to me is to simultaneously repost the question here *and* place a bounty on the original question on MO. If you repost the question here, you should ideally *delete* the question there rather than draw attention to it.
Emil Jeřábek
<combinatorial-game-theory><two-player-games>
Some game on a Boolean function
Alexey Milovanov
# Some game on a Boolean function

(Asked by: username_0 on 2024-09-23)

This is the copy of my question at Mathoverflow: <https://mathoverflow.net/questions/476867/some-game-with-a-boolean-function>.

Let $f: \{0,1\}^{m + k} \to \{0,1\}^n$ be some function,

where $m = n \log n$ and $k < \log \log \log \log n$.

Consider the following game between Alice and Bob that is determined by $f$, $c\_A$ (Alice's capital), $c\_B$ (Bob's capital) and some vector $b \in \{0,1\}^n$.

Consider Boolean variables $x\_1, \ldots, x\_m, y\_1, \ldots, y\_k$.

Initially all this variables are set to $0$. The players can change the value of a variable from $0$ to $1$ by using their money. The cost of each such change is equal to $1$.

Bob can change any variable, and Alice can change only $x\_1, \ldots, x\_m$.

The goal of Bob is to make $f(x\_1, \ldots, x\_m, y\_1, \ldots, y\_k) = b$ and the Alice's goal is the opposite.

A player makes his or her move iff the current value of $f$ does not correspond to his or her goal.

A player looses if he or she spends all his or her money and the current value of $f$ does not correspond to his or her goal.

Let $c\_A:= \frac{m}{4}$ and $c\_B:=\frac{m}{400}$.

**Question** Is it true that for every $f$ Alice has a winning strategy for all $b \in \{ 0,1\}^n$ except at most $\frac{2^n}{n}$ values (for large enough $n$)?

Consider the case $k=0$. In this case Alice has a winning strategy for all $b$ except at most $1$ value even if $c\_A = c\_B$. Indeed, the players have equal opportunities and hence Bob cannot has winning strategy for different $b\_1$ and $b\_2$ (because Alice also can use one of them).

So, my question is if $k$ is some tiny function, can it dramatically change the situation?

Similar games were considered in [1](https://www.sciencedirect.com/science/article/pii/S0890540112001472) [2](https://link.springer.com/chapter/10.1007/978-3-031-36978-0_9). My question is also related to some problem in Kolmogorov complexity.

**Tags:** combinatorial-game-theory, two-player-games

> **Comments:**
> **username_1**: Note that simultaneous cross-posting is generally prohibited... maybe check the rules of cs.theory to see if there are exceptions?  
> **username_2**: The question has been on MO for quite some time with no answer, so it may be ok to repost it here, though the post on MO should at least link here to avoid duplication if it is not deleted. However, what does not make any sense to me is to simultaneously repost the question here *and* place a bounty on the original question on MO. If you repost the question here, you should ideally *delete* the question there rather than draw attention to it.  

---

## 0 answers

