[plexiq]

[ QUOTE ]
This seems to fly in the face of what I know about NE states though, as it shouldn't be possible for a player to deviate profitably from a NE (assuming the above algorithm really does converge to a NE).

[/ QUOTE ]

Well, the definition of a NE is still satisfied. No player can unilaterally deviate from the NE to gain value. Thats true in your example - if only 1 player deviates, he cant improve.

If you assume bot-like players who wont deviate from the NE no matter what happens, then your best choice is to play the NE as well.

That said, i think the problem you describe is inherent in the definition of the NE. It doesnt really matter what algorithm we would use to find (or approximate) the NE.

Some kind of "raw" first idea, didnt really think it through yet:
Instead of optimizing the "current" equity (ie, playing maximally exploitative), each player tries to "drag" the strategies in a direction that will give him better equity than the current state - but only as long as his deviation from maximally exploitative play costs the respective opponents more EV than him.

This should converge to a more "robust" set of strategies. But then, these strategies will be easily exploitable by opponents who simply skip their "spite calls".

This gets pretty interesting if you think about it. If we draw random players from a population of 50% NE, and 50% "spite callers" and put them into a game, the spite caller population would have a higher expectation in this game, i think.

Need to think it through before posting any more. I hope the above makes any sense, lol.