> It's true, however, that this leads to a very interesting consequence which is not discussed in this context, something quite convoluted: "I will commit to a first-order Markov strategy in order to prevent my opponent from using a higher-order Markov strategy, so that my own analysis of their strategy simplifies." It is a curious statement that your own ignorance forces someone else to be ignorant, which you can then exploit.
This is only true if you know the strategy of the enemy beforehand, though. For instance if you play rock-paper-scissors and decide your move only based on the previous move your enemy can easily exploit that after playing for a while. It is true that the enemy doesn't have to remember more than one move after he learns your strategy but he needs to remember many moves to learn it.
1. No, that statement is still true even if you don't know the higher-order strategy of your opponent: no matter what it is, it has the same payoffs as some lower-order strategy.
2. You would have to define "exploit that," especially with the understanding that this is game theory and probabilistic strategies are certainly encouraged. So for example, you might imagine a genius who can consistently outthink you, knows your entire history and how you like to play Rock-Paper-Scissors and immediately as you throw down Rock, simply is able to guess that this is what you're likely to do, and throws Paper.
You can beat this guy. Or, more precisely, you can equal him. It's very simple: before the day has begun, roll a six-sided die and memorize the sequence. As long as they are not exploiting certain "tells" (as a Japanese robot did in the news a week or two ago) -- as long as they are just making a deduction based upon the sort of person you are, they cannot produce a net win against you and you're safe. Indeed, the Nash equilibrium for RPS is not terribly interesting, it's to choose each of the options with probability 1/3rd -- I don't really have much reason to believe that this changes dramatically in iterated RPS.
1. I agree with what you say. There exists a low-order strategy that has the same payoff against the low-order strategy your opponent uses, and you can use that if you know your opponent's strategy. However, in many games there aren't low-order strategies that would work well against any low-order strategy so you need to know the opponent's strategy to choose a proper low-order strategy. Alternatively you could use a higher order strategy that learns the opponent's strategy and adapts to it.
2. Well, I was thinking that a strategy would be a mapping from game history to a probability distribution over possible moves. Should this be considered in some other way?
Sure, you can just play according to the Nash equilibrium and you can't be exploited, but probably a more interesting case is when both players try to outsmart the other player and not just aim for a draw.
This is only true if you know the strategy of the enemy beforehand, though. For instance if you play rock-paper-scissors and decide your move only based on the previous move your enemy can easily exploit that after playing for a while. It is true that the enemy doesn't have to remember more than one move after he learns your strategy but he needs to remember many moves to learn it.