A (simple) problem on Game Theory

Nash equilibrium strategy: In this graph: pick whichever choice has higher chance of winning: https://imgur.com/a/yYKfkKr. This results in the following distribution of choices: https://imgur.com/a/hO0IgeC.

My reasoning: Whatever is opponent's strategy, there exists a probability distribution of his choices. Then, our strategy should be the best response to his strategy. Our best response is easy to calculate if we know opponent's distribution of choices. The value of each number is equal the the percentage of opponent's choices that we are beating. We have to pick the number which has higher value. If we know this best response strategy, we can calculate what the resulting distribution of our picks will be. Next we can iterate to find opponent's best response in the same way. We can pick an initial distribution: pick randomly which is an uniform distribution of picks, then iterate on it. There is some chance this doesn't converge, but experimentally we find this is not the case.

Code: Using n = 10000 choices, and some dynamic programming, 100 iterations is more than enough to converge very nicely.

n = 10000

step = 1./(n-1)

iterations = 100

import matplotlib.pyplot as plt

dist = \[1./n\] \* n

values = \[0.\] \* n

for it in range(iterations):

    value\_action = \[\]

    cumulative\_dist = \[0.\] \* n

    s = 0.

    for i in range(n):

        s += dist\[i\]

        cumulative\_dist\[i\] = s - dist\[i\] / 2.

    for action in range(n):

        val = 0.

        val += cumulative\_dist\[int((action+1) / 3)\]

        if action \* 3 < n:

val += cumulative_dist[action * 3]

        else:

val += 1.

        val -= cumulative\_dist\[action\]

        value\_action.append((val, action))

    value\_action.sort()

    for i in range(n):

        val, ac = value\_action\[i\]

        dist\[ac\] = (2 \* i + 1.) / (n \* n)

        values\[ac\] = val

dist = \[x \* n for x in dist\]

actions = \[step \* x for x in range(n)\]

plt.plot(actions, values)

plt.xlabel('Choice')

plt.ylabel('Chance of winning')

[plt.show](https://plt.show)()

plt.plot(actions, dist)

plt.xlabel('Choice')

plt.ylabel('Probability')

[plt.show](https://plt.show)()

val, ac = value\_action\[n-1\]

print ('Action ' + str(ac / (n-1.)) + ' has highest chance of winning = ' + str(val))
/r/math Thread