Expected value of a function in a probabilistic game

Question

Here is an interesting problem that I recently encountered:

Suppose we have a function $f : \{0, 1\}^{n} \to \mathbb{N}$. The $2^{n}$ of the functional values of $f$ are fixed and known.

Alice and Bob are playing a game with this function (both of them know what the function evaluates to at each of the $2^{n}$ points). The game begins with $n$ integers $a_1, a_2, \ldots, a_n$ such that $a_i = -1$ for all $1 \leq i \leq n$.

In each round, a (fair) coin is flipped. If the coin is heads, then Alice gets her turn. Otherwise, Bob gets his turn. In a single turn, either Alice or Bob gets to pick an index $1 \leq j \leq n$ (that has not been selected before), and they can set $a_j$ to either $0$ or $1$. Clearly, this process will terminate in $n$ steps (and all of the $a_i$'s will be either $0$ or $1$).

Alice's objective is to maximize $f(a_1 a_2a_3\cdots a_n)$, and Bob's objective is to minimize $f(a_1a_2\cdots a_n)$, where $a_1 a_2 \cdots a_n$ is the binary string formed by concatenating the $a_i$ values together.

Assuming Alice and Bob play optimally, what is the expected value of $f$?

---

I know that the answer is

$$\mathbb{E}[f] = \frac{1}{2^n}\sum_{x \in \{0, 1\}^{n}} f(x),$$

but this is not obvious to me.

I will try to explain why the above expression is not as obvious as it might seem. Let the $2^{n}$ functional values be $c_1, c_2, \ldots, c_{2^n}$, and define the "distance" between $c_i$ and $c_j$ to be the number of bits at which $c_i$ and $c_j$ differ. Essentially, the summation above is saying that the answer does not depend on the distance between the values. It is saying that the answer is always the average of all of the values no matter what the distance between them is.

Can someone please explain how this expression can be derived? I've tried to come up with a recurrence to describe the situation by conditioning the expectation on who goes first; however, this has not helped me.

Thank you.

Answer 1

At every turn, the current player chooses to flip the coordinate that influences the result most. I claim this is the same coordinate for both players.

Formally, let us see how Alice calculates her expected gain: Alice tries to choose the index $j$ and entry $0/1$ that would give the following maximum: $$\max_{(i,b)\in[n]\times\{0,1\}}\{\Bbb E_{x\in \{0,1\}^{n-1}}f(x_1,...,x_{i-1},b,x_i,...,x_{n-1})\}$$ That is, Alice tries to maximize the coordinate's influence on the actual result, and given those maximizing $i,b$, it must hold that $$\Bbb E_{x\in \{0,1\}^{n-1}}f(x_1,...,x_{i-1},b,x_i,...,x_{n-1})+\Bbb E_{x\in \{0,1\}^{n-1}}f(x_1,...,x_{i-1},1-b,x_i,...,x_{n-1})=2\Bbb E(f)$$ so we get that the same coordinate would make the most sense for Bob to choose as well. This implies that the order of flipped bits is predetermined (up to two coordinates having the same influence), and therefore the probability for each value is uniform, depending on the results of the coin toss.