Problem of the Month (December 2017)

One model that has been used for understanding the choosing of political platforms is the following. One at a time, players (political parties) choose a number in [0,1] (a platform of how liberal to conservative they are). After the players are done choosing their numbers, they are awarded a score (percentage of the vote) equal to the length of the interval of points that are closer to them than their opponents (since we assume voters are uniformly distributed on [0,1], and vote for the party closest to their own positions).

This model is easy to analyze for 2 players. If player 1 chooses x≤1/2, player 2 chooses x+2ε, and the scores are x+ε and 1–x–ε respectively. If player 1 chooses x≥1/2, player 2 chooses x–2ε, and the scores will be 1–x+ε and x–ε respectively. Thus player 1 chooses 1/2 and player 2 chooses 1/2±2ε, and the scores will be 1/2+ε and 1/2–ε.

The 3 player case is more complicated. If player 1 chooses x≤1/4, player 2 chooses (1–x)/3, and player 3 chooses any number between them in the interval (x, (1–x)/3). In this case the average scores will be (5x+1)/6, (1–x)/3, and (1–x)/2 respectively. If player 1 chooses 1/4<x≤1/2, then player 2 chooses 1–x+2ε and player 3 chooses x–2ε. In this case the scores will be 1/2–x+2ε, 1/2-ε, and x–ε respectively. The cases where player 1 chooses x≥1/2 are similar by symmetry. Thus player 1 chooses 1/4, player 2 chooses 3/4, and player 3 chooses something between in the interval (1/4,3/4), giving average scores of 3/8, 3/8, and 1/4. What are the best strategies for more than 3 players?

This game is also interesting where players get multiple turns in a specified order. For example, for the order 112, player 1 chooses 1/4 and 3/4, and player 2 chooses any number between them in the interval (1/4, 3/4), and the scores will be 3/4 and 1/4 respectively. What are the best strategies for any order of players?


ANSWERS

Players Play Only Once
OrderOptimal PlaysOptimal ScoresAuthor
1[0,1]1 
121/2   1/2+2ε1/2+ε   1/2–ε 
1231/4   3/4   (1/4,3/4)3/8   3/8   1/4 
12341/6   5/6   1/2   (1/6,5/6)7/24   7/24   1/4   1/6Joe DeVincentis
123451/8   7/8   3/8   5/8   (1/8,7/8)11/48   11/48   5/24   5/24   1/8Dan Dima

In fact, Dan Dima gives a convincing argument that for larger number of players n, the first (n–1) player will pick odd multiples of 1/(2n–2), with the first two players picking 1/(2n–2) and (2n–1)/(2n–2), leaving the last player to choose any number between them. This leads to scores (4n–9)/4(n–1)(n–2) for the first two players, (2n–5)/2(n–1)(n–2) for most of the players, and 1/2(n–1) for the last player.

2 Players Make 3 Moves
OrderOptimal PlaysOptimal Scores
1121/4   3/4   (1/4,3/4)3/4   1/4
1211/2   5/6   5/6–2ε5/6–ε   1/6+ε
1221/2   1/2–ε   1/2+εε   1–ε

2 Players Make 4 Moves
OrderOptimal PlaysOptimal Scores
11121/6   1/2   5/6   (1/2,5/6)5/6   1/6
11213/10   7/10   9/10   9/10–2ε9/10–ε   1/10+ε
11221/4   3/4   1/4+ε   3/4–ε1/2+2ε   1/2–ε
12111/2   x   x–ε   x+ε1–ε   ε
12121/4   3/4   3/4+3ε   1/4–ε1/2–ε   1/2+ε
12211/4   3/4   1/4–3ε   3/4+ε1/2+ε   1/2–ε
1222x   x–ε   x+ε   yε   1–ε

3 Players Make 4 Moves
OrderOptimal PlaysOptimal ScoresAuthor
11231/6   5/6   1/2   (1/6,5/6)7/12   1/4   1/6
1213???
1223???
1231???
1232???
12331/4–2ε   3/4+2ε   1/4   3/41/4–ε   1/4–ε   1/2+2εBryce Herdt

2 Players Make 5 Moves
OrderOptimal PlaysOptimal ScoresAuthor
111121/8   3/8   5/8   7/8   (5/8,7/8)7/8   1/8
111213/14   1/2   11/14   13/14   13/14–2ε13/14–ε   1/14+ε
111221/6   1/2   5/6   (1/6,1/2)   (1/2,5/6)2/3   1/3
11211x   y   z   z–ε   z+εε   1–ε
11212???
11221???
112221/4   3/4   1/4–ε   3/4+ε   (1/4,3/4)1/4+2ε   3/4–2ε
12111x   y   y–ε   y+ε   zε   1–ε
12112???
12121???
12122???
122115/6   1/6   1/2   1/6–2ε   (1/6,1/2)5/6–ε   1/6+εJoe DeVincentis
12212???
122211/2   1/6   1/2+3ε   5/6   1/6–ε2/3–ε   1/3+ε
12222x   x–ε   x+ε   y   zε   1–ε

3 Players Make 5 Moves
OrderOptimal PlaysOptimal Scores
11123??
11213??
11223??
11231??
11232??
11233??
12113??
12123??
12131??
12132??
12133??
12213??
12223??
12231??
12232??
12233??
12311??
12312??
12313??
12321??
12322??
12323??
12331??
12332??
12333??

4 Players Make 5 Moves
OrderOptimal PlaysOptimal Scores
12234??
12134??
12234??
12314??
12324??
12334??
12341??
12342??
12343??
12344??

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 12/1/17.