Plotting the distribution of SSE values

[drvinceknight]

From #107:

For some of the more interesting strategies can you plot the observed distributions of SSE? I would expect some that are skewed to toward 0, some toward 1, more U-shaped, and that more wins -> skewed toward 1 / more extortionate, higher mean score --> skewed toward U-shape / zero (but the U-shaped ones outscore those skewed more to zero). That might make an interesting figure, and there's maybe a story about a strategy being initially trusting but not naive.

Here is what this looks like for a small selection:

What do you think @marcharper?

[marcharper]

Seems like maybe the variance of the SSE has some relationship to tournament performance since the evolved strategies tend to have a few skewed points.

Are there any that skew to the right more? Maybe take a look at ALLC, ALLD, and Random(p) for p in np.range(0, 1.1., 0.1)?

[drvinceknight]

Seems like maybe the variance of the SSE has some relationship to tournament performance since the evolved strategies tend to have a few skewed points.

Yeah I suppose this points at the fact that successful strategies must be flexible? (Able to extort weaker ones and cooperate with stronger ones?)

Are there any that skew to the right more? Maybe take a look at ALLC, ALLD, and Random(p) for p in np.range(0, 1.1., 0.1)?

ALLC and ALLD, do not have a measured SSerror as they don't visit all states.

Here's a plot of the exact/expected SSerror for random(p) for p in np.range(0, 1.1., 0.01):

EDIT (Deleted a plot that's not helpful given the next one).

Played around with comparing mean to median and got a selection of ones with a negative skew (so they do exist!):

[marcharper]

Nice! Is there a relatively simple rule that indicates which strategies will perform well -- e.g. low median SSE but higher variance of SSE or something like that? Maybe something like median / variance?

[marcharper]

ALLC and ALLD, do not have a measured SSerror as they don't visit all states.

Have you though about a regularization / offset term to make this possible? For example when estimating odds ratios from contingency tables one can add a value C (equal to 0.5, 1, or...) to each entry so that there's no division of zero in the denominator. For large numbers of observations the asymptotic convergence of the statistic is unchanged.

It seems like this could be done for state_counter to potentially get estimates of SSE for strategies like ALLC:

def get_p_from_interactions(interactions):
    vectors = []
    for state_counter in iu.compute_state_to_action_distribution(interactions):
        p = []
        for state in ((C, C), (C, D), (D, C), (D, D)):
            a = max(1, state_counter[(state, C)])
            b = max(1, state_counter[(state, D)])
            p.append(a / (a + b))
        vectors.append(p)
    return vectors

For Cooperator this yields an SSE close to zero (and a p4 not close to zero):

players = (axl.Cooperator(), axl.EvolvedANN5())
axl.seed(0)
match = axl.Match(players, turns=parameters.TURNS)
interactions = match.play()
p = get_p_from_interactions(interactions=interactions)[1]
x, SSError = zd.get_least_squares(p)
SSError, p

(1.32352941162317e-07, [0.9995, 0.5, 0.5, 0.5])

For Defector the SSE is a larger (and p4 is close to zero):

players = (axl.Defector(), axl.EvolvedANN5())
axl.seed(0)
match = axl.Match(players, turns=parameters.TURNS)
interactions = match.play()
p = get_p_from_interactions(interactions=interactions)[1]
x, SSError = zd.get_least_squares(p)
SSError, p

(0.13235294117647056, [0.5, 0.5, 0.5, 0.0005002501250625312])

Something like this makes sense to me since p(C | (D, D)) for Cooperator is in fact 1 and the method shouldn't fail just because a strategy doesn't visit a state.

I think this idea may be effectively similar to evaluating the strategies in noisy environments, which forces some visits to every state given enough interactions.

eps = list(np.arange(0.005, 0.2, 0.001))
sses = []
for ep in eps:
    players = (axl.Cooperator(), axl.EvolvedANN5())
#     axl.seed(0)
    match = axl.Match(players, turns=10000, noise=ep)
    interactions = match.play()
    p = get_p_from_interactions(interactions=interactions)[1]
    x, SSError = zd.get_least_squares(p)
    sses.append(SSError)

plt.scatter(eps, sses)
plt.xlabel("Noise")
plt.ylabel("SSError")

This produces a plot that converges to zero for Cooperator, which makes sense.

[drvinceknight]

Good idea @marcharper!

It's definitely an improvement on my ¯_(ツ)_/¯ approach to the missing states. Getting valid measures is also going to be interesting with regards to #111, with more data we might get a more pronounced relationship between the error and fixation.

I think there are some minor issues using your suggested approach (but I might be wrong so let's figure it out :)).

The code snippets you sent are actually giving the measures for axl.EvolvedANN5() right? Not for Cooperator/Defector (because of get_p_from_interactions(interactions=interactions)[1]) - perhaps this is what you intended?

If we do the computation for Cooperator we get:

>>> players = (axl.Cooperator(), axl.EvolvedANN5())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[0]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(1.32352941162317e-07, [0.9995, 0.5, 0.5, 0.5])

Similarly for Defector:

>>> players = (axl.Defector(), axl.EvolvedANN5())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[0]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.04764705882352943, [0.5, 0.5, 0.2, 0.000501002004008016])

If we take a look at the same thing against Alternator (for the benefit of simplicity):

>>> players = (axl.Cooperator(), axl.Alternator())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[0]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.058940882353469476, [0.999000999000999, 0.999, 0.5, 0.5])

>>> players = (axl.Defector(), axl.Alternator())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[0]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.014823646706469684, [0.5, 0.5, 0.000999000999000999, 0.001])

What this approach is doing is twofold:

1. Adding slight "error" to the states for which we have observations (that as you pointed out will indeed converge to the correct value).
2. Giving a $p_s$ of $1/2$ (as a=1 and b=1) for states that are not visited. Essentially saying that with no prior information the best guess at a probability of cooperating is $1/2$.

So for example, using this approach we have for Defector $p(C | CC)=1/2$ whereas we know that for Defector $p(C | CC)=0$.

Another approach would be a somewhat Bayesian (?) approach that uses the tiny bit of prior information that we do have. In the case of the history of a state being $\emptyset$ why not replace that with the overall empty history?

This essentially corresponds to, for a history $h$:

$p(C | s) = |{s' \to C \in h | s' = s}| / |{s' \in h | s' = s}|$

but if ${s' \in h | s' = s}\emptyset$ then replace the above with $\emptyset$:

$p(C | s) = |{s' \to C \in h | s' = \emptyset}| / |{s' \in h | s' = \emptyset}|$

This would imply that in the case of an empty set of given interactions we just use the initial play of a strategy as an approximation.

def get_p_from_interactions(interactions):
    vectors = []
    initial_actions = interactions[0]
    for state_counter, initial_action, in zip(iu.compute_state_to_action_distribution(interactions),
                                             initial_actions):
        p = []
        for state in ((C, C), (C, D), (D, C), (D, D)):
            try:
                a = state_counter[(state, C)]
                b = state_counter[(state, D)]
                p.append(a / (a + b))
            except ZeroDivisionError:
                p.append(int(initial_action == C))
        vectors.append(p)
    return vectors

This now gives:

>>> players = (axl.Defector(), axl.Alternator())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[0]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.0588235294117645, [0, 0, 0.0, 0.0])

>>> players = (axl.Cooperator(), axl.Alternator())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[0]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.23529411764705888, [1.0, 1.0, 1, 1])

If we use this to also compute the SSerror of EvolvedANN5 against both these strategies we then get:

>>> players = (axl.Defector(), axl.EvolvedANN5())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[1]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.13235294117647056, [1, 1, 0.75, 0.0])

>>> players = (axl.Cooperator(), axl.EvolvedANN5())
>>> axl.seed(0)
>>> match = axl.Match(players, turns=2000)
>>> interactions = match.play()
>>> p = get_p_from_interactions(interactions=interactions)[1]
>>> x, SSError = zd.get_least_squares(p)
>>> SSError, p
(0.23529411764705888, [1.0, 1, 1, 1])

So EvolvedANN5 acts slight more extortionately against the weaker Cooperator.

This essentially corresponds to your suggestion without the slight noise for cases that we have history for and with a (I'd suggest) "better" guess for states we don't.

Let me know what you think.

[marcharper]

Thanks for catching that mistake.

I like the idea of using prior information or history to compute the missing values and I think we can do a little better than using the first play. We can do this by using all the history: if a state has no visits then we impute a probability of cooperation by averaging over all other plays, which should still give 0 and 1 for Cooperator and Defector respectively, p for Random(p), and 1/2 for Alternator.

I'm not sure if that is better than the first move for the majority of strategies, but given that a lot of strategies cooperate on the first move and then do something very different afterward it seems like a good extension.

[drvinceknight]

Yeah that's a much better idea. I've been exploring my first play suggestion today but using the whole history is surely a way better approach.

I'll give that a whirl and aim to push up a PR today/tomorrow with a bit more analysis and also some improvement to the narrative (but I suspect once this is all in and we're happy, it'll need to be revised further).