Add probabilistic ending variant about axelrod HOT 11 CLOSED

I don't understand. A variable length tournament?

from axelrod.

This is a thing because if you know the number of rounds in advance it's sometimes possible to "back-solve" more optimal strategies. So people often study games of finite but arbitrary length to eliminate this possibility.

from axelrod.

Now I understand. I've read about this before, too.

What does "back-solving" mean?

from axelrod.

I'm not sure if it's the right technical term, but it means that if you know the game is exactly 50 rounds then you can infer what the optimal sequence of plays would be. For example versus TFT you would cooperate until the last round and then defect (getting the sucker payoff but avoiding the punishment since the game ends). But if you didn't know the game was about to end you wouldn't do this because it's usually better to get two cooperation payouts rather than one sucker and one mutual defection payout (depending on the game matrix, of course).

So the number of rounds is a parameter that a strategy has to include in its optimization if it's not arbitrary. If the game is indefinitely long then you might be better off trying to maximize your stationary score (for two memory one players) or your long term score in general.

from axelrod.

Here's a flexible way to do this that aligns with some approaches in the literature. Play N rounds as tournaments already do, then have a probability p that the game ends after each subsequent round. Then the expected number of rounds past N is ~1/p (but the actual number of rounds is potentially unbounded). Some approaches in the literature do this with N=0 or larger.

Alternatively we could draw the number of rounds from a scipy/numpy random variable and play exactly that many rounds. However cheating strategies could try to discover the number of rounds and use it to their advantage (but that's not a big deal really).

Finally we could do both. Draw from a distribution to ensure that the number of rounds is bounded, e.g. start with a Bernoulli distribution of probability p, calculate the distribution of expected first success (i.e. the number of additional rounds), and then pass N + (a draw) in as the number of rounds. Still allows for cheating but at least the tournament runs for a fixed number of rounds. I think the distribution is just a negative binomial NB(1, 1-p), which scipy and numpy both implement.

from axelrod.

I would suggest going with your first approach mainly for simplicity and the fact that that also corresponds to a model of a discounted infinitely repeated game. When I opened this issue it was mainly because I'd just taught infinitely repeated games in class and wished I could have shown an example of a discounted game to my students :)

As far as unbounded length games and cheaters are concerned, here's my thoughts:

• I don't think it's a problem. As long as p>1 it will at some point end and if parameter choice makes it last a super long time that's just the user's choice.
• I wouldn't worry too much about the cheaters, those strategies are actively welcome and just get separated from the rest of the strategies.

Re scipy and numpy there is a current issue about whether or not to use numpy at #158 (at the moment the whole tournament runs and works in base python).

👍

from axelrod.

I guess there's nothing stopping a user now from using a negative binomial to determine the number of rounds and then passing that in to the tournament. From the outside this would be indistinguishable from a tournament that draws against p each round to determine if it should stop.

I don't really have an opinion on the numpy issue, though matplotlib depends on numpy already.

from axelrod.

Yup but matplotlib is wrapped so the library shouldn't crash if it's not
available, but yeah that issue is very much a reopening of the discussion.

On Thu, 7 May 2015 17:25 Marc Harper [email protected] wrote:

I guess there's nothing stopping a user now from using a negative binomial
to determine the number of rounds and then passing that in to the
tournament. From the outside this would be indistinguishable from a a
tournament that draws against p each round to determine if it should stop.

I don't really have an opinion on the numpy issue, though matplotlib
depends on numpy already.

—
Reply to this email directly or view it on GitHub
#37 (comment)
.

from axelrod.

FYI, the second axelrod tournament was setup to end with probability 0.00346 each round, which was supposed to ensure that there would be a median of 200 rounds::

As announced in the rules, the length of the games was determined
probabilistically with a .00346 chance of ending with each given move.
This parameter was chosen so that the expected median length of a
game would be 200 moves. In practice, each pair of players was matched
five times, and the lengths of these five games were determined once and
for all by drawing a random sample. The resulting random sample from
the implied distribution specified that the five games for each pair of
players would be of lengths 63, 77, 151, and 308 moves. Thus the average
length of a game turned out to be somewhat shorter than expected at 151
moves. Since no one knew exactly when the last move would

Ref: http://www.artisresearch.com/articles/Axelrod_Prisoners_Dilemma.pdf

from axelrod.

Ok, I'm starting to take a look at this.

Based on @marcharper:

Here's a flexible way to do this that aligns with some approaches in the literature. Play N rounds as tournaments already do, then have a probability p that the game ends after each subsequent round. Then the expected number of rounds past N is ~1/p (but the actual number of rounds is potentially unbounded). Some approaches in the literature do this with N=0 or larger.

I suggest modifying the tournament function to take a probability_of_match_ending parameter (perhaps p for short...) that would by default have value p=1 (so that once turns is reached if no p is passed the tournament would behave as before).

This would take adding a little bit to the RoundRobin class and obviously looking at the results class carefully.

Does anyone have any thoughts (in particular @meatballs is this going to potentially mess with any of the deep stuff you're working on)?

from axelrod.

🎉

from axelrod.