2x2 Zero-Sum Games with Commitments and Noisy
Observations

Ke Sun, Samir M. Perlaza, Alain Jean-Marie

► To cite this version:

Ke Sun, Samir M. Perlaza, Alain Jean-Marie. 2x2 Zero-Sum Games with Commitments and Noisy Observations. ISIT 2023 - IEEE International Symposium on Information Theory, Jun 2023, Taipei, Taiwan. 10.1109/ISIT54713.2023.10206806. hal-04091712v2

HAL Id: hal-04091712

https://inria.hal.science/hal-04091712v2

Submitted on 11 May 2023

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# 2 × 2 Zero-Sum Games with Commitments and Noisy Observations

Ke Sun*, Samir M. Perlaza†‡§, Alain Jean-Marie†

*School of Computer Engineering and Science, Shanghai University, Shanghai, China

†INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France.

‡ECE Dept. Princeton University, Princeton, 08544 NJ, USA.

§GAATI, Université de la Polynésie Française, Faaa, French Polynesia.

**Abstract**— In this paper, 2 × 2 zero-sum games are studied under the following assumptions: (1) One of the players (the leader) commits to choose its actions by sampling a given probability measure (strategy); (2) The leader announces its action, which is observed by its opponent (the follower) through a binary channel; and (3) the follower chooses its strategy based on the knowledge of the leader's strategy and the noisy observation of the leader's action. Under these conditions, the equilibrium is shown to always exist. Interestingly, even subject to noise, observing the actions of the leader is shown to be either beneficial or immaterial for the follower. More specifically, the payoff at the equilibrium of this game is upper bounded by the payoff at the Stackelberg equilibrium (SE) in pure strategies; and lower bounded by the payoff at the Nash equilibrium, which is equivalent to the SE in mixed strategies. Finally, necessary and sufficient conditions for observing the payoff at equilibrium to be equal to its lower bound are presented. Sufficient conditions for the payoff at equilibrium to be equal to its upper bound are also presented.

## I. INTRODUCTION

Zero-sum games (ZSGs) are mathematical models describing the interaction of mutually adversarial decision makers. Two solution concepts are often adopted for predicting the outcome of ZSGs: the Nash equilibrium (NE) [1] and the Stackelberg equilibrium (SE) [2]. The NE is a prediction observed under the assumption that both players simultaneously choose their strategies (probability measures over the set of possible actions). On the other hand, the SE describes the outcome in which one of the players (the leader) commits to use a particular strategy before its opponent (the follower). In such a case, the follower chooses its strategy as a best response to the commitment of the leader. Commitments are said to be in mixed strategies when the leader is allowed to commit to strategies whose support contains more than one action. In this case, the relevant solution concept is the SE in mixed strategies [3]–[6]. Interestingly, in ZSGs, the payoffs at the NE and the SE in mixed strategies are identical, as shown in [7]. The commitment is said to be in pure strategies when the leader is constrained to commit to play one action with probability one. This is assimilated to the case in which the follower perfectly observes the action played by the leader.

The relevant solution concept under these assumptions is the SE in pure strategies [2], [8], [9]. The expected payoff at the SE in pure strategies is equal to the min max or max min solution, where the optimization is over the set of actions [10], [11]. In this case, the payoff at the SE in pure strategies might be significantly different from the payoff at the NE.

In a nutshell, the underlying assumption of the SE in mixed strategies is that the strategy to which the leader commits to is perfectly observed by the follower and the actions are unobservable. Alternatively, the assumption of the SE in pure strategies is that actions are perfectly observable, which makes the notion of commitment irrelevant. This is essentially because the follower can always respond with an optimal action to the action played by the leader, regardless of the commitment. Nonetheless, often, the actions of the leader are neither unobservable nor perfectly observed. Instead, observations might be obtained subject to noise.

### A. Previous Works

The analysis of noisy observations of the actions played by a leader in ZSGs started in the realm of information theory [12]. Therein, an external entity referred to as the *informant* observes the action of the leader, encodes it and transmits it through a discrete memoryless channel (DMC) to the follower. The latter decodes the action of its opponent and thus, chooses its own action. In [12], commitments are not considered and the observation is noisy due to the impairments typical to data-transmission. In the realm of game theory, bipMatrix games with commitments and observability started with the work of Bagwell [13]. Therein, the leader is restricted to commit to a pure strategy, while the follower might observe a different pure strategy with positive probability. Note that this game is identical to a game without commitments in which the leader plays an action while the follower observes a different action with positive probability before choosing its own action, as described in numerous scenarios [14]–[20].

### B. Contributions

For pedagogical purposes, the analysis is restricted to two-player two-action ZSGs, which capture all interesting challenges due to the noisy observations in the presence of commitments. One of the main contributions is a new game formulation in which the follower obtains a noisy observation

<footnote>This work is supported by the Inria Exploratory Action – Information and Decision Making (AEx IDEM). Ke Sun was with INRIA while developing the majority of this work.</footnote>
of the action played by the leader, whereas the commitment is assumed to be perfectly observed. The game is proved to always possess an equilibrium. The optimal commitments are characterized and the set of best responses of the follower is thoroughly described. An explicit expression for the payoff at the equilibrium is derived. The payoff at equilibrium is greater than the payoff at the NE exclusively when the ZSG exhibits a unique NE in mixed strategies. In all other cases, e.g., ZSG exhibiting strategic dominance, unique NE in pure strategies, or infinitely many NEs, the payoffs with and without observations are identical. When the observation of the action of the leader is noiseless, the payoff at the equilibrium is the same as the payoff at the SE in pure strategies.

## II. GAME FORMULATION

Consider a two-player zero-sum game in normal form with a payoff matrix

$$ \underline{u} = \begin{pmatrix} u_{1,1} & u_{1,2} \\ u_{2,1} & u_{2,2} \end{pmatrix}. \quad (1) $$

Let the elements of the set $\mathcal{K} \triangleq \{1, 2\}$ represent the indices of the players; and let the elements of the set $A_1 = A_2 \triangleq \{a_1, a_2\}$ represent the actions of the players. Hence, for all $(i, j) \in \{1, 2\}^2$, when Player 1 plays $a_i$ and Player 2 plays $a_j$, the outcome of the game is $u_{i,j}$. Player 1 and Player 2 choose their actions to maximize and minimize their payoffs, respectively. When players simultaneously choose their actions in the absence of commitments, the game is represented by the tuple

$$ \mathcal{G}(\underline{u}) \triangleq (\mathcal{K}, A_1, A_2, \underline{u}), \quad (2) $$

and the solution concept is the NE.

When the game is played with commitments and noisy observations, it unfolds in three stages. In the first stage, Player 2 announces its strategy to Player 1 and commits to choose its actions by using such a strategy. A strategy for Player 2 is a probability measure denoted by $P_{A_2} \in \Delta(A_2)$. In stage two, Player 2 plays action $b \in A_2$ with probability $P_{A_2}(b)$, while Player 1 observes action $\tilde{b} \in A_2$ with probability $P_{\tilde{A}_2|A_2=b}(\tilde{b})$. That is, Player 1 obtains a noisy observation of the action played by Player 2. The tuple of probability measures

$$ P_{\tilde{A}_2|A_2} \triangleq (P_{\tilde{A}_2|A_2=a_1}, P_{\tilde{A}_2|A_2=a_2}) \in \Delta(A_2)^2, \quad (3) $$

which is a parameter of the game, defines a discrete memoryless channel (DMC) as in [21], [22]. In the final stage, Player 1 plays the action $a \in A_1$, with probability $P_{A_1|\tilde{A}_2=\tilde{b}}(a)$ and both players obtain their payoffs.

A strategy for Player 1 is a tuple of probability measures

$$ P_{A_1|\tilde{A}_2} \triangleq (P_{A_1|\tilde{A}_2=a_1}, P_{A_1|\tilde{A}_2=a_2}) \in \Delta(A_1)^2, \quad (4) $$

which is chosen based on the commitment (the probability measure $P_{A_2}$). Player 1 chooses its action by sampling the probability measure $P_{A_1|\tilde{A}_2=\tilde{b}}$, which is conditioned on the noisy observation $\tilde{b}$.

The expected payoff obtained by the players is determined by the function $v: \Delta(A_1)^2 \times \Delta(A_2) \to \mathbb{R}$, such that given the strategy $P_{A_1|\tilde{A}_2}$ in (4) of Player 1 and the strategy $P_{A_2}$ of Player 2, the expected payoff is

$$ \begin{aligned} v(P_{A_1|\tilde{A}_2}, P_{A_2}) &= \sum_{(i,j) \in \{1,2\}^2} u_{i,j} \left( \sum_{\tilde{b} \in A_2} P_{A_1|\tilde{A}_2=\tilde{b}}(a_i) P_{\tilde{A}_2|A_2=a_j}(\tilde{b}) \right) P_{A_2}(a_j). \end{aligned} \quad (5) $$

Often, it is said that Player 2 acts as the leader and Player 1 acts as the follower to highlight the order in which players choose their actions.

The extension of the game $\mathcal{G}(\underline{u})$ in (2) to capture commitments and noisy observations through the DMC in (3) is represented by the tuple:

$$ \mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2}) \triangleq (\mathcal{K}, A_1, A_2, \underline{u}, P_{\tilde{A}_2|A_2}). \quad (6) $$

### A. Equilibrium

The set of best responses of Player 1 to the commitment announced by Player 2 is determined by the correspondence $BR_1: \Delta(A_2) \to \mathcal{F}(\Delta(A_1)^2)$, where $\mathcal{F}(\Delta(A_1)^2)$ denotes the power set of $\Delta(A_1) \times \Delta(A_1)$. In particular, the set of best responses to the commitment $P_{A_2}$ is

$$ BR_1(P_{A_2}) = \arg \max_{Q_{A_1|\tilde{A}_2} \in \Delta(A_1)^2} v(Q_{A_1|\tilde{A}_2}, P_{A_2}), \quad (7) $$

where the function $v$ is defined in (5). Let the real-valued function $\hat{v}: \Delta(A_2) \to \mathbb{R}$ be such that

$$ \hat{v}(P_{A_2}) = \max_{Q_{A_1|\tilde{A}_2} \in BR_1(P_{A_2})} v(Q_{A_1|\tilde{A}_2}, P_{A_2}), \quad (8) $$

where the function $v$ is defined in (5), and the correspondence $BR_1$ is defined in (7). Player 2 chooses its strategy (commitment) $P_{A_2}$ assuming that Player 1 uses a best response to such strategy. Hence, the optimal commitments are the minimizers of $\hat{v}$ in (8).

Equipped with these objects, the solution concept for the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6) is the following.

**Definition 1 (Equilibrium).** The tuple $(P_{A_1|\tilde{A}_2}, P_{A_2}) \in \Delta(A_1)^2 \times \Delta(A_2)$ is said to form an equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ if

$$ P_{A_2} \in \arg \min_{P \in \Delta(A_2)} \hat{v}(P) \quad \text{and} \quad (9) $$

$$ P_{A_1|\tilde{A}_2} \in BR_1(P_{A_2}), \quad (10) $$

where the function $\hat{v}$ is in (8), and the correspondence $BR_1$ is in (7).

## III. PRELIMINARIES

The interest on the game $\mathcal{G}(\underline{u})$ in (2) stems from the fact that its payoff at the NE is equivalent to the payoff at the equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6), under the assumption that Player 1 does not obtain any information about the action played by Player 2 from the output of the
DMC. That is, $I(P_{\tilde{A}_2|A_2}; P) = 0$ for all $P \in \Delta(A_2)$, where $I(\cdot; \cdot)$ is the mutual information. Let the expected payoff in the game $\mathcal{G}(\underline{u})$ be represented by the function $u: \Delta(A_1) \times \Delta(A_2) \to \mathbb{R}$ such that, given the strategies $P_{A_1}$ and $P_{A_2}$,

$$u(P_{A_1}, P_{A_2}) = \sum_{(i,j) \in \{1,2\}^2} P_{A_1}(a_i) P_{A_2}(a_j) u_{i,j}. \quad (11)$$

The following lemma characterizes the payoff at the NE of the game $\mathcal{G}(\underline{u})$ and shows that $2 \times 2$ ZSGs exhibit either a unique NE or infinitely many NEs.

**Lemma 1 (Theorem 1.5 in [23]).** Let the probability measures $P_{A_1}^* \in \Delta(A_1)$ and $P_{A_2}^* \in \Delta(A_2)$ form a NE of the game $\mathcal{G}(\underline{u})$ in (2). If the entries of the matrix $\underline{u}$ in (1) satisfy

$$(u_{1,1} - u_{1,2})(u_{2,2} - u_{2,1}) > 0 \quad \text{and} \quad (12a)$$

$$(u_{1,1} - u_{2,1})(u_{2,2} - u_{1,2}) > 0, \quad (12b)$$

then, the NE of the game $\mathcal{G}(\underline{u})$ in (2) is unique, with

$$P_{A_1}^*(a_1) = \frac{u_{2,2} - u_{2,1}}{u_{1,1} - u_{1,2} - u_{2,1} + u_{2,2}} \in (0, 1) \quad \text{and} \quad (13a)$$

$$P_{A_2}^*(a_1) = \frac{u_{2,2} - u_{1,2}}{u_{1,1} - u_{1,2} - u_{2,1} + u_{2,2}} \in (0, 1). \quad (13b)$$

Moreover, the expected payoff at the NE is

$$u(P_{A_1}^*, P_{A_2}^*) = \frac{u_{1,1}u_{2,2} - u_{1,2}u_{2,1}}{u_{1,1} - u_{1,2} - u_{2,1} + u_{2,2}}. \quad (14)$$

If the entries of the matrix $\underline{u}$ in (1) satisfy

$$(u_{1,1} - u_{1,2})(u_{2,2} - u_{2,1}) \le 0 \quad \text{or} \quad (15a)$$

$$(u_{1,1} - u_{2,1})(u_{2,2} - u_{1,2}) \le 0, \quad (15b)$$

then, there exists either a unique NE or infinitely many NEs; and all NE strategies lead to the same payoff,

$$u(P_{A_1}^*, P_{A_2}^*) = \min_{j \in \{1,2\}} \max_{i \in \{1,2\}} u_{i,j} = \max_{i \in \{1,2\}} \min_{j \in \{1,2\}} u_{i,j}. \quad (16)$$

A payoff matrix $\underline{u}$ that satisfies (12) represents a ZSG exhibiting a unique NE in strictly mixed strategies. Alternatively, a payoff matrix $\underline{u}$ that satisfies (15) represents a ZSG exhibiting strategic dominance, a unique pure NE, or infinitely many NEs [23].

Let the function $\hat{u}: \Delta(A_2) \to \mathbb{R}$ be such that for all $P \in \Delta(A_2)$,

$$\hat{u}(P) = \max_{Q \in \Delta(A_1)} u(Q, P), \quad (17)$$

where the function $u$ is defined in (11). The function $\hat{u}$ in (17) determines the payoff $\hat{u}(P)$ in the game $\mathcal{G}(\underline{u})$ in (2) when Player 1 always plays an optimal strategy to the strategy $P$ played by Player 2. Moreover, the minimum of the function $\hat{u}$ is the payoff at the NE.

# IV. MAIN RESULTS

## A. Characterization of the Equilibria

The following theorem ensures the existence of an equilibrium for the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6).

**Theorem 1 (Existence).** The game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6) always possesses an equilibrium.

*Proof:* The proof is presented in Appendix A of [24]. ■

For characterizing the payoff at the equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$, it is important to highlight that the set of optimal commitments for Player 2 are the strategies that minimize the function $\hat{v}$ in (8). Let $P^{(1)}$ and $P^{(2)}$ be two real numbers such that for all $i \in \{1, 2\}$,

$$\begin{pmatrix} 1 \\ 0 \end{pmatrix}^{\mathrm{T}} \underline{u}^{(i)} \begin{pmatrix} P^{(i)} \\ 1 - P^{(i)} \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}^{\mathrm{T}} \underline{u}^{(i)} \begin{pmatrix} P^{(i)} \\ 1 - P^{(i)} \end{pmatrix}, \quad (18)$$

where the $2 \times 2$ matrix $\underline{u}^{(i)}$ satisfies,

$$\underline{u}^{(i)} = \underline{u} \begin{pmatrix} P_{\tilde{A}_2|A_2=a_1}(a_i) & 0 \\ 0 & P_{\tilde{A}_2|A_2=a_2}(a_i) \end{pmatrix}, \quad (19)$$

with the matrix $\underline{u}$ defined in (1); and the probability measures $P_{\tilde{A}_2|A_2}$ defined in (3). Using this notation, the following theorem characterizes the payoff at equilibrium.

**Theorem 2 (Equilibrium Payoff).** Let the tuple $(P_{A_1|\tilde{A}_2}^{\dagger}, P_{A_2}^{\dagger}) \in \Delta(A_1)^2 \times \Delta(A_2)$ form an equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6). If the matrix $\underline{u}$ in (1) satisfies (12), then

$$v(P_{A_1|\tilde{A}_2}^{\dagger}, P_{A_2}^{\dagger}) = \min\{\hat{v}(P_1), \hat{v}(P_2)\}, \quad (20)$$

where, the functions $v$ and $\hat{v}$ are defined in (5) and (8), respectively, and for all $i \in \{1, 2\}$, the probability measure $P_i \in \Delta(A_2)$ is such that $P_i(a_1) = P^{(i)}$, with $P^{(i)}$ in (18). Alternatively, if the entries of the matrix $\underline{u}$ satisfy (15), then

$$v(P_{A_1|\tilde{A}_2}^{\dagger}, P_{A_2}^{\dagger}) = \min_{j \in \{1,2\}} \max_{i \in \{1,2\}} u_{i,j}. \quad (21)$$

*Proof:* The proof is presented in Appendix B of [24]. ■

Theorem 2 characterizes the optimal commitment of Player 2. More specifically, when the payoff matrix $\underline{u}$ in (1) is such that the game $\mathcal{G}(\underline{u})$ in (2) possesses a unique NE in mixed strategies (conditions in (12)), the optimal commitment is one of the strategies $P_1$ or $P_2$ in (20). For all $i \in \{1, 2\}$, the strategy $P_i$ makes Player 1 indifferent to play any of its actions in the game $\mathcal{G}(\underline{u}^{(i)})$, with the matrix $\underline{u}^{(i)}$ in (19). This follows from the construction in (18). Alternatively, when the payoff matrix $\underline{u}$ in (1) is such that the game $\mathcal{G}(\underline{u})$ in (2) does not possess a unique NE in mixed strategies (conditions in (15)), the optimal commitment for Player 2 is a pure strategy. This is equivalent to announcing to Player 1 that a given action would be played with probability one, which makes the noisy observation immaterial. Moreover, from Lemma 1, it follows that the payoffs at the NE and the SE in pure strategies of the game $\mathcal{G}(\underline{u})$ are identical to the payoff at the equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$. That is, neither the fact that Player 2 commits before its opponent nor the fact that Player 1 obtains an observation of the action played by its opponent represent any benefit for either player.
## B. The Set of Best Responses of Player 1

The following lemma shows that, given a commitment $P_{A_2}$, the set of best responses $BR_1(P_{A_2})$ in (7) is the Cartesian product of two sets that can be independently described.

**Lemma 2.** The correspondence $BR_1$ in (7) satisfies for all $P \in \Delta(\mathcal{A}_2)$,

$$BR_1(P) = BR_{1,1}(P) \times BR_{1,2}(P), \quad (22)$$

where for all $i \in \{1, 2\}$, the correspondence $BR_{1,i}$ : $\Delta(\mathcal{A}_2) \to \mathcal{F}(\Delta(\mathcal{A}_1))$ is such that

$$BR_{1,i}(P) = \arg \max_{Q \in \Delta(\mathcal{A}_1)} \begin{pmatrix} Q(a_1) \\ Q(a_2) \end{pmatrix}^{\top} \underline{u}^{(i)} \begin{pmatrix} P(a_1) \\ P(a_2) \end{pmatrix}, \quad (23)$$

where the matrix $\underline{u}^{(i)}$ is in (19).

*Proof:* The proof is presented in Appendix C of [24]. ■

The following lemma characterizes the sets $BR_{1,1}(P)$ and $BR_{1,2}(P)$ in (23).

**Lemma 3.** Given a probability measure $P \in \Delta(\mathcal{A}_2)$, for all $i \in \{1, 2\}$, the correspondence $BR_{1,i}$ in (23) satisfies

$$BR_{1,i}(P) = \begin{cases} \{Q \in \Delta(\mathcal{A}_1) : Q(a_1) = 1\}, & \text{if } s_i > 0, \\ \{Q \in \Delta(\mathcal{A}_1) : Q(a_1) = 0\}, & \text{if } s_i < 0, \\ \Delta(\mathcal{A}_1), & \text{if } s_i = 0, \end{cases} \quad (24)$$

where $s_i \in \mathbb{R}$ is given by

$$s_i \triangleq (u_{1,1} - u_{2,1})P(a_1)P_{\tilde{A}_2|A_2=a_1}(a_i) + (u_{1,2} - u_{2,2})P(a_2)P_{\tilde{A}_2|A_2=a_2}(a_i). \quad (25)$$

*Proof:* The proof is presented in Appendix D of [24]. ■

A first observation from Lemma 3 is that for all $i \in \{1, 2\}$ and for all $P \in \Delta(\mathcal{A}_2)$, the cardinality of set $BR_{1,i}(P)$ is either one or infinite. In the case in which $BR_{1,i}(P)$ is a singleton, the only element is a pure strategy. Alternatively, when the cardinality is infinity, the set $BR_{1,i}(P)$ is identical to the set of all possible probability measures on $\mathcal{A}_1$, i.e., $BR_{1,i}(P) = \Delta(\mathcal{A}_1)$. That is, Player 1 chooses its actions either indifferently (all strategies are best responses) or deterministically (pure strategy). This contrasts with the case of bi-matrix Stakelberg games in which the existence of multiple best responses constraints the existence of equilibria [25].

Note also that for all $(i, j) \in \{1, 2\}^2$, the expected payoff, when Player 1 plays $a_j$, Player 2 has committed to $P_{A_2}$, and the noisy observation is $a_i$, is $u_{j,1}P_{A_2}(a_1)P_{\tilde{A}_2|A_2=a_1}(a_i) + u_{j,2}P_{A_2}(a_2)P_{\tilde{A}_2|A_2=a_2}(a_i)$. Thus, the right-hand side of the equality in (25) is the difference between the expected payoff obtained when Player 1 plays $a_1$ and when it plays $a_2$, subject to the observation $a_i$ and the commitment $P_{A_2}$.

The following lemma presents a different view of the correspondences $BR_{1,1}$ and $BR_{1,2}$ in (23). It suggests that Player 1 performs an estimation of the likelihood with which Player 2 might have played each of its actions based on the knowledge of the commitment and the noisy observation.

**Lemma 4.** Given a probability measure $P \in \Delta(\mathcal{A}_2)$, for all $i \in \{1, 2\}$, the correspondence $BR_{1,i}$ in (23) satisfies

$$BR_{1,i}(P) = \arg \max_{Q \in \Delta(\mathcal{A}_1)} u(Q, P_{A_2|\tilde{A}_2=a_i}), \quad (26)$$

where the function $u$ is defined in (11); the probability measure $P_{A_2|\tilde{A}_2=a_i}$ satisfies for all $j \in \{1, 2\}$,

$$P_{A_2|\tilde{A}_2=a_i}(a_j) = \frac{P_{\tilde{A}_2|A_2=a_j}(a_i)P(a_j)}{\sum_{\ell \in \{1,2\}} P_{\tilde{A}_2|A_2=a_\ell}(a_\ell)P(a_\ell)}, \quad (27)$$

with the probability measures $P_{\tilde{A}_2|A_2=a_1}$ and $P_{\tilde{A}_2|A_2=a_2}$ defined in (3).

*Proof:* The proof is presented in Appendix E of [24]. ■

For all $(i, j) \in \{1, 2\}^2$, the likelihood with which Player 2 has chosen action $a_j$ given the commitment $P$ and the noisy observation $a_i$ is $P_{A_2|\tilde{A}_2=a_i}(a_j)$ in (27). Hence, from Lemma 3 and Lemma 4, the optimal strategy of Player 1 to the observation $a_i$ and the commitment $P$ in the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ is identical to its optimal strategy in the game $\mathcal{G}(\underline{u})$ in (2) when its opponent plays the strategy $P_{A_2|\tilde{A}_2=a_i}$ in (27).

## C. Relevance of Noisy Observations

The following lemma shows that the function $\hat{u}$ in (17) is upper bounded by the function $\hat{v}$ in (8). This implies that, granting observations to Player 1 of the actions played by Player 2 does not harm Player 1. On the contrary, in some cases it might significantly benefit it.

**Lemma 5.** Let the probability measures $P_{A_1}^* \in \Delta(\mathcal{A}_1)$ and $P_{A_2}^* \in \Delta(\mathcal{A}_2)$ form one of the NEs of the game $\mathcal{G}(\underline{u})$ in (2). For all $P \in \Delta(\mathcal{A}_2)$, it holds that

$$u(P_{A_1}^*, P_{A_2}^*) \le \hat{u}(P) \le \hat{v}(P) \le \sum_{j \in \{1,2\}} P(a_j) \left( \max_{i \in \{1,2\}} u_{i,j} \right), \quad (28)$$

where the functions $\hat{v}$, $u$, and $\hat{u}$ are defined in (8), (11), and (17), respectively.

*Proof:* The proof is presented in Appendix F of [24]. ■

The following lemma compares the payoffs at the equilibria of the games $\mathcal{G}(\underline{u})$ in (2) and $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6).

**Lemma 6.** Let the probability measures $P_{A_1}^* \in \Delta(\mathcal{A}_1)$ and $P_{A_2}^* \in \Delta(\mathcal{A}_2)$ form one of the NEs of the game $\mathcal{G}(\underline{u})$ in (2). Let also the tuple $(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger) \in \Delta(\mathcal{A}_1)^2 \times \Delta(\mathcal{A}_2)$ form an equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6). Then,

$$u(P_{A_1}^*, P_{A_2}^*) \le v(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger) \le \min_{j \in \{1,2\}} \max_{i \in \{1,2\}} u_{i,j}. \quad (29)$$

*Proof:* The proof is presented in Appendix G of [24]. ■

Lemma 6 reveals that the payoff at the equilibria of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6) is lower bounded by the NE of the game $\mathcal{G}(\underline{u})$ in (2), which coincides with the SE in mixed strategies; and is upper bounded by the SE in pure strategies of the game $\mathcal{G}(\underline{u})$. The lower bound corresponds to the case in which the
Player 1 does not observe the actions of its opponent, while the upper bound corresponds to the case in which Player 1 has perfect observations of the actions taken by Player 2.

The following lemma presents necessary and sufficient conditions under which the payoff at the equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ is not greater than the NE of the game $\mathcal{G}(\underline{u})$.

**Lemma 7.** Let the tuple $(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger) \in \Delta(A_1)^2 \times \Delta(A_2)$ form an equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6). Let also the tuple $(P_{A_1}^*, P_{A_2}^*) \in \Delta(A_1) \times \Delta(A_2)$ form one of the NEs of the game $\mathcal{G}(\underline{u})$ in (2). Then,

$$v(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger) = u(P_{A_1}^*, P_{A_2}^*), \quad (30)$$

if and only if, (a) the matrix $\underline{u}$ in (1) satisfies (15); or (b) the matrix $\underline{u}$ in (1) satisfies (12) and the DMC in (3) satisfies for all $P \in \Delta(A_2)$, that $I(P_{\tilde{A}_2|A_2}; P) = 0$.

*Proof:* The proof is presented in Appendix H of [24]. ■

Lemma 7 establishes that granting Player 1 with noisy observations of the action played by Player 2 does not make any difference in two particular scenarios. First, in ZSGs with strategic dominance, NEs in pure strategies and infinitely many NEs (condition (a)). Second, in ZSGs when the DMC in (3) is such that Player 1 does not obtain any information about the action played by Player 2 by observing the output of the DMC.

Lemma 5 and Lemma 7 imply that granting Player 1 with relevant noisy observations of the action played by Player 2 makes a difference exclusively for ZSGs with a unique NE in mixed strategies. In this case, given the commitment of the leader $P_{A_2}$, relevant noisy observations refer to observations obtained through a DMC exhibiting positive mutual information between the channel input and the channel output. That is, $I(P_{\tilde{A}_2|A_2}; P_{A_2}) > 0$.

The following lemma describes a special class of channels.

**Lemma 8.** Let $(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger) \in \Delta(A_1)^2 \times \Delta(A_2)$ form an equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6). If for all $P \in \Delta(A_2)$, $I(P_{\tilde{A}_2|A_2}; P) = H(P) = H(P_{\tilde{A}_2})$, with $P_{\tilde{A}_2}(a_i) = \sum_{\ell \in \{1,2\}} P_{\tilde{A}_2|A_2=a_\ell}(a_\ell) P(a_\ell)$ and $i \in \{1,2\}$, then

$$\hat{v}(P_{A_2}^\dagger) = \min_{j \in \{1,2\}} \max_{i \in \{1,2\}} u_{i,j}. \quad (31)$$

*Proof:* The proof is presented in Appendix I of [24]. ■

The condition that for all $P \in \Delta(A_2)$, $I(P_{\tilde{A}_2|A_2}; P) = H(P) = H(P_{\tilde{A}_2})$ implies that the DMC in (3) establishes a deterministic bijection between the channel input and the channel output. From this perspective, Lemma 8 strengthens the observation that under perfect observations of the action played by Player 2, the commitment becomes irrelevant and the payoff at the equilibrium of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ in (6) is identical to the SE in pure strategies of the game $\mathcal{G}(\underline{u})$ in (2), i.e., the min max solution in pure strategies.

<figure><img src="image_2.png" /><figcaption>(a) Payoff matrix $\underline{u} = (-8, 6; 2, -2)$ in (1).</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) Payoff matrix $\underline{u} = (-5, 1; -6, 3)$ in (1).</figcaption></figure>

<caption>Fig. 1: Plots of the function $\hat{v}$ in (8) and $\hat{u}$ in (17) as a function of the commitment $P_{A_2}$ of Player 2 with a symmetric DMC $P_{\tilde{A}_2|A_2=a_1}(a_1) = P_{\tilde{A}_2|A_2=a_2}(a_2) = 0.9$ in (3).</caption>

## V. EXAMPLES

In Figure 1(a), the matrix $\underline{u} = (-8, 6; 2, -2)$ is such that the game $\mathcal{G}(\underline{u})$ exhibits a unique NE in mixed strategies (Lemma 1). Hence, as announced by Lemma 5 and Lemma 7, there exists a strict inequality between the NE payoff $u(P_{A_1}^*, P_{A_2}^*)$ of the game $\mathcal{G}(\underline{u})$ (red triangle) and the equilibrium payoff $v(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger)$ of the game $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ (magenta square). Alternatively, in Figure 1(b), the matrix $\underline{u} = (-5, 1; -6, 3)$ is such that the game $\mathcal{G}(\underline{u})$ exhibits a unique NE in pure strategies (Lemma 1). Hence, as predicted by Lemma 7, the payoffs of the games $\mathcal{G}(\underline{u})$ and $\mathcal{G}(\underline{u}, P_{\tilde{A}_2|A_2})$ are identical (red triangle). That is, $u(P_{A_1}^*, P_{A_2}^*) = v(P_{A_1|\tilde{A}_2}^\dagger, P_{A_2}^\dagger)$.
REFERENCES

[1] J. F. Nash, "Equilibrium points in n-person games," *Proceedings of the National Academy of Sciences*, vol. 36, no. 1, pp. 48–49, 1950.

[2] H. Stackelberg, *Theory of the Market Economy*. Oxford University Press, Mar. 1952.

[3] V. Conitzer and T. Sandholm, "Computing the optimal strategy to commit to," in *Proc. ACM Conf. on Electronic Commerce*, Ann Arbor, Michigan, USA, Jun. 2006, pp. 82–90.

[4] V. Conitzer, "On Stackelberg mixed strategies," *Synthese*, vol. 193, no. 3, pp. 689–703, Mar. 2016.

[5] S. Leonardos and C. Melolidakis, "On the commitment value and commitment optimal strategies in bimatrix games," *International Game Theory Review*, vol. 20, no. 3, p. 1840001, Sep. 2018.

[6] B. von Stengel and S. Zamir, "Leadership games with convex strategy sets," *Games and Economic Behavior*, vol. 69, no. 2, pp. 446–457, Jul. 2010.

[7] J. v. Neumann, "Zur Theorie der Gesellschaftsspiele," *Mathematische annalen*, vol. 100, no. 1, pp. 295–320, 1928.

[8] M. Simaan and J. B. Cruz, "On the Stackelberg strategy in nonzero-sum games," *Journal of Optimization Theory and Applications*, vol. 11, no. 5, pp. 533–555, May 1973.

[9] ——, "Additional aspects of the Stackelberg strategy in nonzero-sum games," *Journal of Optimization Theory and Applications*, vol. 11, no. 6, pp. 613–626, 1973.

[10] C. Jin, P. Netrapalli, and M. Jordan, "What is local optimality in nonconvex-nonconcave minimax optimization?" in *Proc. Int. Conf. on Machine Learning*, Vritual, Jul. 2020, pp. 4880–4889.

[11] Y. Bai, C. Jin, H. Wang, and C. Xiong, "Sample-efficient learning of Stackelberg equilibria in general-sum games," in *Proc. Advances in Neural Information Processing Systems*, vol. 34, Virtual, Dec. 2021, pp. 25799–25811.

[12] H. W. Wallmeier, "Games with informants: An information-theoretical approach towards a game-theoretical problem," *International Journal of Game Theory*, vol. 17, no. 4, pp. 245–278, 1988.

[13] K. Bagwell, "Commitment and observability in games," *Games and Economic Behavior*, vol. 8, no. 2, pp. 271–280, 1995.

[14] W. Müller, "The quality of the signal matters: A note on imperfect observability and the timing of moves," *Journal of Economic Behavior & Organization*, vol. 45, no. 1, pp. 99–106, Mar. 2001.

[15] J. Ferreira, "A note on Bagwell's paradox and forward induction in three classic games," *International Game Theory Review*, vol. 13, no. 01, pp. 93–104, 2011.

[16] J. Teng, "A generalized Stackelberg model with noisy observability and incomplete information," *Available at SSRN 2265130*, 2013.

[17] E. van Damme and S. Hurkens, "Games with imperfectly observable commitment," *Games and Economic Behavior*, vol. 21, no. 1-2, pp. 282–308, 1997.

[18] W. Güth, W. Müller, and Y. Spiegel, "Noisy leadership: An experimental approach," *Games and Economic Behavior*, vol. 57, no. 1, pp. 37–62, Oct. 2006.

[19] J. Bizzotto, T. Hinnosaar, and A. Vigier, "The limits of commitment," *arXiv preprint arXiv:2205.05546*, 2022.

[20] B. Adolph, "Commitment, trembling hand imperfection and observability in games," *Available at SSRN 2159*, 1996.

[21] C. E. Shannon, "A mathematical theory of communication," *The Bell System Technical Journal*, vol. 27, pp. 379–423, Jul. 1948.

[22] ——, "A mathematical theory of communication," *The Bell System Technical Journal*, vol. 27, pp. 623–656, Oct. 1948.

[23] K. Sun, "Some Properties of the Nash Equilibrium in 2 x 2 Zero-Sum Games," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9492, Nov. 2022.

[24] K. Sun, S. M. Perlaza, and A. Jean-Marie, "2 × 2 zero-sum games with commitments and noisy observations," INRIA, Centre Inria d'Université Côte d'Azur, Sophia Antipolis, France, Tech. Rep. RR-9505, May 2023.

[25] R. Lucchetti, F. Mignanego, and G. Pieri, "Existence theorems of equilibrium points in Stackelberg," *Optimization*, vol. 18, no. 6, pp. 857–866, 1987.