1
$\begingroup$

Alice and Bob play a game over $n$ rounds. At each round, Alice picks a number $x_t \in [0,1]$ and Bob simultaneously chooses whether to "peek" at the number $x_t$ which is represented by a variable $y_t \in \{0,1\}$. The game is over at round $t$ if the "revealed" sub-total to Bob $\sum_{s=1}^t y_s \cdot x_s$ exceeds some threshold $\sqrt{y_1+\cdots+y_t}$. But, Bob also has a total budget $\sum_{t=1}^n y_t \leq \sqrt{n}$ on the allowed number of peeks which is known to alice at the beginning.

Therefore, Alice's goal is to maximize $\sum_{t=1}^T x_t$ where $T \leq n$ is the realized number of rounds played before the game ends, while Bob's goal is to minimize $\sum_{t=1}^T x_t$ by scheduling peeks accordingly. Both players make decisions adaptively (although Bob only has bandit information of $x_t$ values on peeked rounds where $y_t=1$) and are allowed to use randomization.

I am not a TCS person, but am wondering if this kind of problem is already studied or reducible to some other well known problem. And, if so, what guarantees are known for Alice and/or Bob. For context, one can think of Bob here as an adversarial multi-armed bandit algorithm which is trying to do some kind of change-point detection in the environment (set by adversary Alice).

$\endgroup$
4
  • $\begingroup$ (i) So $n$ is known in advance to both players? What about $F$? (ii) What do you know about simple special cases, e.g. where $F$ and $B$ are known constants and $n=\infty$? (iii) What happens if the threshold is not exceeded in the first $n$ rounds? $\endgroup$
    – Neal Young
    Commented Feb 29 at 19:19
  • $\begingroup$ $n,F,B$ are known in advance to both players. If $F,B$ are constants (say, Bob only has one round to peek), then there is probably not much Bob can do as Alice can use randomization to achieve a linear $\Omega(T)$ cost with constant probability. I am more interested in the cases where Bob can force Alice to get sublinear value even while constrained to a budget of $B(n)=\sqrt{n}$. For my use case, we have $F(y_1,\ldots,y_t) = \sqrt{y_1+\cdots+y_t}$. $\endgroup$ Commented Feb 29 at 21:48
  • $\begingroup$ I've edited the question to be more specific and avoid ambiguity about some uninteresting cases. $\endgroup$ Commented Feb 29 at 21:54
  • $\begingroup$ What do Alice and Bob know about each other's strategies? E.g. do you assume that at the start of round $t$, Alice knows the probability distribution induced on $y_t$ by Bob's strategy? And/or vice versa (Bob knows the probability distribution induced on $x_t$ by Alice's strategy)? (In both cases, conditioned on all events that have occurred before round $t$.) $\endgroup$
    – Neal Young
    Commented Mar 1 at 16:29

1 Answer 1

1
$\begingroup$

This answer doesn't answer whether or not this is a special case of some kind of game that is studied in TCS. But hopefully the answer helps understand the nature of the game.

The value of the game is $\Theta(n^{3/4})$:

Lemma 1. Alice has a strategy that guarantees $\sum_{t=1}^T x_t \ge n^{3/4}$.

Lemma 2. Bob has a strategy that guarantees $\sum_{t=1}^T x_t = O(n^{3/4})$ in expectation.

(I'm pretty sure the upper bound can be shown to hold w.h.p., and can be tightened to $(1+o(1))n^{3/4}$.)

Proof of Lemma 1. Suppose Alice plays $x_t = n^{-1/4}$ at every time step, and Bob plays any legal strategy.

For the game to terminate at some time $t<n$, it must be that $\sum_{s=1}^t y_s x_s > \sqrt{\sum_{s=1}^t y_s}.$ Substituting $x_t = n^{-1/4}$ and simplifying, this is equivalent to $\sum_{s=1}^t y_s > n^{1/2}.$ But this cannot happen without Bob violating his "budget" $\sum_{s=1}^n y_s \le \sqrt n$.

So the game does not terminate early. So the "payoff" $\sum_{t=1}^T x_t$ equals $n \cdot n^{-1/4} = n^{3/4}$. $~~~\Box$

Proof sketch for Lemma 2. We let r.v. $S$ be the first round $t$ after which Bob is constrained by his budget constraint, that is, when $\sum_{s=1}^{t} y_s \ge \sqrt n$, so that Bob is forced to set $y_s = 0$ for $s > S$. (If it never happens, we let $S=T$.)

Now suppose that Alice plays any legal (possibly randomized) strategy, while Bob plays as follows: for each round $t \le S$ independently, Bob plays $y_t = 1$ with fixed probability $p = 0.5 n^{-1/2}$, and otherwise plays $y_t = 0$. (For each round $t > S$, Bob plays $y_t=0$, per the definition of $S$.)

The total payoff to Alice is then $$\textstyle \sum_{t=1}^T x_t \le T-S + \sum_{t=1}^{S} x_t.~~~~~~(1)$$ We bound the expectations of $T-S$ and $\sum_{t=1}^S x_t$ separately.

At the start of any round $t\le S$, conditioned on all events so far, $E[x_t - p^{-1} x_t y_t] = 0$. Also, $S$ is a stopping time. So by Wald's equation $$\textstyle E\big[\sum_{t=1}^{S} (x_t - p^{-1} x_t y_t) \big] = 0.$$ This implies that

$$ \begin{align}\textstyle E\big[\sum_{t=1}^{S} x_t \big] & \textstyle{} = p^{-1} E\big[\sum_{t=1}^{S} x_t y_t\big] \\ & \textstyle{} \le p^{-1} E\big[1+\sqrt{\sum_{t=1}^S y_t}\big] \\ & \textstyle{} \le p^{-1} (1+\sqrt{n p}) = O(n^{3/4}). ~~(2) \end{align} $$

(The first inequality above uses $\sum_{t=1}^{S-1} y_t x_t \le \sqrt{\sum_{t=1}^{S-1} y_t}$ and $y_S x_S \le 1$. The second inequality uses the concavity of the square root, linearity of expectation, $E[y_t] = p$, and $S\le n$.)

To finish we bound $E[T-S]$. First we observe that the event $S<T$ is unlikely. Recalling that the $y_t$'s are independent 0/1-r.v.s with expectation $p$ and $T\le n$, by a standard Chernoff bound, $$\textstyle\Pr\big[\sum_{t=1}^T y_t \ge 2 np\big] \le \exp(-np / 3).$$ Substituting $p = 0.5 n^{-1/2}$ gives $$\textstyle\Pr\big[\sum_{t=1}^T y_t \ge \sqrt n\big] \le \exp(-\sqrt n / 6).$$ Finally, $T - S \le n$, and $T>S$ only if $\sum_{t=1}^T y_t \ge \sqrt n$, so $$\textstyle E[T- S] \le n \Pr[T > S] \le n \Pr[\sum_{t=1}^T y_t \ge \sqrt n] \le n \exp(- \sqrt n / 6) = O(n^{3/4}).~~~~(3) $$

Inequalities (1), (2), and (3) imply that $E\big[\sum_{t=1}^T x_t\big] = O(n^{3/4})$. $~~~~~\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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