Results 1 to 3 of 3

Thread: optimization/game theory problem

  1. #1
    Newbie
    Joined
    Jun 2017
    From
    California, USA
    Posts
    2

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,386
    Thanks
    903

    Re: optimization/game theory problem

    Is this independent of what $p_k$'s are chosen?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2017
    From
    California, USA
    Posts
    2

    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.
    Last edited by datanerd; Jun 13th 2017 at 12:47 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a game theory problem for voting
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Jan 8th 2013, 05:39 PM
  2. Game theory problem (very simple)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Oct 14th 2012, 10:10 AM
  3. game theory modelling the problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: Apr 17th 2011, 05:42 AM
  4. a game theory problem
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: Jun 27th 2009, 01:02 AM
  5. Game Theory Problem
    Posted in the Business Math Forum
    Replies: 2
    Last Post: Jan 7th 2008, 03:23 AM

Search Tags


/mathhelpforum @mathhelpforum