{"id":2404,"date":"2018-08-19T11:57:35","date_gmt":"2018-08-19T16:57:35","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2404"},"modified":"2018-08-19T20:50:12","modified_gmt":"2018-08-20T01:50:12","slug":"the-number-line-game","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/the-number-line-game\/","title":{"rendered":"The number line game"},"content":{"rendered":"

This Riddler puzzle<\/a> is a game theory problem: how should each player play the game to maximize their own winnings?<\/p>\n

\nAriel, Beatrice and Cassandra \u2014 three brilliant game theorists \u2014 were bored at a game theory conference (shocking, we know) and devised the following game to pass the time. They drew a number line and placed \\$1 on the 1, \\$2 on the 2, \\$3 on the 3 and so on to \\$10 on the 10.<\/p>\n

Each player has a personalized token. They take turns \u2014 Ariel first, Beatrice second and Cassandra third \u2014 placing their tokens on one of the money stacks (only one token is allowed per space). Once the tokens are all placed, each player gets to take every stack that her token is on or is closest to. If a stack is midway between two tokens, the players split that cash.<\/p>\n

How will this game play out? How much is it worth to go first?<\/p>\n

A grab bag of extra credits: What if the game were played not on a number line but on a clock, with values of \\$1 to \\$12? What if Desdemona, Eleanor and so on joined the original game? What if the tokens could be placed anywhere on the number line, not just the stacks?\n<\/p><\/blockquote>\n

Here are the details of how I approached the problem:
\n[Show Solution]<\/a><\/p>\n

\n

This problem is different from previous game theory problems I\u2019ve written about such as the war game<\/a> or the dodgeball duel<\/a>, where all players in the game act simultaneously. In such games, you can assume a strategy for each player, and then look for the strategy that yields a Nash equilibrium<\/a>, which is a set of strategies such that no player has any incentive to change their actions. Sometimes, the optimal strategy is a mixed strategy<\/a>, which means it involves randomness. This is the case in rock-paper-scissors, for example, where the Nash-optimal strategy is to choose randomly.<\/p>\n

What makes the present problem quite different is that it\u2019s a sequential game<\/a> in which each player gets to see the previous players\u2019 moves when it comes their turn to play. This means that there can be no advantage to playing randomly. The standard way to solve such problems is via backward induction (also known as dynamic programming<\/a>). I will illustrate the approach for the basic version of the problem: 10 stacks and 3 players. A strategy<\/em> is a set of moves $(a,b,c)$ where $a$ is Ariel\u2019s move, $b$ is Beatrice\u2019s move, and $c$ is Cassandra\u2019s move. We proceed by backward induction as follows:<\/p>\n

    \n
  1. Given a strategy $(a,b,c)$, let\u2019s call Ariel\u2019s payout $P_A(a,b,c)$. Similarly, we\u2019ll call Beatrice\u2019s and Cassandra\u2019s payouts $P_B$ and $P_C$, respectively.\n<\/li>
  2. Imagine it\u2019s Cassandra\u2019s turn. She observes Ariel and Beatrice\u2019s moves $a$ and $b$. For each potential choice of $c$, we can compute Cassandra\u2019s payout $P_C(a,b,c)$ and then select the most profitable choice of $c$. Let\u2019s call Cassandra\u2019s strategy $K_C(a,b)$. Mathematically, we\u2019re defining:
    \n\\[
    \nK_C(a,b) = \\arg\\max_{c} P_C(a,b,c)
    \n\\]\n<\/li>
  3. Now imagine it\u2019s Beatrice\u2019s turn. She observes Ariel\u2019s move ($a$). She also knows that if she chooses $b$, then Cassandra will follow up with $K_C(a,b)$. So she must choose the best $b$ in anticipation of what Cassandra will do. If we call Beatrice\u2019s strategy $K_B(a)$, then we have:
    \n\\[
    \nK_B(a) = \\arg\\max_{b} P_B(a,b,K_C(a,b))
    \n\\]\n<\/li>
  4. Finally, imagine it\u2019s Ariel\u2019s turn. Although she\u2019s the first to move, no matter which $a$ she picks, she can be assured Beatrice will choose $b = K_B(a)$ and Cassandra will follow-up with $c = K_C(a,b)$. So Ariel can examine all of her options and predict her payout. Ultimately, her decision will be $K_A$, which is given by:
    \n\\[
    \nK_A = \\arg\\max_{a} P_A(a,K_B(a),K_C(a,K_B(a)))
    \n\\]\n<\/li><\/ol>\n

    Computational details<\/h3>\n

    Writing code to implement the backward induction above was quite a challenge. I will include my finished code later so you can play with it, but for now I\u2019ll just highlight two of the major hurdles I had to overcome.<\/p>\n