7. Approximating SSE operators

The goal ahead is to approximate and provide computable representations of:

  • each candidate correspondence \mathcal{W}: D \rightrightarrows \mathbb{R}^{\mathcal{Z}}; and
  • the operator \mathcal{W} \mapsto \mathbf{B}(\mathcal{W}).

7.1. Conceptual

Recall \{Q_k\,|\,k=1,\ldots ,K\} denotes a partition of D, so D=\bigcup_{k=1}^K Q_k. An upper hemicontinuous, compact- and convex-valued correspondence \mathcal{W}:D \rightrightarrows \mathbb{R}^\mathcal{Z} can be approximated by step-valued correspondences using the following procedures: Letting

\begin{equation*} \omega^o_k (\lambda) := \begin{cases} \text{co}\bigcup_{\lambda \in Q_k}\mathcal{W}(\lambda') & \text{if} \ (\lambda) \in Q_k,\\ \emptyset & \text{otherwise}, \end{cases} \end{equation*}

the correspondence defined by \mathcal{W}^o(\lambda) := \bigcup_{k}\omega^o_k (\lambda) gives an outer step-valued approximation of \mathcal{W}.

Similarly, letting

\begin{equation*} \omega^i_k (\lambda) := \begin{cases} \bigcap_{\lambda \in Q_k}\mathcal{W}(\lambda) & \text{if} \ \lambda \in Q_k, \\ \mathbb{R}^\mathcal{Z} & \text{otherwise}, \end{cases} \end{equation*}

the correspondence defined by \mathcal{W}^i(\lambda) := \bigcap_{k}\omega^i_k (\lambda) yields an inner step-valued approximation of \mathcal{W}.

7.2. Practical

Since the convex-valued approximations \mathcal{W}^o and \mathcal{W}^i are constant on each partition element Q_k, and there are K < +\infty partition elements, these approximations can be further approximated by constructing outer and inner approximations for the sets \omega^o_k (\lambda) and \omega^i_k (\lambda) using convex polytopes. Let \mathbb{S}^{N_z-1} := \left\{x \in \mathbb{R}^{N_z} : \| x \| = 1 \right\} be the unit (N_z - 1)-sphere where the norm \| \cdot \| is given by \| x \|_{2} = \left(\sum_{j=1}^{N_z} x_{j}^2\right)^{1/2}. Suppose we have finite sets of directional vectors: H := \{ h_l \in \mathbb{S}^{N_z-1} : l = 1,...,L \} and \tilde{H} := \{ \tilde{h}_l \in \mathbb{S}^{N_z-1} : l = 1,...,L' \}. Let \bar{\omega}^o_k (\lambda) and \bar{\omega}^i_k (\lambda) denote the corresponding polytope approximations, respectively, of \omega^o_k (\lambda) and \omega^i_k (\lambda), where

\begin{equation*} \bar{\omega}^o_k (\lambda) := \begin{cases} \bigcap_{l=1}^{L}\{ z | h_l \cdot z \leq c_{l}^{o}(k) \} & \text{if} \ \lambda \in Q_k,\\ \emptyset & \text{otherwise} \end{cases}, \end{equation*}

and,

\begin{equation*} \bar{\omega}^i_k (\lambda) := \begin{cases} \bigcap_{l=1}^{L'}\{ z | \tilde{h}_l \cdot z \leq c_{l}^{i}(k) \} & \text{if} \ \lambda \in Q_k,\\ \emptyset & \text{otherwise} \end{cases}. \end{equation*}

Let \bar{\mathcal{W}}^o := \cup_{k \in \mathbf{K}}\bar{\omega}^o_k and \bar{\mathcal{W}}^i := \cup_{k \in \mathbf{K}}\bar{\omega}^i_k denote the resulting correspondences. One would like the “true” correspondence \mathcal{W} to be “sandwiched” by polytope “step-correspondences” \bar{\mathcal{W}}^o from the outside, and, by \bar{\mathcal{W}}^i from the inside. [2]

(1)\bar{\mathcal{W}}^i \subset \mathcal{W}^i \subset \mathcal{W} \subset \mathcal{W}^o \subset \bar{\mathcal{W}}^o.

The last statement (1) is only true if the step-correspondence levels c_{l}^{o}(k) and c_{l}^{i}(k) are defined, respectively, as the maximal and minimal levels over each domain partition element Q_k, in each direction h_l \in H or \tilde{h}_l \in \tilde{H}. [1]

In the next section, we show how to construct these upper- and lower bounding estimates c_{l}^{o}(k) and c_{l}^{i}(k) by using stochastic global optimization programs and also separable bilinear program formulations, when \mathcal{W} represents a candidate guess of the symmetric sequential equilibrium payoff correspondence in our class of games.

Footnotes

[1]In the context of our game, where \mathcal{W} stands for a candidate guess of the equilibrium value correspondence, the last statement (1) is only true if the step-correspondence levels c_{l}^{o}(k) and c_{l}^{i}(k) are defined, respectively, as the globally maximal and minimal values of each nonlinear programming problem (which is defined over each state-space partition element Q_k, in each direction h_l \in H or \tilde{h}_l \in \tilde{H}) that summarizes the concept of symmetric sequential equilibrium of the game.
[2]This idea of providing both upper- and lower-bounding estimates of a given correspondence was first proposed by [JYC2003] in the computation of repeated games. Our proposed method is a modification of [SY2000] who in turn extended [JYC2003] to the computation of value correspondences in dynamic games. Our contribution will be in the form of bilinear programming formulations as a practical and computable means of constructing these approximate correspondences.