1. ## optimization/game theory problem

Consider a game of $N$ rounds. For every step $k \in \{1, \dots, N\}$, we pick some $x_k \in [-1, 1]$. The adversary then responds with some $p_k \in [-1, 1]$. Show that there is some strategy for choosing $\{x_k\}_{k=1}^N$ that with knowledge of $N$ achieves
$\sum_{k=1}^N x_k p_k + \left| \sum_{k=1}^N p_k \right| \leq O(\sqrt{N}).$

I have been stuck for a couple days, any help would be so appreciated!

2. ## Re: optimization/game theory problem

Is this independent of what $p_k$'s are chosen?

3. ## Re: optimization/game theory problem

Not entirely. For example, $x_k$ can be a function of $p_1, p_2, \dots, p_{k-1}$. It is important, however to note that $x_k$ picks first, so it does not get to see $p_k$ (so in some sense the adversary has the "upper hand"). You can think of this problem
as specifying $x_1, x_2, \dots, x_N$ such that each $x_j$ can depend on $p_i$ for $i < j$, and then we want to show that
$\max_{p_1, p_2, \dots, p_N \in [-1, 1]} \left \{ \sum_{k=1}^N x_k p_k + \left|\sum_{k=1}^N p_k \right| \right\} \leq C \cdot \sqrt{N} ,$
where $C$ is some numerical constant and $N$ large enough.