Understanding Rationalizability

This notes is about understanding the definition of rationalizability.

O&R is referring to Osborne & Rubinstein 's A course in game theory, which is openly accessible from Professor Rubinstein’s website and specifically here.

Professor Ou-yang’s video lecture is here.

When I was a master’s student, Professor Ou-Yang taught us game theory using the O&R textbook. A few years later, he recorded an online version of this course, along with his other courses, for the COVID-19 cohorts. The O&R textbook remains the primary reference for his master’s-level course, while his PhD-level course uses the MSZ textbook (Game Theory by Maschler, Solan, and Zamir). Something (not) interesting (at all): back when I was still in China, I bought two copies of the MSZ textbook from Book Depository (that website is dead now), quite expensive for me, but I didn’t bring either copy with me to Spain. Professor Ou-Yang has already delivered clear and amazing lectures in detail, but I’d like to add some interpretations. At least for me, these interpretations have been helpful for better understanding, and these interpretations are in line with my ‘kinks’ about those “subjective” things.

Now let’s take a look at the Definition 54.1 in O&R. An important thing to note is that, in this definition, the whole seemingly scary process is about the rationalizability of a single action of a single player, which is $a_{i} \in A_{i}$.

Now some concepts.

Suppose we aim to say that $a_{1}$ is rationalizable, which requires that, there should be a belief of player 1 (the player whose action we are trying to rationalize), such that $a_{1}$ is (one of) the best response to his belief.

Then, what is player 1’s belief? his belief is his subjective conjecture (a probability distribution) about what other people are going to do. In his conjecture, other people can cooperate, can collude,…, which is to say, in his mind, others are as if playing correlated strategies. Therefore, player 1’s belief lives within the same set as the set of correlated strategy profiles of player 2,3,…,N (if there are an N players) , i.e., $\mu_{1}\in\Delta(A_{2}\times A_{3}\times ... \times A_{N})$. His belief assigns each possible action combinations of his opponents a probability.

[Remember? the set of correlated strategy profiles is the single probability simplex over the Cartesian product of every player’s pure strategy space, i.e. $\Delta(\times_{i}S_{i})$, each one of whose elements is a correlated strategy profile (interprated as a probability distribution without requiring independence); while the set of mixed strategy profile is the Cartesian product over the probability simplices of every player’s pure strategy space, i.e. $\times_{i}\Delta(S_{i})$, each one of whose element $\sigma \in \times_{i}\Delta(S_{i})$ is the mixed strategy profile (interprated as a joint probability distribution requiring independence), although we don’t discriminate between $S_{i}$ and $A_{i}$ here since it is in the strategic form setting.

As we know, there are more possible probability distributions when independence is not required compared to when it is, and this is also why information design can be used as a coordinating device to induce results that would otherwise be impossible. Therefore, requiring $a_{1}$ to be a best response to a probability distribution that allows dependence (i.e., a belief) is a weaker condition, as it is easier to find such a probability distribution.]

Let’s now turn to a two-player example, where player 1 has only one opponent: player 2, so we can temporarily leave aside this correlation thing. This example is adapted from Professor Ou-yang’s video lecture.

so, as I said, player 1’s belief is his conjecture about what others are going to do, and since there is only one “others”, player 2, player 1’s belief would be $\mu_{1}\in\Delta(A_{2})$, living in the same set of player 2’s mixed strategies (since player 2 is the only opponent of player 1, player 2’s mixed strategy is the same as player 2’s (as if there is such a thing) ‘correlated strategy profile’, and player 2’s mixed strategy space is the same as player 2’s ‘correlated strategy profile’ space).

To say that $a_{1}$ is rationalizable, it must be the case that $a_{1}$ is (one of) the best response to the belief of himselves, $\mu_{1}^{1}$, interpretaed as a best response to his opponents’ correlated strategy that player 1 thinks they will take, and here it is a best response to player 2’s mixed strategy that player 1 thinks player 2 will take.

(the superindex in $\mu_{1}^{1}$ means that we are in the first step of the whole procedure, it is $t=1$ in O&R’s textbook as well as in Professor Ou-yang’s video; and the subindex means that it is player 1’s belief)

Denoting it as $a_{1}\in\mathbb{BR}_{1}(\mu_{1}^{1})$.

If player 1’s belief is $\mu_{1}^{1}$, it can be interprated that in player 1’s mind, he thinks that player 2’s mixed strategy will assign the same probability distribution as player 1’s belief: with some probability $p\prime=\mu_{1}^{1}(a_{2}\prime)$, player 2 will play action $a_{2}\prime$; with some probability $p\prime\prime=\mu_{1}^{1}(a_{2}\prime\prime)$, player 2 will play action $a_{2}\prime\prime$,…, all those probabilities are from player 1’s subjective thinking (His belief doesn’t have to be correct; it doesn’t have to be coincide with what player 2 is actually planning to do) but they have to satisfy the nonnegativity and sum into one restriction, as well as other conditions that makes it “reasonable” (I am not really using a terminology here, but its meaning will be clear below)

We denote the player 2 in player 1’ conjecture as $I_{1}(2)$, and denote those actions that $I_{1}(2)$ is going to play with strictly postive probabilities as

$$X_{2}^{1}=\{a_{2}\in A_{2}|a_{2}\in\text{support}(\mu_{1}^{1})\}$$

(where $a_{2}\in\text{support}(\mu_{1}^{1})$ means that $\mu_{1}^{1}(a_{2})>0$)

But if player 1 thinks that player 2 ($I_{1}(2)$, i.e. the player 2 in player 1’s mind) is going to play, for example, $a_{2}$, with a strictly positive probability, $\mu_{1}^{1}(a_{2})>0$, what would make his conjecture reasonable? To make his conjecture reasonable, it must be the case that if $I_{1}(2)$ is going to play $a_{2}$ with a strictly positive probability, then $a_{2}$ should also be (one of) the best response to $I_{1}(2)$'s some belief $\mu_{I_{1}(2)}^{2}$.

(In O&R’s book, or Professor Ou-yang’s video lecture,…, it is called "to player 2’s belief $\mu_{2}$". I intentionally abuse the notation here to make it clear that my interpretation is that all of these, as well as the steps following, happens in player 1’s mind, or from player 1’s perspective, because we are trying to rationalize his action $a_{1}$ rather than the action of someone else, althought I won’t introduce the similar cumbersome notation for actions)

To say that $a_{2}$ is (one of) the best response to $I_{1}(2)$'s some belief $\mu_{I_{1}(2)}^{2}$ means that $I_{1}(2)$ thinks that $I_{I_{1}(2)}(1)$ is going to play some action $a_{1}\prime$ with some probability $\mu_{I_{1}(2)}^{2}(a_{1}\prime)$, some action $a_{1}\prime\prime$ with some probability $\mu_{I_{1}(2)}^{2}(a_{1}\prime\prime)$,…, such that $a_{2}$ is an expected utility maximizer where the expectation is taking regarding $I_{I_{1}(2)}(1)$'s mixed strategy.

To interprate: if player 1 (the actual player 1) thinks that player 2 (the player 2 in player 1’ mind, $I_{1}(2)$) will play $a_{2}$ with a strcily positively probability, then it must be the case that player 1 thinks that player 2 ($I_{1}(2)$) will think that $a_{2}$ will be one of the best response against what player 1 ($I_{I_{1}(2)}(1)$) is going to do.

Which is

$$\forall a_{2} \in X_{2}^{1}, \exists \mu_{I_{1}(2)}^{2}\in\Delta(A_{1}) \text{ such that } a_{2}\in\mathbb{BR}_{I_{1}(2)}(\mu_{I_{1}(2)}^{2})$$

Now collect those actions $a_{1}\prime$ with $\mu_{I_{1}(2)}(a_{1}\prime)>0$, aka $a_{1}\prime \in\text{support}\mu_{I_{1}(2)}$ as $X_{I_{I_{1}(2)}(1)}^{2}$, i.e.

$$X_{I_{I_{1}(2)}(1)}^{2}=\{a_{1}\prime\in A_{1}|a_{1}\prime \in\text{support}\mu_{I_{1}(2)}\}$$

(which is just the $X_{1}^{2}$ in O&R.)

But then why $I_{1}(2)$ thinks that $I_{I_{1}(2)}(1)$ will play some $a_{1}\prime$ with strcily positive probability $\mu_{I_{1}(2)}^{2}(a_{1}\prime)>0$? It must be the case that there exists some belief

$$\forall a_{1}\prime \in X_{I_{I_{1}(2)}(1)}^{2}, \exists \mu_{I_{I_{1}(2)}(1)}^{2} \in \Delta(A_{2}) \text{ such that } a_{1}\prime \text{ is a best response to }\mu_{I_{I_{1}(2)}(1)}^{2}$$

(where $\mu_{I_{I_{1}(2)}(1)}^{2}$ is the $\mu_{1}^{2}$ in O&R)

,…, so on and so forth.

Notice that $X_{i}^{t+1}$ is left undefined (or defined as the empty set) (1) for $i=1$ when $t$ is even, or (2) for $i=2$ when $t$ is odd. This requires further elaboration when there are at least three players, just as the correlated strategy of opponents should be taken into account when there are at least three players (so at least two opponents).

To summerzie, to say $a_{1}$ is rationalizable requires that

1. $a_{1}$ is a best response to some belief $\mu_{1}^{1}$;

2. all those actions in the support of $\mu_{1}^{1}$ consitutes $X_{2}^{1}$, and every action $a_{2}$ in the support of $\mu_{1}^{1}$ (i.e. every $a_{2} \in X_{2}^{1}$) should itself also be a best response to some belief $\mu_{I_{1}(2)}^{2}$;

3. then every action in the support of $\mu_{I_{1}(2)}^{2}$ consitutes $X_{I_{I_{1}(2)}(1)}^{2}$, and every action in it should also itself be a best response to some belief,…

I hope this will make it clear the meaning of those $X_{j}^{t}$ in the definition as well as the fact that as $t$ increases, the reasoning is actually going backwards. (There is another definition, also using sequence of sets, which implements iterative elimination and therefore going forwards.)

let me pause here for now. (2025 Jan 8)