2
$\begingroup$

As undergraduates often note, the definition of a strategy appears to be rather strange in the context of repeated games. To illustrate, consider a very simple game in which one player needs to make a decision twice. Every time they need to make the decision, they have 2 possible choices -- call them A or B. Ordinarily, we would think of this person as having $4$ possible (pure) strategies: choose A twice, choose B twice, choose A then B, or choose B then A. According to the standard definition, however, we would say that there are 2 possible histories (A or B); and that a strategy must specify what happens following every possible history. As a result, the player really has $2^3 = 8$ pure strategies! Moreover, each of these strategies specifies what would happen in an impossible situation; namely, if the person were to have made a different choice in the first stage than the one they planned to make.

In case this doesn't seem strange to you, let me provide an example of a pure strategy (I'll put it verbally to convey the full force of the strangeness):

In the first round, I will choose action A. After choosing A, I will then choose A again. However, if I had chosen B in the first round, then I would then have chosen B again in the second round.

My question is why we need to include this last sentence.

Before finally posing my question, I also want to note that this question is not specific to the rather trivial game above. Obviously, one can devise similar examples for more complex multi-player games.

Question: Why does the standard notion of 'strategy' force players to specify what they would do in situations that they know will never arise given their choices earlier in the game? And can we prove standard results (e.g. existence of a Nash equilibrium in extensive games) without making use of this rather un-natural concept of a strategy?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\begingroup$

Your proposed notion of what a strategy should be in repeated game can be adapted to all extensive form games has been called a plan of action by Ariel Rubinstein, who discusses this and related issues in the paper

Rubinstein, Ariel. "Comments on the interpretation of game theory." Econometrica: Journal of the Econometric Society (1991): 909-924.

Some concepts become harder to define, such as backward induction in games of perfect information. However, one can still do pretty much all of game theory. The book " Rationality in extensive form games" by Andres Perea uses the definition as a plan of action throughout.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this. I assume that one can still prove the existence of a Nash equilibrium for (finite) extensive games using the 'plan of action' concept? $\endgroup$
    – afreelunch
    May 26, 2021 at 16:12
  • $\begingroup$ Yes, each strategy in a traditional sense maps to a canonical plan of action that will always give the same payoff. $\endgroup$
    – Michael Greinecker
    May 26, 2021 at 16:29
4
$\begingroup$

The standard definition of a strategy assigns an action to every decision node/information set. This definiton is at least a jack of all trades; it works well in most cases and sometimes leads to slightly annoying notations that seem overcomplicated. I argue that changing the definition of strategy on a case-by-case basis would probably lead to more confusion. (You can refute me by proposing an exact yet general definition that accomodates your concept.)

Also note that if you do not assign an action to every decision node/information set, in a more complicated game you may run into trouble when you examine different strategies of the other players, and suddenly you reach a decision node that you mistakenly thought was unreachable. (This is also a common mistake made by undergrads.) Assigning an action everywhere is a safe bet.

Finally you would also need to adjust other definitions, such as subgame perfectness, to fit your new concept of strategy, as it would leave subgames without any actions assigned.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes I do agree that assigning actions everywhere seems "safe". But I wonder whether it also facilitates application of the Nash theorem? (After converting sequential games into normal form.) Or can this be done with a more natural definition? $\endgroup$
    – afreelunch
    May 25, 2021 at 22:41
  • $\begingroup$ What exactly would this "more natural definition" be? (Please be rigorous.) $\endgroup$
    – Giskard
    May 25, 2021 at 22:41
  • $\begingroup$ Also, you were asking specifically about repeated games; converting to normal form seems strange; you lose a lot of the structure of the game. $\endgroup$
    – Giskard
    May 25, 2021 at 22:42
  • $\begingroup$ 1. I have in mind something like: assign an action at every information set, except those information sets which cannot be reached given the actions you chose at previous nodes [one could formalise but would take some time/space!] 2. I think this is the standard way to prove equilibrium existence for repeated games? $\endgroup$
    – afreelunch
    May 25, 2021 at 22:43
  • 1
    $\begingroup$ 1. As I explained in my answer, in actual games (more than one player) it would not always be easy to verify if something is a strategy according to your definition. (How do I find nodes that are for sure unreachable?) 2. In repeated games you usually want subgame perfect/sequential equilibria, which are usually found without conversion to normal form. $\endgroup$
    – Giskard
    May 25, 2021 at 22:46
4
$\begingroup$

I don't find the definition of a strategy strange at all. In contrast, it seems to be the most natural way and other ways seem to run into problem once applied to general games.

As Giskard said, a strategy maps a decision node/information set into an action. In repeated games, this corresponds to mapping a history (what has happened so far) into an action. To evaluate the profitability of a deviation it is necessary to specify off-path behavior.

Draw a game tree like this: Player 1 can play A and payoff is (2,0), or play B after which player 2 can choose a or b. After B-a payoff is (0,2), after B-b, player 1 can choose C or D with payoffs (5,2) and (0,0). Now would you say "player 1 plays A" is a full strategy? After all, the game is over and all off-path behavior is irrelevant. Of course this does not make sense, because 1 needs to know what 2 does in case 1 plays B. Otherwise who knows if a deviation to B pays off? Maybe 1 would get 5 instead of just 2 - or she gets 0. So let's specify that 2 plays a. Then 1 knows that deviating 2 B does not pay off.... but what about 2? Now, 2 doesn't know what would happen if she played b. So we need to specify that, too, and so on.

Your example of a repeated one-player game is weird to begin with. Why should there be a repeated game of just one player? It is just a repetition of the same game and past behavior does not influence future play. But even in this game a strategy should be a full plan of actions. Suppose you have made a mistake and played B in the first period, then what do you do in the second period? The strategy you propose can also be captured verbally by "Always play the action played in the previous period. Play A in the first period." Does this sound strange to you? In repeated games, you usually do not write down an action for every single history one-by-one, because the main interest is on infinitely repeated games and there are infinitely many histories.

Let's take an infinitely repeated prisoner's dilemma. How would you specify a strategy? If you only specify that both players cooperate(C) if both cooperated before, you cannot evaluate if a deviation to defect (D) is profitable. How would your "more natural approach" take care of this? What would be the notion of subgame perfection? For instance, the grim-trigger strategy "Play C in beginning, play C if opponent always played C so far, otherwise play D forever" is a Nash equilibrium for high discount factors $\delta$. However, it is not a subgame-perfect Nash equilibrium for any $\delta$. In contrast, the grim-trigger strategy "Play C in beginning, play C if everyone always played C so far, otherwise play D forever" would be subgame-perfect for large $\delta$.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ 1/2 I don't think the OP intends to limit assigning actions strictly to the path travelled by the strategy profile. E.g. in a two player two stage prisoner's dilemma, the usual definition of strategy would assign five actions, while the OP's concept would only assign three. Player 1's tit-for-tat strategy starting with cooperation would assign C to the starting node, assign C to the stage two node where both players played C in stage 1, assign D to the node where player 1 played C but player 2 played D in stage 1, and not assign anything to the other two nodes, $\endgroup$
    – Giskard
    May 26, 2021 at 12:18
  • 1
    $\begingroup$ 2/2 because player 1's first action makes those nodes (which follow player 1 playing D in stage 1) unreachable. This still allows us to examine whether a strategy profile constitutes an equilibrium or if there are profitable deviations. In case of a tit-for-that profile, your answer seems to argue against only assigning two actions: one to the first node (the root), and one to the node that follows both players playing C. This would indeed make it impossible to investigate deviations, but I don't think this is the OP's recommendation. $\endgroup$
    – Giskard
    May 26, 2021 at 12:18
  • 1
    $\begingroup$ I see. This kind of confusion suggests that OP's notion is not obviously more natural. In addition, I don't see how, with this notion, stating a strategy becomes any easier or note natural in an infinitely repeated game. $\endgroup$
    – Bayesian
    May 26, 2021 at 15:09
  • $\begingroup$ @Bayesian Indeed, the suggestion was certainly not to remove all actions that may be on the equilibrium path from the definition of a strategy. Instead, the suggestion is to remove actions which will necessarily be off the equilibrium path (regardless of the strategies chosen by the other players). $\endgroup$
    – afreelunch
    May 26, 2021 at 16:07
  • $\begingroup$ Regarding "strangeness": my main claim was that, in real strategic situations, people do not spend much time thinking about what they would do in situations in which they know they could never possibly end up. (For example, since I haven't decided to spend today in Paris, Rome or Venice, I also haven't made plans about what I would have done today in Paris, Rome or Venice.) Any game theoretic model which assumes that I do make all such plans seems quite unrealistic. $\endgroup$
    – afreelunch
    May 26, 2021 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.