Blackwell and Girshick about the concept of strategy:
Imagine that you are to play the White pieces in a single game of chess, and that you discover you are unable to be present for the occasion. There is available a deputy, who will represent you on the occasion, and who will carry out your instructions exactly, but who is absolutely unable to make any decisions of his own volition. Thus, in order to guarantee that your deputy will be able to conduct the White pieces throughout the game, your instructions to him must envisage every possible circumstance in which he may be required to move, and must specify, for each such circumstance, what his choice is to be. Any such complete set of instructions constitutes what we shall call a strategy.
Now think about an infinite game, like repeated prisoner’s dilemma. If we take the idea about strategy as set of instructions seriously then not every function from past histories to an action is something we would like to call a strategy, because not every function can be described by a set of instructions ! This should be clear even before we formalize what instructions mean, simply because the set of possible `instructions’ is countable, as every such instructions is just a sentence in English.
So what should be the formal definition of a strategy in these games, a definition that will capture the intuition of a complete set of instructions that specify what your choice is to be for each possible circumstances? You know what I think.
The Leisure of the Theory Class 
4 comments
April 5, 2010 at 9:29 pm
Emil Temnyalov
Is it generally agreed upon that there can only be countably many “instructions”? If we’re just talking about sentences in English, it seems like there might be uncountably many.
My first argument would be a variation on diagonalisation in the context of words: as long as you allow me to construct infinitely long sentences, if you give me an enumeration of all sentences in English I could construct one which is not in your enumeration. I’m not sure what people think about an infinitely long sentence, but I can imagine how basic examples might be constructed–e.g. “I know that you know that I know…” seems to be have a clearly understood meaning despite it being infinitely long.
What is the argument against there being infinitely long sentences, if it is appears that we can understand their meaning fine? (E.g. I think I understand what the sentence “I like r” means, for any real r.)
Perhaps a second, somewhat different argument would be that for every real number r, I can make the sentence “I like the number r”. Since there are uncountably many of the former, there must be uncountably many such imaginable sentences.
April 6, 2010 at 2:19 am
Jonathan Weinstein
Emil, it seems you are only counting infinitely long sentences if we can describe them to each other in finitely many symbols. Then you are still stuck in a countable set, although you’ve made it a bit bigger than before. By more and more sophisticated notation you can denote more and more things, but always countably many.
In other words, just adding infinite sentences that can be described using such tricks as “…and so on” doesn’t evade the countability trap. You need to include infinite sentences with no compressible pattern. I agree with Eran that these should not be considered strategies, except perhaps for convenience.
April 6, 2010 at 2:54 pm
Tweets that mention Complete set of instructions « The Leisure of the Theory Class -- Topsy.com
[…] This post was mentioned on Twitter by Ablenia Jones. Ablenia Jones said: Complete set of instructions « The Leisure of the Theory Class: The Leisure of the Theory Class. Feeds: Posts · Co… http://bit.ly/ar0ou3 […]
April 8, 2010 at 2:13 pm
Eilon
Consider a repeated game where both players have finitely many actions. The set of finite histories is countable, and therefore the set of pure strategies is the set of functions from the set of integers N to the set of actions. This set is equivalent to [0,1], so that every pure strategy is equivalent to a point in the unit interval.
Now, I have an agent and I would like to instruct him to play the strategy that corresponds to the number x. Easy: I simply tell him x. How do I do that? Indeed, if my language is finite and sentences are finite this may be difficult, but who said I must rely on my language? Suppose that I find a human whose height is exactly x. Then I tell my agent to choose that strategy that corresponds to the height of this person. Voila. Note that at every given stage the agent need not know all of x, but only some finite feature of x (e.g., the next digit in the binary expansion of x), and therefore he can use x to choose a strategy. Bottom line: language is not the only way to communicate information.
And if you say that our universe is finite, and therefore there are only finitely many possible heights, I would ask: and then how the game is repeated indefinitely. Or, who said that our universe is the only universe?