Paper deep dive

The fixed-point bundle method over product-of-simplex domains arising from game equilibria

Hongbo Sun

Year: 2026Venue: arXiv preprintArea: math.OCType: PreprintEmbeddings: 123

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%

Last extracted: 9/16/2026, 7:29:19 AM

Summary

This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, enabling the solution of Nash equilibria. The authors establish an equivalence between VIs on product-of-simplex domains and simplex domains via a fiber bundle isomorphism. This geometric equivalence allows the predictor-corrector path-following algorithm, originally designed for simplex domains, to inherit global convergence guarantees with linear gap reduction when applied to product-of-simplex domains. Numerical experiments on 5600 instances confirm robust performance.

Entities (8)

Variational Inequality · mathematical-problem · 99%Fixed-point bundle method · algorithmframework · 98%Nash Equilibrium · game-theory-concept · 97%Product-of-Simplex Domain · mathematical-domain · 96%Simplex Domain · mathematical-domain · 96%Predictor-Corrector Path-Following Algorithm · algorithm · 95%Fiber Bundle Isomorphism · mathematical-concept · 94%Dirichlet Distribution · probability-distribution · 90%

Relation Signals (6)

Fixed-point bundle method → extendsto → Product-of-Simplex Domain

confidence 95% · This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain

Predictor-Corrector Path-Following Algorithm → inheritsconvergencefrom → Simplex Domain Framework

confidence 94% · the predictor-corrector path-following algorithm for the VI on the product-of-simplex domain is shown to inherit the convergence guarantee of the simplex-domain framework

Fixed-point bundle method → solves → Nash Equilibrium

confidence 93% · directly applicable to solving Nash equilibria

Fiber Bundle Isomorphism → establishesequivalencebetween → Simplex Domain

confidence 92% · establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism

Variational Inequality → reformulates → Nash Equilibrium

confidence 90% · a game equilibrium problem can be equivalently reformulated as a variational inequality (VI)

Dirichlet Distribution → usedforsmoothing → Variational Inequality

confidence 88% · smoothing the continuous mapping ... using Dirichlet distribution averaging

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex domain and establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism. Exploiting this geometric equivalence, the predictor-corrector path-following algorithm for the VI on the product-of-simplex domain is shown to inherit the convergence guarantee of the simplex-domain framework, namely, global convergence with linear gap reduction near solutions. Numerical experiments on 5600 randomly generated instances with dimensions ranging from 2-player 128-action to 128-player 2-action demonstrate robust performance. The algorithm converges in every tested instance.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

120,308 characters extracted from source content.

Expand or collapse full text

The fixed-point bundle method over product-of-simplex domains arising from game equilibria Hongbo Sun †thanks: Experiment codes and results are available at https://github.com/shb20tsinghua/FiberBundle_VI. Email: shb20@tsinghua.org.cn Abstract This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex domain and establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism. Exploiting this geometric equivalence, the predictor-corrector path-following algorithm for the VI on the product-of-simplex domain is shown to inherit the convergence guarantee of the simplex-domain framework, namely, global convergence with linear gap reduction near solutions. Numerical experiments on 5600 randomly generated instances with dimensions ranging from 2-player 128-action to 128-player 2-action demonstrate robust performance. The algorithm converges in every tested instance. Keywords: variational inequality, Nash equilibrium, interior point method, fiber bundle, path-following MSCcodes: 49J40, 90C33, 90C51, 91A06 Contents 1 Introduction 2 Approximate reduction to analytic VI on simplex product 3 The fixed-point bundle of VI on simplex product 3.1 Generalizing the three equivalent characterizations 3.2 The composite fixed-point bundle 4 Equivalence between VI on simplex product and VI on simplex 4.1 Transforming VI⁡(F,Δnm) VI(F, _n^m) into VI⁡(F¯,Δmn+) VI( F, _mn^+) 4.2 Isomorphism between fixed-point bundles 4.3 Equivalence between characterizations 4.4 Equivalence between differential properties 5 Path-following on the fixed-point bundles 5.1 Transforming the predictor-corrector framework 5.2 Transferring the convergence results 5.3 The complete path-following algorithm 6 Experiments 7 Conclusion References 1 Introduction Game equilibrium problems, introduced by Nash [1], are central in economics [2], engineering [3], artificial intelligence [4], etc. They describe noncooperative settings in which each agent selects a strategy to maximize its own utility given the strategies of others, and an equilibrium is a strategy profile from which no agent has a unilateral incentive to deviate. Under certain conditions, a game equilibrium problem can be equivalently reformulated as a variational inequality (VI) [5]. Let K⊆ℝnK ^n be a nonempty compact convex set (a convex body) and H:K→ℝnH:K ^n be a continuous function. The VI problem VI⁡(H,K) VI(H,K) asks for x⋆∈Kx ∈ K such that ⟨H⁡(x⋆),x′−x⋆⟩≥0forallx′∈K. H(x ),x -x ≥ 0 for~all~x ∈ K. When K has a product structure such that K=∏iKiK= _iK_i, and H is a block-wise gradient field such that H=[Hi]=[∇xifi]H=[H_i]=[ _x_if_i], the problem VI⁡(H,K) VI(H,K) is a game equilibrium problem with KiK_i as each player’s strategy set and fif_i as each player’s payoff function. In terms of iterative methods with asymptotic convergence, existing algorithms for game equilibrium problems are largely the same as those for VIs [6]. VI algorithms fall into several categories, each with its application to game equilibrium problems. Projection [7] and proximal point methods [8] reformulate the equilibrium conditions as a fixed-point equation and iterate projections onto the feasible set. Merit-function approaches [9] convert the game into an optimization problem via merit functions and apply gradient or Newton updates. Interior point methods [10] transform the game into a complementarity problem and follow a central path subject to the perturbed KKT system. Homotopy methods [11] deform a simple operator into the target game operator. Operator splitting methods [12] exploit decompositions such as sums of individual monotonic operators. Modern variants incorporate adaptive step sizes, inertial terms, or stochastic estimates for large-scale strategic interactions [13, 14]. This paper mainly deals with VIs with the product-of-simplex domain, which is the canonical domain for mixed strategies of finite normal-form games. We extend the fixed-point bundle framework in Paper 1 [15] for VIs on simplex domain to VIs on product-of-simplex domain. In Paper 1, the fixed-point bundle framework formulates the solution space of a VI on simplex domain as a fiber bundle, where starting point selection, path-following, and singularity avoidance are systematically integrated. The path-following algorithm applies to VIs with general continuous functions and general compact convex domains after approximate reduction, and it guarantees global convergence with linear gap reduction near solutions. This paper establishes an equivalence between the fixed-point bundle framework over product-of-simplex domain and that over simplex domain, showing that the path-following algorithm with product-of-simplex domain has the same convergence result as in Paper 1. The proposed approach begins by approximately reducing the general VI⁡(H,K) VI(H,K) to a smooth VI⁡(F,Δnm) VI(F, _n^m) with domain Δnm _n^m (product of m n-dimensional simplices) and a real-analytic operator F, in correspondence to the VI with real-analytic operator and simplex domain that Paper 1 deals with. The three equivalent characterizations in Paper 1 can be generalized to VI⁡(F,Δnm) VI(F, _n^m) via the decomposable structure of the gap function of VI⁡(F,Δnm) VI(F, _n^m). Then, we derive the fixed-point bundle of VI⁡(F,Δnm) VI(F, _n^m), which turns out to have a composite structure on top of the ordinary fiber bundle structure. An operator F¯ F can be constructed based on the homeomorphism ϕ:Δnm×Δm∘→Δmn+φ: _n^m× _m → _mn^+, such that VI⁡(F¯,Δmn+) VI( F, _mn^+) and VI⁡(F,Δnm) VI(F, _n^m) have the same solutions. The central innovation of this paper is to establish the equivalence between the fixed-point bundle frameworks of VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(F¯,Δmn+) VI( F, _mn^+) via a fiber bundle isomorphism. However, there is a gap: F¯ F is only defined on Δmn+ _mn^+, instead of being a smooth map on the closed simplex Δmn _mn. Thus, we can only have the fixed-point bundle framework of VI⁡(F¯,Δmn+) VI( F, _mn^+) as a formality by substituting F¯ F into Paper 1, while the assertions concerning this framework do not directly transfer. The predictor-corrector path-following algorithm for VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(F¯,Δmn+) VI( F, _mn^+) turns out to fix the variable on a specific slice given by winit∈Δm∘w_ init∈ _m . The map F¯ F restricted to this slice can be extended to a map F~ F real-analytic on the closed simplex Δmn _mn, such that all the results in Paper 1 apply to VI⁡(F~,Δmn) VI( F, _mn). Then, transferring from VI⁡(F~,Δmn) VI( F, _mn) to VI⁡(F¯,Δmn+) VI( F, _mn^+) and to VI⁡(F,Δnm) VI(F, _n^m), the path-following algorithm for VI⁡(F,Δnm) VI(F, _n^m) has the same convergence guarantee as in Paper 1. In experiments, numerical experiments on 5600 randomly generated instances with dimensions ranging from 2-player 128-action to 128-player 2-action show that the algorithm succeeds in every case. The remainder of the paper is organized as follows. Section 2 details the approximation reductions. Section 3 generalizes the three equivalent characterizations and the fixed-point bundle. Section 4 constructs a VI on simplex and establishes its equivalence to the VI on product-of-simplex. Section 5 transforms the predictor-corrector scheme and transfers convergence. Section 6 presents experimental results. Concluding remarks appear in Section 7. For vectors, we use a∘ba b for componentwise multiplication and a/ba/b for componentwise division. Inequality a≥ba≥ b is also interpreted componentwise. For matrix A, componentwise multiplication is interpreted as A∘b=Adiag(b)A b=A diag(b) and b∘A=diag⁡(b)Ab A= diag(b)A. For tensors, ℝmnR^mn is a vector space with dimension mnmn, ℝm×nR^m× n is a tensor space with shape m×nm× n, and the operation reshape⁡(⋅) reshape(·) always represents switching between these two shapes. For block stacking, [ai][a_i] represents concatenating small vectors aia_i into a large vector, and Diag⁡[xiI] Diag[x_iI] represents a block diagonal matrix. The operation norm⁡([xi])=[xi]/(∑jxj) norm([x_i])=[x_i]/( _jx_j) denotes normalization. The operation w⊙πw π is defined by w∈ℝmw ^m, π∈ℝm×nπ ^m× n, w⊙π∈ℝm×nw π ^m× n, and (w⊙π)i=wiπi(w π)_i=w_i _i. Finally, 1 is the all-one vector; it sometimes has dimension n, sometimes dimension mnmn, but its dimension can always be inferred from context. 2 Approximate reduction to analytic VI on simplex product Similar to Paper 1, we first introduce the approximate reduction from general VI⁡(H,K) VI(H,K) to VI⁡(F,Δnm) VI(F, _n^m). Approximating convex bodies via simplex product In Paper 1, the fixed-point bundle method applies to VIs on general convex bodies based on the fact that any convex body can be inner-approximated arbitrarily well by polytopes, which are linear transformations of simplices. In fact, polytopes and simplices are in one-to-one correspondence via linear transformations when they have the same number of vertices. The linear transformation x=[v1,…,vn]σx= [v_1,…,v_n ]σ transforms a simplex Δ to a polytope with vertices v1,…,vnv_1,…,v_n. In this paper, we need to approximate convex bodies with linear transformations of a simplex product, which yield the Minkowski sum of polytopes. The linear transformation x=Vreshape(π)=∑i=1mViπi=∑i=1m[vi1,…,vin]πix=V reshape(π)= _i=1^mV_i _i= _i=1^m [v_i1,…,v_in ] _i transforms a simplex product Δnm _n^m into a Minkowski sum of m polytopes, where each summand has vertices vi1,…,vinv_i1,…,v_in. The Minkowski sum of polytopes is still a polytope, and if each summand polytope has nin_i vertices, the resulting polytope can have at most ∏ini _in_i vertices. For instance, each simplex Δn _n has n vertices, and their Cartesian product Δnm _n^m, which is a Minkowski sum in higher-dimensional space, has nmn^m vertices. Thus, the Minkowski sum of polytopes can potentially lead to an enormous compression of the input vertex budget from ∏ini _in_i to ∑ini _in_i, resulting in a dimension reduction for the fixed-point bundle method. For inner approximation of general convex bodies, since the Minkowski sum of polytopes includes ordinary polytopes as single-summand cases, approximating convex bodies with a Minkowski sum of polytopes is trivially at least as good as approximating with an ordinary polytope. However, the caveat is that this is not true if a specific number of summands is required in the Minkowski sum. Even for a Minkowski sum of nin_i-vertex polytopes, ∏ini _in_i is only an upper bound on its vertex number; its vertex number can still be less than ∑ini _in_i. There are indeed cases where approximation by Minkowski sums has a strict advantage. For d-dimensional convex bodies with some regularity condition, the approximation error using a polytope with n vertices is O(n−2/(d−1))O(n^-2/(d-1)) [16]. Then, it can be shown that for a d-dimensional convex body K=K1×⋯×KmK=K_1×…× K_m that is the Cartesian product of did_i-dimensional convex bodies KiK_i, the Minkowski sum of individual polytopes approximating KiK_i has strictly smaller approximation error than directly approximating K with ordinary polytopes under the same input vertex budget. In this paper, we stop at the trivial guarantee that approximation with a linear image of a simplex product is at least as good as approximation with a linear image of a simplex. We do not study for which kinds of convex bodies the former has a strict advantage, and we do not develop a mechanism for discovering and exploiting nontrivial decomposition structures of a target convex body. Approximating continuous functions via analytic functions on simplex product The linear transformation x=Vreshape(π)x=V reshape(π) transforms the VI as follows. ⟨H⁡(x),x′−x⟩=∑i⟨Hi(∑iViπi),Viπi′−Viπi⟩=∑i⟨Vi⊤Hi(∑iViπi),πi′−πi⟩≥0. H(x),x -x = _i H_i( _iV_i _i),V_i _i -V_i _i = _i V_i H_i( _iV_i _i), _i - _i ≥ 0. Similar to Paper 1, we then smooth the continuous mapping F⁡(π)=reshape⁡(V⊤H(Vreshape(π)))F(π)= reshape(V H(V reshape(π))) using Dirichlet distribution averaging. The Dirichlet distribution Dir⁡(α) Dir(α) on the simplex Δ is given by Dir⁡(y,α)=1B⁡(α)∏i=1nyiαi−1,α>0, Dir(y;α)= 1B(α) _i=1^ny_i _i-1, α>0, (2.1) where y∈Δy∈ is the variable, α>0α>0 is a vector of concentration parameters, and B⁡(α)B(α) is the Beta function. We need a Dir⁡(αi) Dir( _i) for each πi∈Δn _i∈ _n, so the map F⁡(π)F(π) is actually smoothed with the product Dirichlet distribution ∏iDir⁡(αi) _i Dir( _i). For each component Fi,aF_i,a of F, we define the following operation. (TjFi,a)(π1,…,πm)= (T_jF_i,a)( _1,…, _m)= Yj∼Dir⁡(αj)[Fi,a(π1,…,Yj,…,πm)] _Y_j Dir( _j) [F_i,a( _1,…,Y_j,…, _m) ] (2.2) = = ∫ΔnFi,a(π1,…,yj,…,πm)Dir(yj,αj)dyj _ _nF_i,a( _1,…,y_j,…, _m) Dir(y_j; _j)\,dy_j Then, the product Dirichlet distribution smoothing of a continuous map F:Δ→ℝnF: ^n is the map Fϵ:Δ→ℝnF_ε: ^n given componentwise by Fϵ,i,a(π)=Y∼∏j=1mDir⁡(πj/ϵ+cj)[Fi,a(Y)]=(T1∘⋯∘TmFi,a)(π),F_ε,i,a(π)=E_Y _j=1^m Dir( _j/ε+c_j) [F_i,a(Y) ]=(T_1 … T_mF_i,a)(π), (2.3) where ϵ>0ε>0 is a scalar that measures approximation error, and ci>0c_i>0 is a constant vector ensuring πi/ϵ+ci>0 _i/ε+c_i>0 for all πi∈Δn _i∈ _n. Following Paper 1, we then prove that Fϵ(π)F_ε(π) is real-analytic on Δnm _n^m. Instead of proving it from scratch, we reuse the analyticity result for single-variable Dirichlet distribution averaging in Paper 1. Then, Hartogs’ theorem on separate holomorphy [17] from complex analysis can be used to extend this to analyticity for multiple-variable Dirichlet distribution averaging. This theorem states that for a function g:U×V→ℂg:U× V on U⊂ℂmU ^m and V⊂ℂnV ^n, if for every fixed u∈Uu∈ U, the map v↦g⁡(u,v)v g(u,v) is holomorphic on U, and for every fixed v∈Vv∈ V, the map u↦g⁡(u,v)u g(u,v) is holomorphic on V, then g is holomorphic on U×VU× V. Proposition 1. For every ϵ>0ε>0, Fϵ(π)F_ε(π) is real-analytic on Δnm _n^m. Proof. In the proof of Proposition 1, it is shown that if f⁡(σ)f(σ) is continuous on the simplex Δ , then for every σ∈Δσ∈ , (Tf)(z)(Tf)(z) is holomorphic on the complex neighborhood Uσ=z∈ℂn|∥z−σ∥≤dU_σ=\z ^n| z-σ ≤ d\. In our case, for every π∈Δnmπ∈ _n^m, we study (T1∘⋯∘TmFi,a)(z1,…,zm)(T_1 … T_mF_i,a)(z_1,…,z_m) on the product complex neighborhood Uπ=∏jUπjU_π= _jU_ _j with Uπj=zj∈ℂn|∥zj−πj∥≤djU_ _j=\z_j ^n| z_j- _j ≤ d_j\. We denote (yk′,yk^):=(y1,…,yk−1,yk′,yk+1,…,ym)(y_k ,y_ k):=(y_1,…,y_k-1,y_k ,y_k+1,…,y_m) and Tk^:=T1∘⋯∘Tk−1∘Tk+1∘⋯∘TmT_ k:=T_1 … T_k-1 T_k+1 … T_m. First, the operators TjT_j are commutative. The operation (T1∘⋯∘TmFi,a)(z1,…,zm)(T_1 … T_mF_i,a)(z_1,…,z_m) is an integral of the continuous Fi,a(y1,…,ym)F_i,a(y_1,…,y_m) over the compact region Δnm _n^m against the product measure ∏j=1mDir⁡(yj,zj/ϵ+cj)dyj _j=1^m Dir(y_j;z_j/ε+c_j)dy_j. By the Fubini-Tonelli theorem [18], if a multiple integral integrates a continuous integrand over a compact region, the order of integration can be interchanged. Thus, for every index k, we can denote Fϵ,i,a=Tk∘Tk^Fi,aF_ε,i,a=T_k T_ kF_i,a. Next, we prove separate holomorphy for every index k. Since Fi,a(y)F_i,a(y) is continuous on the compact set Δnm _n^m, it is uniformly continuous, i.e., for any ϵ>0ε>0 there exists δ>0δ>0 such that whenever ∥yk−yk′∥<δ y_k-y_k <δ, we have |Fi,a(yk′,yk^)−Fi,a(yk,yk^)|<ϵ F_i,a(y_k ,y_ k)-F_i,a(y_k,y_ k) <ε. Then, given fixed zj∈Uπjz_j∈ U_ _j for j≠kj≠ k, we have |(Tk^Fi,a)(yk,zk^)−(Tk^Fi,a)(yk′,zk^)|≤ (T_ kF_i,a)(y_k,z_ k)-(T_ kF_i,a)(y_k ,z_ k) ≤ ∫Δnm−1|Fi,a(yk′,yk^)−Fi,a(yk,yk^)|∏j≠kDir⁡(yj,zj/ϵ+cj)dyj _ _n^m-1 F_i,a(y_k ,y_ k)-F_i,a(y_k,y_ k) _j≠ k Dir(y_j;z_j/ε+c_j)\,dy_j < < ϵ∫Δnm−1∏j≠kDir⁡(yj,zj/ϵ+cj)dyj=ϵ ε _ _n^m-1 _j≠ k Dir(y_j;z_j/ε+c_j)\,dy_j=ε Thus, (Tk^Fi,a)(yk,zk^)(T_ kF_i,a)(y_k,z_ k) is (uniformly) continuous in yky_k on Δ . Then, the analyticity result for single-variable Dirichlet distribution averaging in the proof of Proposition 1 in Paper 1 applies to Fϵ,i,a=Tk(Tk^Fi,a)F_ε,i,a=T_k(T_ kF_i,a). We obtain that for every fixed zj∈Uπjz_j∈ U_ _j for j≠kj≠ k, the map zk↦Fϵ,i,a(zk,zk^)z_k F_ε,i,a(z_k,z_ k) is holomorphic in zkz_k on UπkU_ _k. Then, Hartogs’ theorem on separate holomorphy applies, and we obtain that Fϵ,i,a(z)F_ε,i,a(z) is holomorphic in z on UπU_π. Since π∈Δnmπ∈ _n^m is arbitrary, it follows that Fϵ,i,a(π)F_ε,i,a(π) is real-analytic in π on Δnm _n^m. The vector function Fϵ(π)F_ε(π) is real-analytic in π on Δnm _n^m because each of its components indexed by (i,a)(i,a) is real-analytic. ∎ 3 The fixed-point bundle of VI on simplex product 3.1 Generalizing the three equivalent characterizations As in Paper 1, we deal with VI⁡(F,Δnm) VI(F, _n^m) assuming F is real-analytic on Δnm _n^m throughout the following developments. In Paper 1, the analysis is built on the three equivalent characterizations of VI⁡(F¯,Δ) VI( F, ). Thus, we begin by transforming these three equivalent characterizations to characterize VI⁡(F,Δnm) VI(F, _n^m). First, we show that VI⁡(F,Δnm) VI(F, _n^m) can be decomposed into several VIs on Δn _n via its gap function. Theorem 2. For every π∈Δnmπ∈ _n^m, we have gap⁡(π)=∑igapi(πi,πi^),wheregapi(πi,πi^):=supπi′∈Δn⟨Fi(πi,πi^),πi−πi′⟩ gap(π)= _i gap_i( _i, _ i), where~ gap_i( _i, _ i):= _ _i ∈ _n F_i( _i, _ i), _i- _i (3.1) Consequently, for every π∈Δnmπ∈ _n^m, gap⁡(π)=0 gap(π)=0 if and only if gapi(πi,πi^)=0 gap_i( _i, _ i)=0 for every index i. Proof. First, we derive gap⁡(π) gap(π) as follows. gap⁡(π)= gap(π)= supπ′∈Δnm⟨F⁡(π),π−π′⟩=∑i(πi⊤Fi(π)−mina⁡Fi,a(π)) _π ∈ _n^m F(π),π-π = _i ( _i F_i(π)- _aF_i,a(π) ) = = ∑isupπi′∈Δn⟨Fi(π),πi−πi′⟩=∑igapi(πi,πi^) _i _ _i ∈ _n F_i(π), _i- _i = _i gap_i( _i, _ i) Thus, we obtain gap⁡(π)=∑igapi(πi,πi^) gap(π)= _i gap_i( _i, _ i). For every π∈Δnmπ∈ _n^m, we have gap⁡(π)≥0 gap(π)≥ 0 and gapi(πi,πi^)≥0 gap_i( _i, _ i)≥ 0 by definition. Then, by gap⁡(π)=∑igapi(πi,πi^) gap(π)= _i gap_i( _i, _ i), we have gap⁡(π)=0 gap(π)=0 if and only if gapi(πi,πi^)=0 gap_i( _i, _ i)=0 for every index i. ∎ In Theorem 2, gapi(πi,πi^) gap_i( _i, _ i) can be viewed as the gap function of a parametric variational inequality VI⁡(Fi(⋅,πi^),Δn) VI(F_i(·, _ i), _n) with πi _ i as the parameter. The theorem implies that π is a solution of VI⁡(F,Δnm) VI(F, _n^m) if and only if πi _i is a solution of VI⁡(Fi(⋅,πi^),Δn) VI(F_i(·, _ i), _n) for each index i. Since VI⁡(Fi(⋅,πi^),Δn) VI(F_i(·, _ i), _n) is a VI on simplex, the three equivalent characterizations in Paper 1 apply to it. However, they are compatible over index i only pointwise for individual π∈Δnmπ∈ _n^m, at which point all the parameters πi _ i and variables πi _i across index i come from the same π. In Paper 1, the three equivalent characterizations are indeed pointwise. Their definitions consist only of functions, equalities, and inequalities that are essentially pointwise objects assigning values to each individual (πi,τi)( _i, _i). The equivalence is also in pointwise form, stating that for each individual (πi,τi)( _i, _i), the properties of satisfying the three characterizations are equivalent. Thus, stacking the three equivalent characterizations of VI⁡(Fi(⋅,πi^),Δn) VI(F_i(·, _ i), _n) over index i at each individual π∈Δnmπ∈ _n^m, we obtain the generalization characterizing VI⁡(F,Δnm) VI(F, _n^m). We briefly go through them since the generalization merely adds a subscript i to those in Paper 1. Linear programming form. Equation (3.2) is the fixed-point KKT system (FPKKT). It consists of the perturbed KKT conditions (3.2a) of a parametric linear programming problem and the fixed-point condition π^=π π=π, where τ is the barrier parameter. [π^i∘ri−τiri−Fi(π)−vi⊤π^i−]=0 bmatrix π_i r_i- _i\\ r_i-F_i(π)-v_i1\\ 1 π_i-1\\ bmatrix=0 (3.2a) π^=π π=π (3.2b) Brouwer fixed-point form. Equation (3.3) is the Brouwer function. It is given by the correspondence from (π,τ)(π,τ) to (π^,r,v)( π,r,v) subject to perturbed KKT conditions (3.2a). It can be shown that this correspondence is a continuous function such that the Brouwer fixed-point theorem applies to it. (π^,r,v)=M⁡(π,τ),s.t.perturbedKKTconditions(3.2a).( π,r,v)=M(π,τ), s.t.~perturbed~KKT~conditions~ equ_kkt. (3.3) The Brouwer function is computed by solving the bisection problem (3.4) for every i. qi(vi)=⊤τiFi(π)+vi−1,vi∈[−mina⁡Fi,a(π),−mina⁡Fi,a(π)+⊤τi]q_i(v_i)=1 _iF_i(π)+v_i1-1, v_i∈[- _aF_i,a(π),- _aF_i,a(π)+1 _i] (3.4) Mixed complementarity problem form. Equation (3.5) is the (barriered) mixed complementarity problem (MCP), which comes from FPKKT (3.2) by making the complementarity term πi∘ri _i r_i the objective function. The τ=0τ=0 case is the original problem, and the τ>0τ>0 case is its barrier problem. min(π,r,v) _(π,r,v) ∑iπi⊤ri−τi⊤ln⁡πi−τi⊤ln⁡ri _i _i r_i- _i _i- _i r_i (3.5) s.t. s.t. ri=Fi(π)+vi r_i=F_i(π)+v_i1 ⊤πi=1 1 _i=1 (πi,ri)≥0 ( _i,r_i)≥ 0 Equivalence. The three characterizations are equivalent in the sense that for each variable-barrier pair (π,τ)(π,τ), the properties of satisfying the three characterizations are equivalent. Theorem 3. For (π,τ)∈Δnm×τ∈ℝm×n|τ>0(π,τ)∈ _n^m×\τ ^m× n|τ>0\, the following statements are equivalent. (i) (π,τ)(π,τ) satisfies FPKKT (3.2) for some r,vr,v. (i) π is a fixed point such that π^=π π=π of the Brouwer function (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ). (i) (π,τ)(π,τ) satisfies πˇ=π π=π and the perturbed KKT conditions of MCP (3.5), where πˇ π is the Lagrangian multiplier associated with the constraint r≥0r≥ 0. Analogous to Paper 1, FPKKT (3.2) characterizes paths leading to solutions of VI⁡(F,Δnm) VI(F, _n^m), the Brouwer function (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ) guarantees the existence of paths subject to FPKKT (3.2) via the Brouwer fixed-point theorem, and MCP (3.5) characterizes the paths as its special central paths. It can be shown that these statements indeed hold for VI⁡(F,Δnm) VI(F, _n^m), but we only use the formality and the equivalence of the three characterizations. In this paper, we intend to reuse the theoretical guarantees in Paper 1 by establishing an equivalence between VI⁡(F,Δnm) VI(F, _n^m) and some VI⁡(F¯,Δ) VI( F, ) to which Paper 1 applies, instead of directly transferring the theoretical guarantees onto VI⁡(F,Δnm) VI(F, _n^m). 3.2 The composite fixed-point bundle As in Paper 1, the solution space of FPKKT (3.2) can be constructed as a fiber bundle called the fixed-point bundle, which is the central geometric object of the path-following framework. For every π∈Δnmπ∈ _n^m, the admissible τ value satisfying FPKKT (3.2) can be expressed as τi=πi∘(Fi(π)+vi)=πi∘Fi(π)−(πi⊤Fi(π))πi+(vi+πi⊤Fi(π))πi. _i= _i (F_i(π)+v_i1)= _i F_i(π)-( _i F_i(π)) _i+(v_i+ _i F_i(π)) _i. Then, letting τ~i(π):=πi∘Fi(π)−(πi⊤Fi(π))πi τ_i(π):= _i F_i(π)-( _i F_i(π)) _i and v¯wi:=vi+πi⊤Fi(π) vw_i:=v_i+ _i F_i(π), part of the solution space of FPKKT (3.2) has the structure shown in equation (3.6). E=⋃π∈Δnmπ×B⁡(π) E= _π∈ _n^m\π\× B(π) (3.6) B⁡(π)=⋃w∈Δm∘B~(π,w) B(π)= _w∈ _m B(π,w) B~(π,w)=τ~(π)+v¯w⊙π|v¯∈ℝ∖0 B(π,w)= \ τ(π)+ vw π| v \0\ \ Note that E is not the entire solution space of FPKKT (3.2); it only contains τ such that ⊤τi=v¯wi1 _i= vw_i with v¯≠0 v≠ 0 and w ranging over Δm∘ _m , which indicates that the ⊤τi1 _i have the same sign for all i. We denote this set as ℝ±m×n:=τ∈ℝm×n|(⊤τi)(⊤τj)>0,∀i,j,R^m× n_±:=\τ ^m× n|(1 _i)(1 _j)>0,~∀ i,j\, then for every (π,τ)∈E(π,τ)∈ E, we have τ∈ℝ±m×nτ ^m× n_±. As equation (3.6) shows, E is a fiber bundle with projection α:E→Δnmα:E→ _n^m onto its base space Δnm _n^m such that α⁡((,,,))=πα((π,τ))=π, where the fiber over π∈Δnmπ∈ _n^m is α−1(π)=π×B⁡(π)α^-1(π)=\π\× B(π). This resembles the fiber bundle structure in Paper 1. In our case, equation (3.6) additionally shows a composite fiber bundle structure, such that each fiber B⁡(π)B(π) is itself a fiber bundle. Lemma 4. For any π∈Δnmπ∈ _n^m and w1,w2∈Δm∘w_1,w_2∈ _m , if w1≠w2w_1≠ w_2 then B~(π,w1)∩B~(π,w2)=∅ B(π,w_1)∩ B(π,w_2)= . Proof. Suppose for (π,w1)(π,w_1) and (π,w2)(π,w_2), there exist v¯1≠0 v_1≠ 0 and v¯2≠0 v_2≠ 0 such that πi∘Fi(π)+v¯1w1,iπi=πi∘Fi(π)+v¯2w2,iπi _i F_i(π)+ v_1w_1,i _i= _i F_i(π)+ v_2w_2,i _i for every i. Then v¯1w1,iπi=v¯2w2,iπi v_1w_1,i _i= v_2w_2,i _i. Multiplying by ⊤1 and summing over i, we have v¯1w1,i=v¯2w2,i v_1w_1,i= v_2w_2,i and v¯1=v¯2 v_1= v_2. Since v¯1≠0 v_1≠ 0 and v¯2≠0 v_2≠ 0, we have w1=w2w_1=w_2. By contraposition, if w1≠w2w_1≠ w_2, we have B~(π,w1)∩B~(π,w2)=∅ B(π,w_1)∩ B(π,w_2)= . ∎ Lemma 4 shows that for every π, B⁡(π)B(π) is indeed a fiber bundle. Given that v¯=0 v=0 is excluded from B~(π,w) B(π,w), B⁡(π)B(π) is the disjoint union of B~(π,w) B(π,w) over w∈Δm∘w∈ _m , where B~(π,w) B(π,w) are the fibers of B⁡(π)B(π). If v¯=0 v=0 were not excluded, all the B~(π,w) B(π,w) over w∈Δm∘w∈ _m would share a common point τ~(π) τ(π). Then, B~(π,w) B(π,w) would no longer be fibers of B⁡(π)B(π), but B⁡(π)B(π) could still be fibers of E. Therefore, E in equation (3.6) is a composite fiber bundle as equation (3.7) shows. We refer to this as the composite fixed-point bundle. E→α1Δnm×Δm∘→α2Δnm E _1 _n^m× _m _2 _n^m (3.7) α1((π,τ))=(π,norm⁡([⊤τi])) _1 ((π,τ) )=(π, norm([1 _i])) α2((,,,))=π _2 ((π,w) )=π There are three fiber bundles in the composite fixed-point bundle E→Δnm×Δm∘→ΔnmE→ _n^m× _m → _n^m. • Bundle E→Δnm×Δm∘E→ _n^m× _m : Each fiber π×B~(π,w)\π\× B(π,w) is a one-dimensional affine line spanned by v¯∈ℝ v excluding a single point (π,τ~(π))(π, τ(π)). The projection map α1 _1 projects each (π,τ)∈E(π,τ)∈ E to (π,norm⁡([⊤τi]))∈Δnm×Δm∘(π, norm([1 _i]))∈ _n^m× _m . • Bundle Δnm×Δm∘→Δnm _n^m× _m → _n^m: Each fiber Δm∘ _m is the interior of a simplex. The projection map α2 _2 projects each (π,w)∈Δnm×Δm∘(π,w)∈ _n^m× _m to π∈Δnmπ∈ _n^m. • Bundle E→ΔnmE→ _n^m: Each fiber π×B⁡(π)\π\× B(π) is an m-dimensional affine cone spanned by v¯w vw with w∈Δm∘w∈ _m and v¯∈ℝ v excluding a single point (π,τ~(π))(π, τ(π)). The projection map α2∘α1 _2 _1 projects each (π,τ)∈E(π,τ)∈ E to π∈Δnmπ∈ _n^m. In short, E→Δnm×Δm∘E→ _n^m× _m has a large base space and small fibers, whereas E→ΔnmE→ _n^m has a small base space and large fibers. Each fiber π×B⁡(π)\π\× B(π) of E→ΔnmE→ _n^m is the union of all the fibers π×B~(π,w)\π\× B(π,w) of E→Δnm×Δm∘E→ _n^m× _m over w∈Δm∘w∈ _m . As in Paper 1, we then derive the fixed-point bundle equation and define two sections of the fiber bundle. The fixed-point bundle equation G⁡(π,τ)=0G(π,τ)=0 is obtained by eliminating r and v in FPKKT (3.2) with the projection matrix I−πi⊤I- _i1 , where G⁡(π,τ)G(π,τ) is as equation (3.8) shows. Gi(π,τ)=(I−πi⊤)(πi∘Fi(π)−τi),(π,τ)∈Δnm×ℝ±m×nG_i(π,τ)= (I- _i1 ) ( _i F_i(π)- _i ), (π,τ)∈ _n^m×R^m× n_± (3.8) The two sections τˇ(π) τ(π) and τ~(π) τ(π) are sections of the bundle E∪(π,τ~(π))|π∈Δnm→ΔnmE∪\(π, τ(π))|π∈ _n^m\→ _n^m. The bundle E∪(π,τ~(π))|π∈Δnm→ΔnmE∪\(π, τ(π))|π∈ _n^m\→ _n^m adds back the point excluded by v¯≠0 v≠ 0 in each fiber of E→ΔnmE→ _n^m. Section τˇ(π) τ(π) satisfies τˇ(π)≥0 τ(π)≥ 0, and it characterizes the gap of VI⁡(F,Δnm) VI(F, _n^m) such that gapi(πi,πi^)=⊤τˇi(π) gap_i( _i, _ i)=1 τ_i(π). Section τ~(π) τ(π) satisfies ⊤τ~i(π)=01 τ_i(π)=0, and it governs the differential properties of the composite fixed-point bundle as will be discussed later. τˇi(π) τ_i(π) =πi∘(Fi(π)−(mina⁡Fi,a(π))a) = _i (F_i(π)- ( _aF_i,a(π) )1_a ) (3.9) τ~i(π) τ_i(π) =πi∘(Fi(π)−(πi⊤Fi(π)))=(I−πi⊤)(πi∘Fi(π)) = _i (F_i(π)- ( _i F_i(π) )1 )= (I- _i1 ) ( _i F_i(π) ) 4 Equivalence between VI on simplex product and VI on simplex The equivalence between VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(Fi(⋅,πi^),Δn) VI(F_i(·, _ i), _n) in the last section relies on a fixed parameter πi _ i, so the equivalence only holds pointwise for each individual π, and does not apply when π varies or in global situations. In this section, we construct a VI⁡(F¯,Δmn+) VI( F, _mn^+) preserving the solutions of VI⁡(F,Δnm) VI(F, _n^m), and establish the equivalence between their fixed-point bundle frameworks. 4.1 Transforming VI⁡(F,Δnm) VI(F, _n^m) into VI⁡(F¯,Δmn+) VI( F, _mn^+) We begin by constructing a VI on simplex preserving the solutions of VI⁡(F,Δnm) VI(F, _n^m). First, we lift VI⁡(F,Δnm) VI(F, _n^m) to a VI defined on Δnm×Δm∘ _n^m× _m with operator Fˇ(π,w)=(F(π),0) F(π,w)=(F(π),0). Then, the gap function of VI⁡(Fˇ,Δnm×Δm∘) VI( F, _n^m× _m ) is derived as follows. gapFˇ(π,w)= gap_ F(π,w)= sup(π′,w′)∈Δnm×Δm∘⟨(F⁡(π),0),(π′,w′)−(π,w)⟩ _(π ,w )∈ _n^m× _m (F(π),0),(π ,w )-(π,w) = = supπ′∈Δnm⟨F⁡(π),π′−π⟩=gap⁡(π) _π ∈ _n^m F(π),π -π = gap(π) Thus, for any w⋆∈Δm∘w ∈ _m , (π⋆,w⋆)(π ,w ) is a solution of VI⁡(Fˇ,Δnm×Δm∘) VI( F, _n^m× _m ) if and only if π⋆π is a solution of VI⁡(F,Δnm) VI(F, _n^m). Viewing πi _i as conditional distributions and w as a marginal distribution, we can transform (π,w)(π,w) into a joint distribution σ that takes values on a simplex. In fact, this is a real-analytic homeomorphism ϕ:Δnm×Δm∘→Δmn+φ: _n^m× _m → _mn^+ defined as follows. ϕ⁡(π,w)=σ, φ(π,w)=σ, s.t.σi,a=wiπi,a s.t.~ _i,a=w_i _i,a (4.1) ϕ−1(σ)=(π,w), φ^-1(σ)=(π,w), s.t.(πi,a,wi)=(σi,a/∑aσi,a,∑aσi,a) s.t.~( _i,a,w_i)= ( _i,a/ _a _i,a, _a _i,a ) We denote Δmn+=σ∈Δmn|∑aσi,a>0. _mn^+=\σ∈ _mn| _a _i,a>0\. The map ϕφ is a bijection between Δnm×Δm∘ _n^m× _m and Δmn+ _mn^+ because ϕ−1φ^-1 as defined is its inverse. Both ϕφ and ϕ−1φ^-1 are real-analytic because they consist only of elementary operations and the denominator ∑aσi,a>0 _a _i,a>0 on Δmn+ _mn^+. Thus, ϕ:Δnm×Δm∘→Δmn+φ: _n^m× _m → _mn^+ is a real-analytic homeomorphism. Next, we can use the homeomorphism ϕ:Δnm×Δm∘→Δmn+φ: _n^m× _m → _mn^+ to transform VI⁡(Fˇ,Δnm×Δm∘) VI( F, _n^m× _m ) into a VI on Δmn+ _mn^+. This is performed using the standard procedure of changing the variable of a VI [19]. For a general variational inequality VI⁡(H,K) VI(H,K), a standard theorem states that x⋆∈Kx ∈ K solves VI⁡(H,K) VI(H,K) if and only if −H⁡(x⋆)∈NK(x⋆)-H(x )∈ N_K(x ), where NK(x)=v∈ℝn|⟨v,x′−x⟩≤0,∀x′∈KN_K(x)=\v ^n| v,x -x ≤ 0,∀ x ∈ K\ is the normal cone. Another standard theorem on change of variables for normal cones states that if z=ψ⁡(x)z=ψ(x) is a diffeomorphism between K and ψ⁡(K)ψ(K), then NK(x)=(∂ψ⁡(x)/∂x)⊤Nψ⁡(K)(ψ⁡(x))N_K(x)=(∂ψ(x)/∂ x) N_ψ(K)(ψ(x)). Thus, if we define H¯(z)=(∂ψ⁡(x)/∂x)−⁣⊤H(x)s.t.x=ψ⁡(z) H(z)=(∂ψ(x)/∂ x)^- H(x)~ s.t.~x=ψ(z), then x⋆∈Kx ∈ K is a solution of VI⁡(H,K) VI(H,K) if and only if z⋆=ψ⁡(x⋆)z =ψ(x ) is a solution of VI⁡(H¯,ψ⁡(K)) VI( H,ψ(K)), which is a transformation obtained by change of variables. Note that H¯(z)=(∂ψ⁡(x)/∂x)−⁣⊤H(x) H(z)=(∂ψ(x)/∂ x)^- H(x) is equivalent to ⟨H¯(z),dz⟩=⟨H⁡(x),dx⟩ H(z),dz = H(x),dx given z=ψ⁡(x)z=ψ(x) and dz=(∂ψ⁡(x)/∂x)dxdz=(∂ψ(x)/∂ x)dx. Then, we can use this equation to find F¯(σ) F(σ), changing the variable of VI⁡(Fˇ,Δnm×Δm∘) VI( F, _n^m× _m ) based on σ=ϕ⁡(π,w)σ=φ(π,w), which is derived as follows. ⟨F¯(σ),dσ⟩ F(σ),dσ =⟨Fˇ(π,w),d⁡(π,w)⟩ = F(π,w),d(π,w) ∑i⟨F¯i(σ),widπi+πidwi⟩ _i F_i(σ),w_id _i+ _idw_i =∑i⟨Fi(π),dπi⟩ = _i F_i(π),d _i ∑i⟨wiF¯i(σ),dπi⟩+∑i(πi⊤F¯i(σ))dwi _i w_i F_i(σ),d _i + _i( _i F_i(σ))dw_i =∑i⟨Fi(π),dπi⟩ = _i F_i(π),d _i The coefficients of dπid _i and dwidw_i must be identically 00 for the equality to hold. Then, for every index i, wiF¯i(σ)−Fi(π)=kw_i F_i(σ)-F_i(π)=k1 and πi⊤F¯i(σ)=0 _i F_i(σ)=0. Therefore, we arrive at the function F¯(σ) F(σ) in equation (4.2), and VI⁡(F¯,Δmn+) VI( F, _mn^+) is the transformation of VI⁡(Fˇ,Δnm×Δm∘) VI( F, _n^m× _m ) by changing the variable via σ=ϕ⁡(π,w)σ=φ(π,w). F¯i(σ)=1wi(Fi(π)−(πi⊤Fi(π))),s.t.(π,w)=ϕ−1(σ). F_i(σ)= 1w_i (F_i(π)-( _i F_i(π))1 ), s.t.~(π,w)=φ^-1(σ). (4.2) In fact, we can establish the equivalence between VI⁡(F¯,Δmn+) VI( F, _mn^+) and VI⁡(F,Δnm) VI(F, _n^m) directly, without going through the two-step construction of lifting and change of variables. Theorem 5. The gap functions of VI⁡(F¯,Δmn+) VI( F, _mn^+) and VI⁡(F,Δnm) VI(F, _n^m) satisfy the following equation. gapF¯(σ)=maxi⁡gapi(πi,πi^)wi,s.t.σ=ϕ⁡(π,w) gap_ F(σ)= _i gap_i( _i, _ i)w_i, s.t.~σ=φ(π,w) (4.3) Consequently, given σ=ϕ⁡(π,w)σ=φ(π,w), gapF¯(σ)=0 gap_ F(σ)=0 if and only if gap⁡(π)=0 gap(π)=0. Proof. Using (π,w)=ϕ−1(σ)(π,w)=φ^-1(σ), we have the following deduction. ⟨F¯(σ),σ′−σ⟩=∑i⟨1wi(Fi(π)−(πi⊤Fi(π))),wi′πi′−wiπi⟩ F(σ),σ -σ = _i 1w_i (F_i(π)-( _i F_i(π))1 ),w_i _i -w_i _i = = ∑i(⟨1wiFi(π),wi′πi′−wiπi⟩−πi⊤Fi(π)wi(wi′−wi))=∑iwi′wi⟨Fi(π),πi′−πi⟩ _i ( 1w_iF_i(π),w_i _i -w_i _i - _i F_i(π)w_i(w_i -w_i) )= _i w_i w_i F_i(π), _i - _i Then, the gap function of VI⁡(F¯,Δmn+) VI( F, _mn^+) is derived as follows. The second line follows from wi′/wi>0w_i /w_i>0 for every i. gapF¯(σ)=supσ′∈Δmn+⟨F¯(σ),σ′−σ⟩=sup(π′,w′)∈Δnm×Δm∘∑iwi′wi⟨Fi(π),πi′−πi⟩ gap_ F(σ)= _σ ∈ _mn^+ F(σ),σ -σ = _(π ,w )∈ _n^m× _m _i w_i w_i F_i(π), _i - _i = = supw′∈Δm∘∑iwi′wisupπi′∈Δn⟨Fi(π),πi′−πi⟩=maxi⁡gapi(πi,πi^)wi _w ∈ _m _i w_i w_i _ _i ∈ _n F_i(π), _i - _i = _i gap_i( _i, _ i)w_i Since gapi(πi,πi^)≥0 gap_i( _i, _ i)≥ 0, wi>0w_i>0, and gapF¯(σ)≥0 gap_ F(σ)≥ 0, we have that gapF¯(σ)=0 gap_ F(σ)=0 if and only if gapi(πi,πi^)=0 gap_i( _i, _ i)=0 for every i, which is equivalently gap⁡(π)=0 gap(π)=0 by Theorem 2. ∎ Therefore, for any w⋆∈Δm∘w ∈ _m , π⋆∈Δnmπ ∈ _n^m is a solution of VI⁡(F,Δnm) VI(F, _n^m) if and only if σ⋆=ϕ⁡(π⋆,w⋆)σ =φ(π ,w ) is a solution of VI⁡(F¯,Δmn+) VI( F, _mn^+). Thus, we have transformed VI⁡(F,Δnm) VI(F, _n^m) to VI⁡(F¯,Δmn+) VI( F, _mn^+) while preserving the solutions. The transformation VI⁡(F¯,Δmn+) VI( F, _mn^+) is not a smooth VI on the closed simplex, because Δmn+ _mn^+ excludes points where ⊤σi=01 _i=0, and F¯(σ) F(σ) blows up as σ approaches these points. Thus, results about the fixed-point bundle framework in Paper 1 do not apply to VI⁡(F¯,Δmn+) VI( F, _mn^+). Nevertheless, we can still substitute F¯(σ) F(σ) into the fixed-point bundle framework in Paper 1 as a mere formality, without invoking any theoretical guarantee provided by the theorems in Paper 1. In the following developments of this section, we establish the equivalence between the formality-only fixed-point bundle framework of VI⁡(F¯,Δmn+) VI( F, _mn^+) and the composite fixed-point bundle framework of VI⁡(F,Δnm) VI(F, _n^m), while the final gap from VI⁡(F¯,Δmn+) VI( F, _mn^+) to an actual smooth VI on a closed simplex will be filled in the next section. 4.2 Isomorphism between fixed-point bundles First, we establish the equivalence between the fixed-point bundles of VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(F¯,Δmn+) VI( F, _mn^+). The fixed-point bundle of VI⁡(F,Δnm) VI(F, _n^m) is the composite fixed-point bundle E→Δnm×Δm∘→ΔnmE→ _n^m× _m → _n^m defined in equation (3.6). From Paper 1, the fixed-point bundle of VI⁡(F¯,Δmn+) VI( F, _mn^+) has fibers B¯′(σ) B (σ) derived as follows. B¯′(σ) B (σ) =σ∘F¯(σ)+vσ|v∈ℝ = \σ F(σ)+vσ|v \ =μ|μi=wiπi∘1wi(Fi(π)−(πi⊤Fi(π)))+vwiπi,(π,w)=ϕ−1(σ),v∈ℝ = \μ| _i=w_i _i 1w_i (F_i(π)-( _i F_i(π))1 )+vw_i _i,(π,w)=φ^-1(σ),v \ =reshape(τ~(π)+v¯w⊙π)|(π,w)=ϕ−1(σ),v¯∈ℝ = \ reshape( τ(π)+ vw π)|(π,w)=φ^-1(σ), v \ We exclude the point given by v¯=0 v=0 from each fiber B¯′(σ) B (σ) in correspondence with the composite fixed-point bundle of VI⁡(F,Δnm) VI(F, _n^m). Then, the fixed-point bundle E¯→Δmn+ E→ _mn^+ of VI⁡(F¯,Δmn+) VI( F, _mn^+) is as equation (4.4) shows. E¯→α¯Δmn+ E α _mn^+ (4.4) α¯((,,,))=σ α ((σ,μ) )=σ E¯=⋃σ∈Δmn+σ×B¯(σ) E= _σ∈ _mn^+\σ\× B(σ) B¯(σ)=reshape(τ~(π)+v¯w⊙π)|(π,w)=ϕ−1(σ),v¯∈ℝ∖0 B(σ)= \ reshape( τ(π)+ vw π)|(π,w)=φ^-1(σ), v \0\ \ Note that B¯(σ) B(σ) consists of μ=reshape⁡(τ~(π)+v¯w⊙π)μ= reshape( τ(π)+ vw π), while B~(π,w) B(π,w) consists of τ=τ~(π)+v¯w⊙πτ= τ(π)+ vw π. This indicates that the bundles E→Δnm×Δm∘E→ _n^m× _m and E¯→Δmn+ E→ _mn^+ have very similar fibers. We can show that there is a homeomorphism between E and E¯ E, given by Φ as equation (4.5) shows. Φ⁡(π,τ)=(σ,μ), (π,τ)=(σ,μ), s.t.σ=ϕ⁡(π,norm⁡([⊤τi])),μi=τi s.t.~σ=φ(π, norm([1 _i])), _i= _i (4.5) Φ−1(σ,μ)=(π,τ), ^-1(σ,μ)=(π,τ), s.t.π=ϕπ−1(σ),τi=μi s.t.~π=φ^-1_π(σ), _i= _i It can be verified that Φ and Φ−1 ^-1 are indeed inverse maps of each other between E and E¯ E. Then, Φ is a homeomorphism between E and E¯ E if it is continuous. However, we aim to prove further that Φ is a homeomorphism between larger sets containing E and E¯ E. Recall that for every (π,τ)∈E(π,τ)∈ E, we have τ∈ℝ±m×nτ ^m× n_±. Since μ in E¯ E and τ in E are related by a reshape, we introduce another set ℝ±mn:=μ∈ℝmn|(⊤μi)(⊤μj)>0,∀i,j=reshape(ℝ±m×n),R^mn_±:=\μ ^mn|(1 _i)(1 _j)>0,~∀ i,j\= reshape(R^m× n_±), and study the homeomorphism Φ with τ∈ℝ±m×nτ ^m× n_± and μ∈ℝ±mnμ ^mn_±. Theorem 6. For (π,τ)∈Δnm×ℝ±m×n(π,τ)∈ _n^m×R^m× n_± and (σ,μ)∈Δmn+×ℝ±mn(σ,μ)∈ _mn^+×R^mn_±, the maps Φ and Φ−1 ^-1 satisfy (Φ−1∘Φ)(π,τ) ( ^-1 )(π,τ) =(π,τ), =(π,τ), (4.6) (Φ∘Φ−1)(σ,μ) ( ^-1 )(σ,μ) =(reshape⁡(norm⁡([⊤μi])⊙ϕπ−1(σ)),μ). = ( reshape ( norm([1 _i]) φ^-1_π(σ) ),μ ). Consequently, Φ is a real-analytic homeomorphism such that Δnm×ℝ±m×n≅(Δmn+×ℝ±mn)∩(σ,μ)|ϕw−1(σ)=norm⁡([⊤μi]). _n^m×R^m× n_± ( _mn^+×R^mn_± )∩ \(σ,μ)|φ^-1_w(σ)= norm([1 _i]) \. (4.7) Proof. For each (π,τ)∈Δnm×ℝ±m×n(π,τ)∈ _n^m×R^m× n_±, under the map Φ−1∘Φ ^-1 , we have (π,τ)↦(ϕ⁡(π,norm⁡([⊤τi])),reshape⁡(τ))↦ (π,τ) (φ(π, norm([1 _i])), reshape(τ) ) (ϕπ−1(ϕ⁡(π,norm⁡([⊤τi]))),reshape⁡(reshape⁡(τ))) (φ^-1_π (φ(π, norm([1 _i])) ), reshape( reshape(τ)) ) =(π,τ). =(π,τ). For each (σ,μ)∈Δmn+×ℝ±mn(σ,μ)∈ _mn^+×R^mn_±, under the map Φ∘Φ−1 ^-1, we have (σ,μ)↦(ϕπ−1(σ),reshape⁡(μ))↦ (σ,μ) (φ^-1_π(σ), reshape(μ) ) (ϕ⁡(ϕπ−1(σ),norm⁡([⊤μi])),reshape⁡(reshape⁡(μ))) (φ (φ^-1_π(σ), norm([1 _i]) ), reshape( reshape(μ)) ) =(reshape⁡(norm⁡([⊤μi])⊙ϕπ−1(σ)),μ). = ( reshape ( norm([1 _i]) φ^-1_π(σ) ),μ ). Φ−1∘Φ ^-1 is always an identity map, whereas Φ∘Φ−1 ^-1 is an identity map if and only if norm⁡([⊤μi])=ϕw−1(σ) norm([1 _i])=φ^-1_w(σ). To prove that Φ is a bijection between the LHS (left-hand side) and RHS (right-hand side) in equation (4.7), we further need to show that Φ⁡(LHS)⊂RHS ( LHS)⊂ RHS and Φ−1(RHS)⊂LHS ^-1( RHS)⊂ LHS. For every (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) with (π,τ)∈Δnm×ℝ±m×n(π,τ)∈ _n^m×R^m× n_± (belonging to the LHS), by definition of Φ , we have ϕw−1(σ)=ϕw−1(ϕ⁡(π,norm⁡([⊤τi])))=norm⁡([⊤τi])=norm⁡([⊤μi]). φ^-1_w(σ)=φ^-1_w (φ(π, norm([1 _i])) )= norm([1 _i])= norm([1 _i]). Then, (σ,μ)(σ,μ) belongs to the RHS. Thus, Φ⁡(LHS)⊂RHS ( LHS)⊂ RHS. For every (π,τ)=Φ−1(σ,μ)(π,τ)= ^-1(σ,μ) with (σ,μ)(σ,μ) belonging to the RHS, we trivially have (π,τ)∈Δnm×ℝ±m×n(π,τ)∈ _n^m×R^m× n_± (belonging to the LHS). Thus, Φ−1(RHS)⊂LHS ^-1( RHS)⊂ LHS. Therefore, we have proved that Φ is a bijection between the LHS and RHS in equation (4.7). The maps ϕφ and ϕ−1φ^-1 in equation (4.1) are real-analytic because they consist only of elementary operations and the denominator ∑aσi,a>0 _a _i,a>0 on Δmn+ _mn^+. The maps Φ and Φ−1 ^-1 in equation (4.5) are also real-analytic because they consist only of elementary operations and the real-analytic ϕφ and ϕ−1φ^-1, and the denominator ∑i⊤τi>0 _i1 _i>0 on ℝ±m×nR^m× n_±. Therefore, Φ is a real-analytic homeomorphism between the LHS and RHS in equation (4.7). ∎ Theorem 6 shows that Φ is a homeomorphism beyond E and E¯ E. This is useful in establishing the equivalence between the three equivalent characterizations of VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(F¯,Δmn+) VI( F, _mn^+), because E and E¯ E are only solutions of the characterizations, but with Φ in equation (4.7), we can compare the function values of the characterizations whether on solutions or not. Next, we show that E→Δnm×Δm∘E→ _n^m× _m and E¯→Δmn+ E→ _mn^+ are isomorphic as fiber bundles. Given general fiber bundles E→BE αB and E′→α′B′E α B , a bundle isomorphism is a pair of homeomorphisms (ψ:B→B′,Ψ:E→E′)(ψ:B→ B , :E→ E ) such that α′∘Ψ=ψ∘α =ψ α. Theorem 7. (Φ,ϕ)( ,φ) is a bundle isomorphism such that E→Δnm×Δm∘≅E¯→Δmn+.E→ _n^m× _m E→ _mn^+. Proof. First, we prove that Φ is a homeomorphism between E and E¯ E. We have E⊂Δnm×ℝ±m×nE⊂ _n^m×R^m× n_± trivially. By the definition of B¯(σ) B(σ), every μ∈B¯(σ)μ∈ B(σ) for some σ∈Δmn+σ∈ _mn^+ satisfies ⊤μi=v¯wi1 _i= vw_i with w=ϕw−1(σ)w=φ^-1_w(σ). Thus, E¯⊂(Δmn+×ℝ±mn)∩(σ,μ)|ϕw−1(σ)=norm⁡([⊤μi]) E⊂( _mn^+×R^mn_±)∩\(σ,μ)|φ^-1_w(σ)= norm([1 _i])\. We further need to show Φ⁡(E)⊂E¯ (E)⊂ E and Φ−1(E¯)⊂E ^-1( E)⊂ E. For every (π,τ)∈E(π,τ)∈ E, we have τ=τ~(π)+v¯w⊙πτ= τ(π)+ vw π for some w∈Δm∘w∈ _m and v¯≠0 v≠ 0. Then, under the map Φ , we have (π,τ~(π)+v¯w⊙π)↦ (π, τ(π)+ vw π) (ϕ⁡(π,w),reshape⁡(τ~(π)+v¯w⊙π)) (φ(π,w), reshape( τ(π)+ vw π) ) =(σ,reshape(τ~(π)+v¯w⊙π))s.t.(π,w)=ϕ−1(σ), = (σ, reshape( τ(π)+ vw π) ) s.t.~(π,w)=φ^-1(σ), which indicates that Φ⁡(π,τ)∈E¯ (π,τ)∈ E. For every (σ,μ)∈E¯(σ,μ)∈ E, we have μ=reshape⁡(τ~(π)+v¯w⊙π)μ= reshape( τ(π)+ vw π) for (π,w)=ϕ−1(σ)(π,w)=φ^-1(σ) and v¯≠0 v≠ 0. Then, under the map Φ−1 ^-1, we have (σ,reshape⁡(τ~(π)+v¯w⊙π))↦ (σ, reshape( τ(π)+ vw π)) (ϕπ−1(σ),τ~(π)+v¯w⊙π) (φ^-1_π(σ), τ(π)+ vw π ) =(π,τ~(π)+v¯w⊙π)s.t.(π,w)=ϕ−1(σ), = (π, τ(π)+ vw π ) s.t.~(π,w)=φ^-1(σ), which indicates that Φ−1(σ,μ)∈E ^-1(σ,μ)∈ E. Therefore, we have Φ⁡(E)⊂E¯ (E)⊂ E and Φ−1(E¯)⊂E ^-1( E)⊂ E, so Φ is a homeomorphism between E and E¯ E. We already have that ϕφ is a homeomorphism between Δnm×Δm∘ _n^m× _m and Δmn+ _mn^+. For (Φ,ϕ)( ,φ) to constitute a bundle isomorphism, we additionally need α¯∘Φ=ϕ∘α1 α =φ _1, where α1 _1 and α¯ α are bundle projections. For each (π,τ)∈E(π,τ)∈ E, under the maps Φ:E→E¯ :E→ E and α¯:E¯→Δmn+ α: E→ _mn^+, we have (π,τ)↦(ϕ⁡(π,norm⁡([⊤τi])),reshape⁡(τ))↦ϕ⁡(π,norm⁡([⊤τi])),(π,τ) (φ(π, norm([1 _i])), reshape(τ)) φ(π, norm([1 _i])), and under the maps α1:E→Δnm×Δm∘ _1:E→ _n^m× _m and ϕ:Δnm×Δm∘→Δmn+φ: _n^m× _m → _mn^+, we have (π,τ)↦(π,norm⁡([⊤τi]))↦ϕ⁡(π,norm⁡([⊤τi])).(π,τ) (π, norm([1 _i])) φ(π, norm([1 _i])). Therefore, we obtain α¯∘Φ=ϕ∘α1 α =φ _1, so (Φ,ϕ)( ,φ) is a bundle isomorphism between E→Δnm×Δm∘E→ _n^m× _m and E¯→Δmn+ E→ _mn^+. ∎ 4.3 Equivalence between characterizations Having obtained the homeomorphism in equation (4.7), we then use it to establish the equivalence between the characterizations of VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(F¯,Δmn+) VI( F, _mn^+). First, we introduce the objects for which the equivalence is to be studied, where we replace the FPKKTs with the fixed-point bundle equations, and we add sections of the fixed-point bundles into the study. Sections. The sections τˇ(π) τ(π) and τ~(π) τ(π) of the bundle E∪(π,τ~(π))|π∈Δnm→ΔnmE∪\(π, τ(π))|π∈ _n^m\→ _n^m are as equation (3.9) shows. The sections μˇ(σ) μ(σ) and μ~(σ) μ(σ) of the bundle E¯∪(σ,reshape⁡(τ~(ϕπ−1(σ))))|σ∈Δmn+→Δmn+ E∪\(σ, reshape( τ(φ^-1_π(σ))))|σ∈ _mn^+\→ _mn^+ are from Paper 1, shown in equation (4.8). μˇ(σ)= μ(σ)= σ∘(F¯(σ)−(mini,a⁡F¯i,a(σ))) σ ( F(σ)- ( _i,a F_i,a(σ) )1 ) (4.8) μ~(σ)= μ(σ)= σ∘(F¯(σ)−(σ⊤F¯(σ)))=(I−σ⊤)(σ∘F¯(σ)) σ ( F(σ)- (σ F(σ) )1 )= (I- 1 ) (σ F(σ) ) Fixed-point bundle equations. The fixed-point bundle equation of E→ΔnmE→ _n^m is as equation (3.8) shows. The fixed-point bundle equation of E¯→Δmn+ E→ _mn^+ is G¯(σ,μ)=0 G(σ,μ)=0 from Paper 1, where G¯(σ,μ)=(I−σ⊤)(σ∘F¯(σ)−μ). G(σ,μ)= (I- 1 )(σ F(σ)-μ). (4.9) Brouwer functions. The Brouwer function (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ) characterizing VI⁡(F,Δnm) VI(F, _n^m) is as equation (3.3) shows. The Brouwer function characterizing VI⁡(F¯,Δmn+) VI( F, _mn^+) is from Paper 1. In fact, (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ) in this paper can only be shown equivalent to an index-wise variant (σ^,r¯,v¯)=M¯(σ,μ)( σ, r, v)= M(σ,μ) as shown in equation (4.10), instead of the original Brouwer function in Paper 1. (σ^,r¯,v¯)=M¯(σ,μ),s.t.[σ^i∘r¯i−μiri−F¯i(σ)−v¯i⊤σ^i−⊤σi]=0( σ, r, v)= M(σ,μ), s.t.~ bmatrix σ_i r_i- _i\\ r_i- F_i(σ)- v_i1\\ 1 σ_i-1 _i\\ bmatrix=0 (4.10) The index-wise variant (σ^,r¯,v¯)=M¯(σ,μ)( σ, r, v)= M(σ,μ) has two modifications compared to the original one. First, in Paper 1, all the components of r¯ r depend on a single scalar v¯ v, whereas in equation (4.10), each r¯i r_i depends on an independent v¯i v_i. Second, the constraint ∑i⊤σ^i=1 _i1 σ_i=1 in Paper 1 changes to the index-wise constraint ⊤σ^i−⊤σi1 σ_i-1 _i in equation (4.10). This variant essentially uses the index-wise v¯i v_i to control each ⊤σ^i1 σ_i instead of the entire ∑i⊤σ^i _i1 σ_i. MCPs. The two MCPs characterizing VI⁡(F,Δnm) VI(F, _n^m) and VI⁡(F¯,Δmn+) VI( F, _mn^+) are as equation (4.11) shows. mcp⁡(π,τ) mcp(π,τ) originates from MCP (3.5), and (r,v)(r,v) is additionally constrained by the Brouwer function (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ) to make π the only optimization variable. mcp⁡(σ,μ) mcp(σ,μ) originates from the MCP in Paper 1, where (r¯,v¯)( r, v) is originally additionally constrained by the Brouwer function in Paper 1 to make σ the only optimization variable, but we modify (r¯,v¯)( r, v) to be additionally constrained by the index-wise variant (σ^,r¯,v¯)=M¯(σ,μ)( σ, r, v)= M(σ,μ). mcp⁡(π,τ) mcp(π,τ) =∑i(πi⊤ri−τi⊤ln⁡πi−τi⊤ln⁡ri),s.t.(π^,r,v)=M⁡(π,τ) = _i ( _i r_i- _i _i- _i r_i ), s.t.~( π,r,v)=M(π,τ) (4.11) mcp⁡(σ,μ) mcp(σ,μ) =σ⊤r¯−μ⊤ln⁡σ−μ⊤ln⁡r¯,s.t.(σ^,r¯,v¯)=M¯(σ,μ) =σ r-μ σ-μ r, s.t.~( σ, r, v)= M(σ,μ) Equivalence. The sections τˇ(π) τ(π) and μˇ(σ) μ(σ) do not have a useful relation themselves, but since gapi(πi,πi^)=⊤τˇi(π) gap_i( _i, _ i)=1 τ_i(π) and gapF¯(σ)=⊤μˇ(σ) gap_ F(σ)=1 μ(σ), they are related through the gap function relation in Theorem 5. The relations between the remaining characterizations are as the following proposition shows. Proposition 8. For (π,τ)∈Δnm×ℝ±m×n(π,τ)∈ _n^m×R^m× n_± and (σ,μ)∈Δmn+×ℝ±mn(σ,μ)∈ _mn^+×R^mn_±, let ϕw−1(σ)=norm⁡([⊤μi])φ^-1_w(σ)= norm([1 _i]) and (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ), then the following equalities hold. (i) μ~i(σ)=τ~i(π) μ_i(σ)= τ_i(π). (i) G¯i(σ,μ)=Gi(π,τ) G_i(σ,μ)=G_i(π,τ). (i) σ^i=wiπ^i σ_i=w_i π_i and r¯i=ri/wi r_i=r_i/w_i, where (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ) and (σ^,r¯,v¯)=M¯(σ,μ)( σ, r, v)= M(σ,μ). (iv) mcp⁡(σ,μ)=mcp⁡(π,τ) mcp(σ,μ)= mcp(π,τ). Proof. (i) Substituting σ=ϕ⁡(π,w)σ=φ(π,w) and F¯(σ) F(σ), we have (σ∘F¯(σ))i=wiπi∘1wi(Fi(π)−(πi⊤Fi(π)))=τ~i(π). (σ F(σ) )_i=w_i _i 1w_i (F_i(π)-( _i F_i(π))1 )= τ_i(π). Then, since ⊤τ~i(π)=01 τ_i(π)=0 for every index i, we obtain the equation μ~i(σ)=(σ∘(F¯(σ)−(σ⊤F¯(σ))))i=τ~i(π)−(∑j⊤τ~j(π))σi=τ~i(π). μ_i(σ)= (σ ( F(σ)- (σ F(σ) )1 ) )_i= τ_i(π)- ( _j1 τ_j(π) ) _i= τ_i(π). (i) Substituting (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) and σ=ϕ⁡(π,w)σ=φ(π,w), using μ~i(σ)=τ~i(π) μ_i(σ)= τ_i(π) in the first line, and using w=ϕw−1(σ)=norm⁡([⊤μi])=norm⁡([⊤τi])w=φ^-1_w(σ)= norm([1 _i])= norm([1 _i]) in the second line, we have G¯i(σ,μ) G_i(σ,μ) =μ~i(σ)−(μi−(⊤μ)σi)=τ~i(π)−(τi−(∑i⊤τi)wiπi) = μ_i(σ)- ( _i-(1 μ) _i )= τ_i(π)- ( _i-( _i1 _i)w_i _i ) =τ~i(π)−(τi−(⊤τi)πi)=Gi(π,τ). = τ_i(π)- ( _i-(1 _i) _i )=G_i(π,τ). (i) In (π^,r,v)=M⁡(π,τ)( π,r,v)=M(π,τ), each viv_i is given by the zero of qi(vi)=0q_i(v_i)=0 as equation (3.4) shows. In (σ^,r¯,v¯)=M¯(σ,μ)( σ, r, v)= M(σ,μ), each v¯i v_i is given by the zero of q¯i(v¯i)=0 q_i( v_i)=0 via a similar derivation from equation (4.10). qi(vi) q_i(v_i) =⊤τiFi(π)+vi−1 =1 _iF_i(π)+v_i1-1 q¯i(v¯i) q_i( v_i) =⊤μiF¯i(σ)+v¯i−⊤σi=wi(⊤μiFi(π)−(πi⊤Fi(π))+v¯iwi−1) =1 _i F_i(σ)+ v_i1-1 _i=w_i (1 _iF_i(π)-( _i F_i(π))1+ v_iw_i1-1 ) Comparing qi(vi)q_i(v_i) and q¯i(v¯i) q_i( v_i), it can be directly observed that when σ=ϕ⁡(π,w)σ=φ(π,w) and μi=τi _i= _i, their zeros viv_i and v¯i v_i satisfy vi=v¯iwi−πi⊤Fi(π)v_i= v_iw_i- _i F_i(π). Then, we obtain r¯i=ri/wi r_i=r_i/w_i at this time from ri=Fi(π)+vir_i=F_i(π)+v_i1 and r¯i=F¯i(σ)+v¯i r_i= F_i(σ)+ v_i1. Then, σ^i=wiπ^i σ_i=w_i π_i follows from π^i=τi/ri π_i= _i/r_i and σ^i=μi/r¯i σ_i= _i/ r_i. (iv) By r¯i=ri/wi r_i=r_i/w_i from the Brouwer functions and σi=wiπi _i=w_i _i, we have σi∘r¯i=πi∘ri _i r_i= _i r_i, then it follows that mcp⁡(σ,μ)=mcp⁡(π,τ) mcp(σ,μ)= mcp(π,τ). ∎ Proposition 8 will be used to transform the computational formula of the formality-only path-following algorithm for VI⁡(F¯,Δmn+) VI( F, _mn^+) into the computational formula of the path-following algorithm for VI⁡(F,Δnm) VI(F, _n^m), and we will deal with the difference between the index-wise variants and the original Brouwer functions and MCPs. 4.4 Equivalence between differential properties In Paper 1, to maintain the constraint σ∈Δσ∈ , σ is represented by the softmax function such that σ=softmax⁡(θ)σ= softmax(θ). Then, the differentiable properties are measured by differentiating with respect to θ instead of σ. In this subsection, we derive the equivalence between the differential properties of the two fixed-point bundles. First, we also use the softmax function to represent π to maintain the constraint π∈Δnmπ∈ _n^m. Theorem 9. For any σ∈Δmn+σ∈ _mn^+, π∈Δnmπ∈ _n^m, and w∈Δm∘w∈ _m , σ=ϕ⁡(π,w)σ=φ(π,w) if and only if there exists θ such that σ=softmax⁡(θ)=exp⁡(θ)∑i⊤exp⁡(θi),wi=⊤exp⁡(θi)∑i⊤exp⁡(θi),πi=softmax⁡(θi)=exp⁡(θi)⊤exp⁡(θi).σ= softmax(θ)= (θ) _i1 ( _i),~w_i= 1 ( _i) _i1 ( _i),~ _i= softmax( _i)= ( _i)1 ( _i). (4.12) Proof. Given σ=ϕ⁡(π,w)σ=φ(π,w), we have the softmax representations with θ=ln⁡σθ= σ. Given the softmax representations, σi=wiπi _i=w_i _i can be directly verified. ∎ Theorem 9 shows that if we represent σ,π,wσ,π,w using softmax functions, then σ=ϕ⁡(π,w)σ=φ(π,w) is automatically satisfied. If we additionally represent μ=reshape⁡(τ)μ= reshape(τ), then (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) is satisfied as long as w⁡(θ)=norm⁡([⊤τi])w(θ)= norm([1 _i]). Consequently, viewed as functions in θ, the sections τ~(π) τ(π) and μ~(σ) μ(σ) in Proposition 8 (i) are in fact the same functions. Viewed as functions in (θ,τ)(θ,τ), the fixed-point bundle functions G¯(σ,μ) G(σ,μ) and G⁡(π,τ)G(π,τ) in Proposition 8 (i) are in fact the same functions as long as w⁡(θ)=norm⁡([⊤τi])w(θ)= norm([1 _i]). The differentiable properties are measured by differentiating with respect to θ, so we derive the differentials of σ,π,wσ,π,w with respect to θ. dσ= dσ= exp⁡(θ)∘dθ⊤exp⁡(θ)−⊤(exp⁡(θ)∘dθ)(⊤exp⁡(θ))2exp⁡(θ)=σ∘dθ−(σ⊤dθ)σ (θ) dθ1 (θ)- 1 ( (θ) dθ )(1 (θ))^2 (θ)=σ dθ-(σ dθ)σ dπi= d _i= exp⁡(θi)∘dθi⊤exp⁡(θi)−⊤(exp⁡(θi)∘dθi)(⊤exp⁡(θi))2exp⁡(θi)=πi∘dθi−(πi⊤dθi)πi ( _i) d _i1 ( _i)- 1 ( ( _i) d _i )(1 ( _i))^2 ( _i)= _i d _i-( _i d _i) _i dwi= dw_i= ⊤(exp⁡(θi)∘dθi)∑j⊤exp⁡(θj)−∑j⊤(exp⁡(θj)∘dθj)(∑j⊤exp⁡(θj))2(⊤exp⁡(θi))=wiπi⊤dθi−wi∑jwjπj⊤dθj 1 ( ( _i) d _i ) _j1 ( _j)- _j1 ( ( _j) d _j )( _j1 ( _j))^2(1 ( _i))=w_i _i d _i-w_i _jw_j _j d _j The derivation shows that the differentials dσ,dπ,dwdσ,dπ,dw are as equation (4.13) shows. dσ/σ=(I−σ⊤)dθ,dπi/πi=(I−πi⊤)dθi,dw/w=(I−w⊤)[πi⊤dθi]dσ/σ= (I-1σ )dθ,~d _i/ _i= (I-1 _i )d _i,~dw/w= (I-1w )[ _i d _i] (4.13) Note that softmax⁡(θ+k)=softmax⁡(θ) softmax(θ+k1)= softmax(θ), indicating that softmax is invariant under adding a scaled 1, and adding a scaled 1 to dθdθ does not change the differentials dσdσ or dπdπ. Thus, we denote dθ¯ dθ and dθ~ dθ in equation (4.14) such that σ⊤dθ¯=0σ dθ=0 and πi⊤dθ~i=0 _i dθ_i=0, where dθ¯ dθ has already appeared in Paper 1. dθ¯:=(I−σ⊤)dθ,dθ~i:=(I−πi⊤)dθi dθ:= (I-1σ )dθ, dθ_i:= (I-1 _i )d _i (4.14) As in Paper 1, instead of using the plain dθdθ, we actually use dθ¯ dθ and dθ~ dθ as the differentials measuring the differentiable properties of the fixed-point bundles. First, we study their relation. Lemma 10. Let (σ,π,w)(σ,π,w) be subject to equation (4.12), then for any dθdθ, the following statements hold. (i) σ⊤dθ~=0σ dθ=0. (i) πi⊤dθ¯i=0 _i dθ_i=0 for every index i if and only if dθ~=dθ¯ dθ= dθ, which is equivalently dw=0dw=0. Proof. (i) For σ⊤dθ~σ dθ, we can derive σ⊤dθ~=∑jwjπj⊤dθ~jσ dθ= _jw_j _j dθ_j. Then, we have σ⊤dθ~=0σ dθ=0 since πj⊤dθ~j=0 _j dθ_j=0. (i) For πi⊤dθ¯i _i dθ_i, dθ¯−dθ~ dθ- dθ, and dwdw, we can derive the following three equations. πi⊤dθ¯i _i dθ_i =πi⊤(dθi−(σ⊤dθ))=πi⊤dθi−∑jwjπj⊤dθj = _i (d _i-(σ dθ)1 )= _i d _i- _jw_j _j d _j dθ¯i−dθ~i dθ_i- dθ_i =dθi−(σ⊤dθ)−(dθi−(πi⊤dθi))=(πi⊤dθi)−(∑jwjπj⊤dθj) =d _i-(σ dθ)1-(d _i-( _i d _i)1)=( _i d _i)1-( _jw_j _j d _j)1 dw/w dw/w =(I−w⊤)[πi⊤dθi]=[πi⊤dθi−∑jwjπj⊤dθj]. = (I-1w )[ _i d _i]= [ _i d _i- _jw_j _j d _j ]. Therefore, πi⊤dθ¯i=0 _i dθ_i=0 for every index i, dθ~=dθ¯ dθ= dθ, and dw=0dw=0 are all equivalent to πi⊤dθi=∑jwjπj⊤dθj _i d _i= _jw_j _j d _j for every index i. ∎ The differentiable properties of the fixed-point bundle are governed by the section μ~(σ) μ(σ) and τ~i(π) τ_i(π), such that their differentials appear in the singular manifold, differential equation, Newton equation, and gradient of related functions. In Paper 1, dμ~(σ)d μ(σ) is measured with respect to dθ¯ dθ. Next, we measure dτ~i(π)d τ_i(π) with respect to dθ~ dθ and derive the relation to dμ~(σ)d μ(σ) since μ~(σ)=τ~i(π) μ(σ)= τ_i(π). In the following equations, let δij _ij be the Kronecker delta, such that δij=1 _ij=1 when i=ji=j and δij=0 _ij=0 when i≠ji≠ j. Theorem 11. Let σ=ϕ⁡(π,w)σ=φ(π,w), then the differentials of τ~(π) τ(π) and μ~(σ) μ(σ) satisfy dτ~i(π)=dμ~i(σ)=σi∘J¯i(σ)dθ¯=σi∘J¯i(σ)dθ~=πi∘Ji(π)dθ~,d τ_i(π)=d μ_i(σ)= _i J_i(σ) dθ= _i J_i(σ) dθ= _i J_i(π) dθ, (4.15) where J⁡(π)J(π) and J¯(σ) J(σ) are given by the following equations. Jij(π) J_ij(π) :=(I−πi⊤)(∂Fi(π)∂πj∘πj+δij((I−πi⊤)Fi(π))∘I)(I−πj⊤)+kwiwjπj⊤ := (I-1 _i ) ( ∂ F_i(π)∂ _j _j+ _ij ( (I-1 _i )F_i(π) ) I ) (I-1 _j )+kw_iw_j1 _j (4.16) J¯(σ) J(σ) :=(I−σ⊤)(∂F¯(σ)∂σ∘σ+((I−σ⊤)F¯(σ))∘I)(I−σ⊤)+kσ⊤ := (I-1σ ) ( ∂ F(σ)∂σ σ+ ( (I-1σ ) F(σ) ) I ) (I-1σ )+k1σ Consequently, wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π). Proof. (1) Proving dτ~i(π)=dμ~i(σ)=σi∘J¯i(σ)dθ¯d τ_i(π)=d μ_i(σ)= _i J_i(σ) dθ. In Paper 1, we have dμ~i(σ)=σi∘J¯i(σ)dθ¯d μ_i(σ)= _i J_i(σ) dθ. Proposition 8 shows that τ~i(π)=μ~i(σ) τ_i(π)= μ_i(σ), thus dτ~i(π)=dμ~i(σ)d τ_i(π)=d μ_i(σ). (2) Proving dτ~i(π)=σi∘J¯i(σ)dθ¯=σi∘J¯i(σ)dθ~d τ_i(π)= _i J_i(σ) dθ= _i J_i(σ) dθ. Note that dθdθ and dθ~ dθ lead to the same dπdπ in equation (4.13) since I−πi⊤I-1 _i is idempotent. Then, substituting dθdθ with dθ~ dθ does not change dτ~i(π)d τ_i(π) since τ~i(π) τ_i(π) depends only on π. Thus, we have the following derivation, where (I−σ⊤)dθ~=dθ~(I-1σ ) dθ= dθ by Lemma 10 (i). dτ~i(π)=σi∘J¯i(σ)dθ¯=σi∘J¯i(σ)(I−σ⊤)dθ=σi∘J¯i(σ)(I−σ⊤)dθ~=σi∘J¯i(σ)dθ~ d τ_i(π)= _i J_i(σ) dθ= _i J_i(σ) (I-1σ )dθ= _i J_i(σ) (I-1σ ) dθ= _i J_i(σ) dθ (3) Proving dτ~i(π)=πi∘Ji(π)dθ~d τ_i(π)= _i J_i(π) dθ. The differential dτ~(π)d τ(π) is derived as follows. In the third line, we use ⊤dπi=01 d _i=0. In the last line, we use dπi/πi=dθ~i=(I−πi⊤)dθ~id _i/ _i= dθ_i=(I-1 _i ) dθ_i. dτ~i(π)=(I−πi⊤)(πi∘∑j∂Fi(π)∂πjdπj+Fi(π)∘dπi)−⊤(πi∘Fi(π))dπi d τ_i(π)= (I- _i1 ) ( _i _j ∂ F_i(π)∂ _jd _j+F_i(π) d _i )-1 ( _i F_i(π) )d _i =(I−πi⊤)(πi∘∑j∂Fi(π)∂πjdπj+(Fi(π)∘I−(πi⊤Fi(π))I)dπi)−(πi⊤Fi(π))πi⊤dπi = (I- _i1 ) ( _i _j ∂ F_i(π)∂ _jd _j+ (F_i(π) I-( _i F_i(π))I )d _i )- ( _i F_i(π) ) _i1 d _i =πi∘(I−πi⊤)(∑j(∂Fi(π)∂πj∘πj)dπjπj+((I−πi⊤)Fi(π))∘dπiπi) = _i (I-1 _i ) ( _j ( ∂ F_i(π)∂ _j _j ) d _j _j+ ( (I-1 _i )F_i(π) ) d _i _i ) =πi∘(I−πi⊤)(∑j(∂Fi(π)∂πj∘πj)(I−πj⊤)dθ~j+((I−πi⊤)Fi(π))∘(I−πi⊤)dθ~i) = _i (I-1 _i ) ( _j ( ∂ F_i(π)∂ _j _j ) (I-1 _j ) dθ_j+ ( (I-1 _i )F_i(π) ) (I-1 _i ) dθ_i ) Substituting Jij(π)J_ij(π) and using πi⊤dθ~i=0 _i dθ_i=0, we obtain dτ~i(π)=πi∘Ji(π)dθ~d τ_i(π)= _i J_i(π) dθ. (4) Proving wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π). Let J¯0ij(σ) J_0ij(σ) and J0ij(π)J_0ij(π) be the corresponding matrices with the arbitrary scalar k set to 00. Then, we have the following derivation, where kσ⊤k1σ and kwiwjπj⊤kw_iw_j1 _j are eliminated by (I−σ⊤)(I-1σ ) and (I−πj⊤)(I-1 _j ), and (I−σ⊤)(I-1σ ) and (I−πj⊤)(I-1 _j ) are absorbed into J¯0ij(σ) J_0ij(σ) and J0ij(π)J_0ij(π) by idempotence. σi∘J¯i(σ)dθ~ _i J_i(σ) dθ =σi∘J¯i(σ)(I−σ⊤)dθ=σi∘∑jJ¯0ij(σ)dθj = _i J_i(σ) (I-1σ )dθ= _i _j J_0ij(σ)d _j πi∘Ji(π)dθ~ _i J_i(π) dθ =πi∘∑jJij(π)(I−πj⊤)dθj=πi∘∑jJ0ij(π)dθj = _i _jJ_ij(π) (I-1 _j )d _j= _i _jJ_0ij(π)d _j Then, by σi∘J¯i(σ)dθ~=πi∘Ji(π)dθ~ _i J_i(σ) dθ= _i J_i(π) dθ for every dθdθ, we have wiJ¯0ij(σ)=J0ij(π)w_i J_0ij(σ)=J_0ij(π). From wi(kσ⊤)ij=wi(kσj⊤)=kwiwjπj⊤w_i(k1σ )_ij=w_i(k1 _j )=kw_iw_j1 _j , we obtain wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π). ∎ Theorem 11 establishes the equivalence between the differentials of τ~(π) τ(π) and μ~(σ) μ(σ), which govern the differential properties of the fixed-point bundles. Furthermore, we obtain wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π) between the two Jacobian-like matrices, which play a central role in the predictor-corrector algorithm. The derivative of F¯(σ) F(σ) is given by ∂F¯i(σ)∂σj=1wiwj(I−πi⊤)∂Fi(π)∂πj(I−πi⊤)⊤−δij1wi(F¯i(σ)⊤+F¯i(σ)⊤). ∂ F_i(σ)∂ _j= 1w_iw_j (I-1 _i ) ∂ F_i(π)∂ _j (I-1 _i ) - _ij 1w_i ( F_i(σ)1 +1 F_i(σ) ). (4.17) It would be very complicated to directly verify wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π) via symbolic derivation from equation (4.16), but we have verified in numerical experiments that no significant difference can be found between Diag⁡[wiI]J¯(σ) Diag[w_iI] J(σ) and J⁡(π)J(π) with k=0k=0. 5 Path-following on the fixed-point bundles 5.1 Transforming the predictor-corrector framework Paper 1 adopts the predictor-corrector framework to perform path-following on the fixed-point bundle. This framework alternates between predictor steps and corrector steps. A predictor step updates along the tangent direction of the fixed-point bundle, which is given by the differential equations of G¯(σ,μ)=0 G(σ,μ)=0 or G⁡(π,τ)=0G(π,τ)=0. A corrector step updates onto the fixed-point bundle, which can be given by the Newton equations of G¯(σ,μ)=0 G(σ,μ)=0 or G⁡(π,τ)=0G(π,τ)=0, or by the gradients of mcp⁡(σ,μ) mcp(σ,μ) and mcp⁡(π,τ) mcp(π,τ). We have the formality-only predictor and corrector for G¯(σ,μ)=0 G(σ,μ)=0 from Paper 1. In this subsection, we use the equivalence established previously to obtain the predictor and corrector for G⁡(π,τ)=0G(π,τ)=0. Differential equations and Newton equations of G¯(σ,μ)=0 G(σ,μ)=0 and G⁡(π,τ)=0G(π,τ)=0. In Paper 1, the differential equation and Newton equation of G¯(σ,μ)=0 G(σ,μ)=0 are given by equations (5.1) and (5.2). (J¯(σ)+(⊤μ)I)dθ¯=(I−σ⊤)(dμ/σ) ( J(σ)+(1 μ)I ) dθ= (I-1σ )(dμ/σ) (5.1) (J¯(σ)+(⊤μ)I)dθ¯=−G¯(σ,μ)/σ ( J(σ)+(1 μ)I ) dθ=- G(σ,μ)/σ (5.2) Proposition 12. Let (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) and ϕw−1(σ)=norm⁡([⊤μi])φ^-1_w(σ)= norm([1 _i]). In both differential equation (5.1) and Newton equation (5.2), we have πi⊤dθ¯i=0 _i dθ_i=0 for every index i. Consequently, dθ¯=dθ~ dθ= dθ and dw=0dw=0. Proof. Differential equation (5.1) and Newton equation (5.2) can be derived as follows. We first multiply both sides by Diag⁡[wiI] Diag[w_iI] in the first lines, and then substitute wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π) and w=norm⁡([⊤τi])w= norm([1 _i]) in the second lines. Diag⁡[wiI](J¯(σ)+(⊤μ)I)dθ¯ Diag [w_iI ] ( J(σ)+(1 μ)I ) dθ =Diag⁡[wiI](I−σ⊤)(dμ/σ) = Diag [w_iI ] (I-1σ )(dμ/σ) (J⁡(π)+Diag⁡[(⊤τi)I])dθ¯ (J(π)+ Diag [(1 _i)I ] ) dθ =[(I−πi⊤)(dτi/πi)] = [ (I-1 _i )(d _i/ _i) ] Diag⁡[wiI](J¯(σ)+(⊤μ)I)dθ¯ Diag [w_iI ] ( J(σ)+(1 μ)I ) dθ =−Diag⁡[wiI](G¯(σ,μ)/σ) =- Diag [w_iI ] ( G(σ,μ)/σ ) (J⁡(π)+Diag⁡[(⊤τi)I])dθ¯ (J(π)+ Diag [(1 _i)I ] ) dθ =−[Gi(π,τ)/πi] =- [G_i(π,τ)/ _i ] Then, multiplying the i-th row blocks on both sides by πi⊤ _i and using πi⊤Ji(π)=0 _i J_i(π)=0, we obtain πi⊤dθ¯i=0 _i dθ_i=0. Then, dθ¯=dθ~ dθ= dθ and dw=0dw=0 follow from Lemma 10 (i). ∎ Proposition 8 already shows that G¯(σ,μ)=0 G(σ,μ)=0 and G⁡(π,τ)=0G(π,τ)=0 are in fact the same function with the same variable and the same value. Then, from the proof of Proposition 12 and dθ¯=dθ~ dθ= dθ, it immediately follows that the differential equation and Newton equation of G⁡(π,τ)=0G(π,τ)=0 are given by equations (5.3) and (5.4). (J⁡(π)+Diag⁡[(⊤τi)I])dθ~=[(I−πi⊤)(dτi/πi)] (J(π)+ Diag [(1 _i)I ] ) dθ= [ (I-1 _i )(d _i/ _i) ] (5.3) (J⁡(π)+Diag⁡[(⊤τi)I])dθ~=[(I−πi⊤)(Fi(π)−τi/πi)] (J(π)+ Diag [(1 _i)I ] ) dθ= [ (I-1 _i )(F_i(π)- _i/ _i) ] (5.4) These equations also indicate that (π,τ)∈E(π,τ)∈ E is a singular point if and only if ∑i⊤τi _i1 _i is an eigenvalue of −[(1/wi)Jij(π)]-[(1/w_i)J_ij(π)]. In Paper 1, (σ,μ)∈E¯(σ,μ)∈ E is a singular point if and only if ⊤μ1 μ is an eigenvalue of −J¯(σ)- J(σ). This aligns with the homeomorphism between (σ,μ)(σ,μ) and (π,τ)(π,τ). Gradients of mcp⁡(σ,μ) mcp(σ,μ) and mcp⁡(π,τ) mcp(π,τ). Recall that mcp⁡(σ,μ) mcp(σ,μ) is a variant of the original MCP characterizing VI⁡(F¯,Δmn+) VI( F, _mn^+) in Paper 1. Denote the original MCP as mcp¯(σ,μ) mcp(σ,μ). In Paper 1, the gradient of mcp¯(σ,μ) mcp(σ,μ) is derived as the first equality in the following equation. dmcp¯(σ,μ)= d mcp(σ,μ)= (σ−σ^)⊤(J¯(σ)+(r¯−(I−σ⊤)F¯(σ))∘I)dθ¯=dmcp(σ,μ) (σ- σ ) ( J(σ)+ ( r- (I-1σ ) F(σ) ) I ) dθ=d mcp(σ,μ) In the first equality, (σ−σ^)⊤dv¯=0(σ- σ) 1d v=0 is used to eliminate dv¯d v in the derivation in Paper 1. From dmcp¯(σ,μ)d mcp(σ,μ) to dmcp(σ,μ)d mcp(σ,μ), the elimination of dv¯id v_i remains as the following equation shows. Thus, we have the second equality in the above equation, indicating that dmcp(σ,μ)d mcp(σ,μ) also yields that expression. (σ−μ/r¯)⊤[dv¯i]= (σ-μ/ r) [d v_i1]= ∑i(σi−σ^i)⊤dv¯i=∑i(wiπi−wiπ^i)⊤dv¯i=0 _i( _i- σ_i) 1d v_i= _i(w_i _i-w_i π_i) 1d v_i=0 Then, we have the following derivation from that expression. In the first line, we use mcp⁡(π,τ)=mcp⁡(σ,μ) mcp(π,τ)= mcp(σ,μ) in Proposition 8. In the second line, we replace dθ¯=(I−σ⊤)dθ dθ=(I-1σ )dθ with (I−σ⊤)dθ~(I-1σ ) dθ, and use σ⊤dθ~=0σ dθ=0 in Lemma 10 (i). The substitution is valid because dθdθ and dθ~ dθ lead to the same dπdπ in equation (4.13) since I−πi⊤I-1 _i is idempotent, which in turn leads to the same dmcp(π,τ)d mcp(π,τ). In the third line, we use r¯i=ri/wi r_i=r_i/w_i and σ^i=wiπ^i σ_i=w_i π_i in Proposition 8 (i), wiJ¯ij(σ)=Jij(π)w_i J_ij(σ)=J_ij(π) in Theorem 11, as well as σ⊤F¯(σ)=0σ F(σ)=0 and wiF¯i(σ)=Fi(π)−(πi⊤Fi(π))w_i F_i(σ)=F_i(π)-( _i F_i(π))1. In the fourth line, we use ri=Fi(π)+vir_i=F_i(π)+v_i1 and π^i⊤Fi(π)+vi=⊤τi π_i F_i(π)+v_i=1 _i. dmcp(π,τ)=dmcp(σ,μ) d mcp(π,τ)=d mcp(σ,μ) = = (σ−σ^)⊤(J¯(σ)+(r¯−(I−σ⊤)F¯(σ))∘I)dθ~ (σ- σ ) ( J(σ)+ ( r- (I-1σ ) F(σ) ) I ) dθ = = ∑i,j(πi−π^i)⊤(Jij(π)+δij(ri−(Fi(π)−(πi⊤Fi(π))))∘I)dθ~j _i,j ( _i- π_i ) (J_ij(π)+ _ij (r_i- (F_i(π)-( _i F_i(π))1 ) ) I ) dθ_j = = ∑i,j(πi−π^i)⊤(Jij(π)+δij(⊤τi+(πi−π^i)⊤Fi(π))I)dθ~j _i,j ( _i- π_i ) (J_ij(π)+ _ij (1 _i+( _i- π_i) F_i(π) )I ) dθ_j Ignoring the higher-order term ((πi−π^i)⊤Fi(π))(πi−π^i)(( _i- π_i) F_i(π))( _i- π_i), we obtain the inexact gradient of mcp⁡(π,τ) mcp(π,τ) in equation (5.5). ∇mcp(π,τ)=(J⁡(π)+Diag⁡[(⊤τi)I])⊤[πi−π^i]∇ mcp(π,τ)= (J(π)+ Diag [(1 _i)I ] ) [ _i- π_i ] (5.5) Regularized Newton equations. In Paper 1, the standard Newton corrector is used to prove the convergence rate of the overall predictor-corrector path-following algorithm, and two regularized Newton correctors are provided for practical use. The regularized Newton equations turn the coefficient matrix positive semidefinite and control its condition number using a regularization parameter, so that the iteration is stabilized and the update steps do not blow up when approaching singularities. Here, we derive the two corresponding regularized Newton correctors for VI⁡(F,Δnm) VI(F, _n^m). We denote JG:=J⁡(π)+Diag⁡[(⊤τi)I]J_G:=J(π)+ Diag[(1 _i)I] as a shorthand notation. From the standard Newton equation (5.4), by multiplying both sides by JGJ_G and adding a regularization parameter δH _H to the coefficient, we obtain the regularized Newton equation (5.6). (JG⊤JG+δHI)dθ= (J_G J_G+ _HI )dθ= −JG⊤[(I−πi⊤)(Fi(π)−τi/πi)] -J_G [ (I-1 _i )(F_i(π)- _i/ _i) ] (5.6) dθ~i= dθ_i= (I−πi⊤)dθi (I-1 _i )d _i In Paper 1, the right-hand side of the standard Newton equation (5.4) can be transformed into σ−σ^σ- σ as the first line of the following equation shows, where vgbv_gb1 is changed to [vgb,i][v_gb,i1] to reflect the change from the original Brouwer function to the index-wise variant (σ^,r¯,v¯)=M¯(σ,μ)( σ, r, v)= M(σ,μ). Given (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) and ϕw−1(σ)=norm⁡([⊤μi])φ^-1_w(σ)= norm([1 _i]), this transformation can be further transformed as follows. σr¯∘(J¯(σ)+(⊤μ)I)(dθ¯+[vgb,i]) σ r ( J(σ)+(1 μ)I ) ( dθ+[v_gb,i1] ) =−(σ−σ^) =- (σ- σ ) wiπiri/wi∘∑j((1/wi)Jij(π)+δij(1/wi)(⊤τi)I)(dθ¯i+vgb,i) w_i _ir_i/w_i _j ((1/w_i)J_ij(π)+ _ij(1/w_i)(1 _i)I ) ( dθ_i+v_gb,i1 ) =−(wiπi−wiπ^i) =- (w_i _i-w_i π_i ) πiri∘∑j(Jij(π)+δij(⊤τi)I)(dθ¯i+vgb,i) _ir_i _j (J_ij(π)+ _ij(1 _i)I ) ( dθ_i+v_gb,i1 ) =−(πi−π^i) =- ( _i- π_i ) Then, by multiplying both sides by JGJ_G and adding a regularization parameter δH _H to the coefficient, we obtain the regularized Newton equation (5.7). (JG⊤∘[πiri]∘JG+δHI)dθ= (J_G [ _ir_i ] J_G+ _HI )dθ= −JG⊤[πi−π^i] -J_G [ _i- π_i ] (5.7) dθ~i= dθ_i= (I−πi⊤)dθi (I-1 _i )d _i 5.2 Transferring the convergence results So far, we have completed the formality-only fixed-point bundle framework of VI⁡(F¯,Δmn+) VI( F, _mn^+) and the composite fixed-point bundle framework of VI⁡(F,Δnm) VI(F, _n^m). Now, we are finally ready to fill the final gap from VI⁡(F¯,Δmn+) VI( F, _mn^+) to an actual smooth VI on a closed simplex, such that the theoretical guarantees in Paper 1 apply. As in Paper 1, the path-following iteration consists of four parts: (i) reducing μ>0μ>0 or τ>0τ>0 toward 00; (i) avoiding singular points along the fibers by adding βσβσ or βnorm([⊤τi])⊙πβ norm([1 _i]) π such that ⊤μ+β1 μ+β avoids the eigenvalues of −J¯(σ)- J(σ), or ∑i⊤τi+β _i1 _i+β avoids the eigenvalues of −Diag⁡[(1/wi)I]J(π)- Diag[(1/w_i)I]J(π); (i) a predictor step along the tangent direction of G¯(σ,μ)=0 G(σ,μ)=0 or G⁡(π,τ)=0G(π,τ)=0; (iv) a corrector step toward G¯(σ,μ)=0 G(σ,μ)=0 or G⁡(π,τ)=0G(π,τ)=0. First, we establish the equivalence between the path-following algorithms for VI⁡(F¯,Δmn+) VI( F, _mn^+) and VI⁡(F,Δnm) VI(F, _n^m) with standard Newton correctors. Theorem 13. Let the starting points be (σinit,vinitσinit)( _ init,v_ init _ init) and (πinit,vinitwinit⊙πinit)( _ init,v_ initw_ init _ init) such that σinit=ϕ⁡(πinit,winit) _ init=φ( _ init,w_ init). Let the iteration consist of the following three kinds of updates. (i) μ′=(1−η)μ =(1-η)μ and τ′=(1−η)τ =(1-η)τ. (i) μ^=μ+βσ μ=μ+βσ and τ^=τ+βnorm([⊤τi])⊙π τ=τ+β norm([1 _i]) π. (i) σi′=ϕw,i−1(σ)softmax(ln⁡ϕπ,i−1(σ)+dθ¯i)σ _i=φ^-1_w,i(σ) softmax( φ^-1_π,i(σ)+ dθ_i) and πi′=softmax⁡(ln⁡πi+dθ~i)π _i= softmax( _i+ dθ_i) with dθ¯ dθ and dθ~ dθ subject to the differential equations or the Newton equations of G¯(σ,μ)=0 G(σ,μ)=0 and G⁡(π,τ)=0G(π,τ)=0. Then, (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) and winit=ϕw−1(σ)=norm⁡([⊤μi])w_ init=φ^-1_w(σ)= norm([1 _i]) hold constantly during the iteration. Proof. The first equality (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) holds if and only if σ=ϕ⁡(π,w)σ=φ(π,w), μ=reshape⁡(τ)μ= reshape(τ), and w=norm⁡([⊤μi])w= norm([1 _i]). Given the first equality, the second equality holds if and only if w=winitw=w_ init. Thus, we use these four equalities to verify that the two conditions are preserved during the iteration. At the starting points (σinit,vinitσinit)( _ init,v_ init _ init) and (πinit,vinitwinit⊙πinit)( _ init,v_ initw_ init _ init), from σinit=ϕ⁡(πinit,winit) _ init=φ( _ init,w_ init), we can verify σ=ϕ⁡(π,w)σ=φ(π,w), μ=reshape⁡(τ)μ= reshape(τ), ϕw−1(σ)=winitφ^-1_w(σ)=w_ init, and norm⁡([⊤μi])=winit norm([1 _i])=w_ init. Thus, the conditions (σ,μ)=Φ⁡(π,τ)(σ,μ)= (π,τ) and winit=ϕw−1(σ)=norm⁡([⊤μi])w_ init=φ^-1_w(σ)= norm([1 _i]) hold at the starting points. Next, it remains to prove that given that the two conditions hold, the updates preserve them. Update (i): Since σ and π remain unchanged, we have σ=ϕ⁡(π,w)σ=φ(π,w) and w=winitw=w_ init.For μ′μ , we have norm⁡([⊤μi′])=norm⁡([⊤μi]) norm([1 μ _i])= norm([1 _i]), so w=norm⁡([⊤μi′])w= norm([1 μ _i]) given w=norm⁡([⊤μi])w= norm([1 _i]). For μ′μ and τ′τ , we have μ′=reshape⁡(τ′)μ = reshape(τ ) given μ=reshape⁡(τ)μ= reshape(τ). Thus, the two conditions are preserved. Update (i): Since σ and π remain unchanged, we have σ=ϕ⁡(π,w)σ=φ(π,w) and w=winitw=w_ init. For μ μ, we have norm⁡([⊤μ^i])=norm⁡([⊤μi+βwinit,i])=winit norm([1 μ_i])= norm([1 _i+β w_ init,i])=w_ init given ⊤σi=wi1 _i=w_i and w=norm⁡([⊤μi])w= norm([1 _i]). For μ μ and τ τ, we have σ=reshape⁡(norm⁡([⊤τi])⊙π)σ= reshape( norm([1 _i]) π) given μ=reshape⁡(τ)μ= reshape(τ) and norm⁡([⊤μi])=w norm([1 _i])=w, then we have μ^=reshape⁡(τ^) μ= reshape( τ). Thus, the two conditions are preserved. Update (i): The update σi′=ϕw,i−1(σ)softmax(ln⁡ϕπ,i−1(σ)+dθ¯i)σ _i=φ^-1_w,i(σ) softmax( φ^-1_π,i(σ)+ dθ_i) preserves ϕw−1(σ)=wφ^-1_w(σ)=w such that ϕw−1(σ′)=wφ^-1_w(σ )=w as well, and then w=winitw=w_ init is also preserved. Since μ and τ remain unchanged, we have μ=reshape⁡(τ)μ= reshape(τ) and w=norm⁡([⊤μi])w= norm([1 _i]). Proposition 12 shows that dθ¯=dθ~ dθ= dθ for either the differential equations or the Newton equations, then softmax⁡(ln⁡ϕπ,i−1(σ)+dθ¯i)=πi′ softmax( φ^-1_π,i(σ)+ dθ_i)=π _i given σ=ϕ⁡(π,w)σ=φ(π,w), which indicates σ′=ϕ⁡(π′,w)σ =φ(π ,w). Thus, the two conditions are preserved. Therefore, the conditions hold at the starting points, and the updates preserve them, so they hold constantly during the iteration. ∎ In Theorem 13 (i), σ is updated by σi′=ϕw,i−1(σ)softmax(ln⁡ϕπ,i−1(σ)+dθ¯i)σ _i=φ^-1_w,i(σ) softmax( φ^-1_π,i(σ)+ dθ_i), instead of the Paper 1 version σ′=softmax⁡(ln⁡σ+dθ¯)σ = softmax( σ+ dθ). In fact, the former is a second-order correction of the latter to enforce w as an exact constant on top of the dw=0dw=0 implied by Proposition 12. The difference between the two updates for σ is derived as follows, where dπi=πi∘dθ~id _i= _i dθ_i in equation (4.13) and dθ¯=dθ~ dθ= dθ in Proposition 12 are used in the second line. softmaxi(ln⁡σ+dθ¯)−ϕw,i−1(σ)softmax(ln⁡ϕπ,i−1(σ)+dθ¯i) softmax_i( σ+ dθ)-φ^-1_w,i(σ) softmax( φ^-1_π,i(σ)+ dθ_i) = = σi+σi∘dθ¯i+o⁡(dθ¯i)−ϕw,i−1(σ)(ϕπ,i−1(σ)+ϕπ,i−1(σ)∘dθ¯i+o⁡(dθ¯i))=o⁡(dθ¯i) _i+ _i dθ_i+o( dθ_i)-φ^-1_w,i(σ)(φ^-1_π,i(σ)+φ^-1_π,i(σ) dθ_i+o( dθ_i))=o( dθ_i) A second-order correction o⁡(dθ¯i)o( dθ_i) at each update does not change the convergence rate of the original predictor-corrector framework [20]. Theorem 13 shows that the predictor-corrector path-following algorithms on E¯→Δmn+ E→ _mn^+ and E→Δm∘×Δnm→ΔnmE→ _m × _n^m→ _n^m generate sequences of (σ,μ)(σ,μ) and (π,τ)(π,τ) that correspond exactly via the homeomorphism Φ . Furthermore, w remains constant during the entire iteration. This can be used to fill the final gap by constructing a smooth VI⁡(F~,Δmn) VI( F, _mn) on the closed simplex such that all results in Paper 1 apply. Specifically, we want a map F~ F that is real-analytic on the closed simplex Δmn _mn, such that F~ F and F¯ F have the same value on the subset W⁡(winit)=σ∈Δmn|ϕw,i−1(σ)=winitW(w_ init)=\σ∈ _mn|φ^-1_w,i(σ)=w_ init\, which is given by equation (5.8). F~i(σ)= F_i(σ)= 1winit,i(Fi(π~)−(π~i⊤Fi(π~))) 1w_ init,i (F_i( π)-( π_i F_i( π))1 ) (5.8) s.t. s.t. π~i(σ)=(1−ϕw,i−1(σ)w~i(σ))πinit,i+σiw~i(σ) π_i(σ)= (1- φ^-1_w,i(σ) w_i(σ) ) _ init,i+ _i w_i(σ) w~(σ)=ϕw−1(σ)+(winit−ϕw−1(σ))2 w(σ)=φ^-1_w(σ)+(w_ init-φ^-1_w(σ))^2 For every σ∈Δmnσ∈ _mn, we have π~(σ)∈Δnm π(σ)∈ _n^m, because there is ⊤π~i(σ)=11 π_i(σ)=1 from ⊤σi=ϕw,i−1(σ)1 _i=φ^-1_w,i(σ) and ⊤πinit,i=11 _ init,i=1, and π~i(σ)≥0 π_i(σ)≥ 0 from w~(σ)≥ϕw−1(σ) w(σ)≥φ^-1_w(σ). Considering also that F is real-analytic on Δnm _n^m and the denominators winit>0w_ init>0 and w~(σ)>0 w(σ)>0, we obtain that F~(σ) F(σ) is real-analytic on the simplex Δmn _mn. Furthermore, when ϕw−1(σ)=winitφ^-1_w(σ)=w_ init, we have w~(σ)=winit w(σ)=w_ init and π~(σ)=ϕπ−1(σ) π(σ)=φ^-1_π(σ), then F~(σ)=F¯(σ) F(σ)= F(σ). Thus, F~ F and F¯ F have the same value on the subset W⁡(winit)W(w_ init). We also need to compare the derivatives of F~ F and F¯ F in addition to their function values. Proposition 14. On W⁡(winit)W(w_ init), the differential equation (5.1) or Newton equation (5.2) remains the same when the operator F¯ F is replaced by F~ F. Proof. Proposition 12 shows that dw=0dw=0 in differential equation (5.1) and Newton equation (5.2). For the differentials dF~(σ)d F(σ) and dF¯(σ)d F(σ), if σ∈W⁡(winit)σ∈ W(w_ init) and dw=0dw=0, we have dF~(σ)=dF¯(σ)d F(σ)=d F(σ) since F~(σ) F(σ) and F¯(σ) F(σ) have the same value on W⁡(winit)W(w_ init). Then, expanding dF~(σ)d F(σ) and dF¯(σ)d F(σ), we have ∂F~(σ)∂σ∘σ∘dθ¯=∂F¯(σ)∂σ∘σ∘dθ¯. ∂ F(σ)∂σ σ dθ= ∂ F(σ)∂σ σ dθ. Note that the differential equations and Newton equations depend on the operator F¯ F only through its value F¯(σ) F(σ) and its differential (∂F~(σ)/∂σ)∘σ∘dθ¯(∂ F(σ)/∂σ) σ dθ. Thus, we obtain that on W⁡(winit)W(w_ init), the differential equations or Newton equations are the same for operators F¯ F and F~ F. ∎ Theorem 13 shows that the update of the predictor-corrector path-following algorithm keeps σ constantly on W⁡(winit)W(w_ init). Theorem 14 shows that on W⁡(winit)W(w_ init), the differential equations or Newton equations are the same for operators F¯ F and F~ F. Therefore, the predictor-corrector path-following algorithms applied to VI⁡(F¯,Δmn+) VI( F, _mn^+) and VI⁡(F~,Δmn) VI( F, _mn) produce exactly the same iteration sequence. The problem VI⁡(F~,Δmn) VI( F, _mn) is a real-analytic VI on the closed simplex such that all the results in Paper 1 apply to it. Then, the theoretical guarantees of the path-following on the fixed-point bundle transfer from VI⁡(F~,Δmn) VI( F, _mn) to VI⁡(F¯,Δmn+) VI( F, _mn^+), and then to VI⁡(F,Δnm) VI(F, _n^m). 5.3 The complete path-following algorithm In the last subsection, we adopt a singularity avoidance mechanism for VI⁡(F,Δnm) VI(F, _n^m) corresponding to the one for VI⁡(F¯,Δmn+) VI( F, _mn^+) in Paper 1, which is setting τ^=τ+βw⊙π τ=τ+β w π with w=norm⁡([⊤τi])w= norm([1 _i]) such that ∑i⊤τi+β _i1 _i+β avoids the eigenvalues of −Diag⁡[(1/wi)I]J(π)- Diag[(1/w_i)I]J(π). Now that we have shown that w can remain unaffected during the iteration process, we can add a mechanism to arbitrarily modify w in singularity avoidance. Specifically, we reallocate ⊤τi1 _i to change w=norm⁡([⊤τi])w= norm([1 _i]). Similar to Paper 1, τ must satisfy τ>0τ>0 to ensure path-following leading to solutions of VI⁡(F,Δnm) VI(F, _n^m). Since τˇ(π) τ(π) is a section of the fixed-point bundle, for any (π,τ)∈E(π,τ)∈ E, we have τi=τˇi(π)+kiπi _i= τ_i(π)+k_i _i. Considering mina⁡τˇi,a(π)=0 _a τ_i,a(π)=0, we have τ>0τ>0 if and only if ⊤τi>⊤τˇi(π)1 _i>1 τ_i(π). Thus, we have τ^>0 τ>0 and ∑i⊤τ^i=∑i⊤τi+β _i1 τ_i= _i1 _i+β if and only if there exists w~i∈Δm∘ w_i∈ _m such that τ τ satisfies ⊤τ^i=w~i(∑i⊤τi+β−∑i⊤τˇi(π))+⊤τˇi(π).1 τ_i= w_i ( _i1 _i+β- _i1 τ_i(π) )+1 τ_i(π). (5.9) In singularity avoidance, we select w~∈Δm∘ w∈ _m and β such that ∑i⊤τi+β _i1 _i+β avoids the eigenvalues of −Diag⁡[(1/wi)I]J(π)- Diag[(1/w_i)I]J(π) with wi=⊤τ^i/(∑j⊤τ^j)w_i=1 τ_i/( _j1 τ_j) given by equation (5.9). Then, the τ τ after singularity avoidance is τ^=τ~(π)+(∑i⊤τi+β)w⊙π τ= τ(π)+( _i1 _i+β)w π. Our experimental results are based on this singularity avoidance mechanism with w~∈Δm∘ w∈ _m randomly selected, which has better performance than keeping w fixed. The path-following algorithm for VI⁡(F,Δnm) VI(F, _n^m) is given in Algorithm 1. Apart from its singularity avoidance step, it corresponds to Algorithm 1 in Paper 1 via the equivalence established in this paper. Algorithm 1 Path-following on the composite fixed-point bundle 1: A smooth map F:Δnm→ℝm×nF: _n^m ^m× n and its derivative [∂Fi/∂πj][∂ F_i/∂ _j], a designated starting point πinit∈Δnm _ init∈ _n^m, and a desired precision ϵ>0ε>0 2: Set (π0,τ0)=(πinit,vinitwinit⊙πinit)( _0, _0)=( _ init,v_ initw_ init _ init) for a winit∈Δm∘w_ init∈ _m and a sufficiently large vinitv_ init 3: repeat 4: repeat 5: Compute (π^k,rk,vk)=M⁡(πk,τt)( π_k,r_k,v_k)=M( _k, _t) by solving bisection problem (3.4) 6: Construct the matrix J⁡(πk)J( _k) in equation (4.16) 7: Solve regularized Newton equation (5.6) or (5.7) for dθ~k dθ_k with δH=∥G⁡(πk,τt)∥/(mn) _H= G( _k, _t) /(mn) 8: Update πk+1,i=softmax⁡(ln⁡πk,i+dθ~k,i) _k+1,i= softmax( _k,i+ dθ_k,i) 9: until ∥G⁡(πk,τt)∥≤ϵ/(mn) G( _k, _t) ≤ε/(mn) 10: Set τ^=τ~(π)+(∑i⊤τi+β)w⊙π τ= τ(π)+( _i1 _i+β)w π with wi=⊤τ^i/(∑j⊤τ^j)w_i=1 τ_i/( _j1 τ_j) given by equation (5.9), such that ∑i⊤τt,i+βt _i1 _t,i+ _t avoids the nonzero eigenvalues of −Diag⁡[(1/wi)I]J(πk)- Diag[(1/w_i)I]J( _k) 11: Update and truncate τt+1=((1−ηt)τ^t).clip⁡(min=ϵ/(mn)) _t+1=((1- _t) τ_t). clip( =ε/(mn)) with a sufficiently small ηt _t 12: Solve differential equation (5.3) for dθ~t dθ_t with dτt=τt+1−τ^td _t= _t+1- τ_t 13: Set π0,i=softmax⁡(ln⁡πk,i+dθ~t,i) _0,i= softmax( _k,i+ dθ_t,i) 14: until ∑i⊤τˇi(πk)≤ϵ _i1 τ_i( _k)≤ε 15: return πk _k as an approximate solution of VI⁡(F,Δnm) VI(F, _n^m) The corrector can be either regularized Newton equation (5.6) or regularized Newton equation (5.7). Similar to Paper 1, the former mixes the standard Newton equation (5.4) and the inexact gradient JG⊤[Gi(π,τ)/πi]J_G [G_i(π,τ)/ _i] of ∥[Gi(π,τ)/πi]∥ [G_i(π,τ)/ _i] , while the latter mixes the standard Newton equation (5.4) and the inexact gradient JG⊤[πi−π^i]J_G [ _i- π_i] of mcp⁡(π,τ) mcp(π,τ). A difference from Paper 1 is that the performance of regularized Newton corrector (5.6) is not ideal for solving VI⁡(F,Δnm) VI(F, _n^m). This is because the τ/πτ/π term in corrector (5.6) frequently causes overflow in problems with large dimension, whereas the similar term τ/rτ/r in corrector (5.7) does not, because it is subject to the bisection problem (3.4). The overflow could cause G⁡(π,τ)G(π,τ) to fail to be corrected to 00, triggering singularity avoidance that practically lets the algorithm try to approach the solution in another direction where π has more even components. This leads to much higher iteration cost for VI⁡(F,Δnm) VI(F, _n^m) on simplex product than for VIs on simplex in Paper 1, because VI⁡(F,Δnm) VI(F, _n^m) has much more nonlinearity, which can be seen from the rapid increase in the number of singularity encounters as m increases. Thus, we only test the algorithm with corrector (5.7) in experiments. 6 Experiments We test the algorithm on randomly generated instances of VI⁡(F,Δnm) VI(F, _n^m) with F represented by two different models: a neural network and a payoff tensor. The neural network representation models VI problems with a general real-analytic operator. In our experiments, we use a neural network with architecture [mn,50,mn][mn,50,mn] and tanh activation to represent F, with parameters generated from a uniform distribution. The payoff tensor representation models finite normal-form games. For m-player n-action finite normal-form games, the payoff function is a multilinear function given by an m-th order payoff tensor of shape (n,…,n)(n,…,n), which consists of nmn^m elements, growing exponentially with m. We use the classical low-rank CP (canonical polyadic) representation as a practical alternative to the full tensor representation [21]. Specifically, F is represented by Fi(π)=∇πifi(π)F_i(π)= _ _if_i(π), where fi(π)=∑r∏j=1m(Ur,i,jπj)f_i(π)= _r _j=1^m(U_r,i,j _j) (6.1) is the low-rank CP payoff function. Each UiU_i is a third-order tensor of shape (R,m,n)(R,m,n), reducing the total storage requirement from nmn^m to RmnRmn. In our experiments, each element u∈Uu∈ U is generated from a normal distribution with mean 11 and variance 1/m1/m, so that ∏j=1muj _j=1^mu_j has mean 11 and variance near e−1e-1, preventing overflow or underflow for very large m. We use R=50R=50 in the experiments. Table 1: Statistics (mean / median) solving VI⁡(F,Δnm) VI(F, _n^m) Neural network F Payoff F m,nm,n Iteration count Singularity avoidance times Iteration count Singularity avoidance times 8,28,2 375 / 353 0.9 / 0.0 370 / 359 0.3 / 0.0 8,48,4 500 / 409 5.0 / 0.0 451 / 440 2.1 / 0.0 8,88,8 658 / 553 10.8 / 7.0 507 / 436 3.8 / 0.0 8,168,16 839 / 704 18.4 / 13.5 579 / 511 6.3 / 1.0 8,328,32 1191 / 1006 34.8 / 28.0 735 / 641 12.3 / 9.0 2,82,8 381 / 363 1.0 / 0.0 422 / 413 0.3 / 0.0 4,84,8 442 / 377 3.5 / 0.0 446 / 415 1.4 / 0.0 8,88,8 658 / 553 10.8 / 7.0 507 / 436 3.8 / 0.0 16,816,8 1666 / 1301 46.3 / 33.5 634 / 552 8.9 / 5.5 32,832,8 7481 / 4902 218.1 / 147.5 1124 / 937 27.7 / 21.0 2,1282,128 480 / 401 5.3 / 0.0 492 / 455 1.7 / 0.0 4,644,64 701 / 626 15.5 / 11.5 575 / 482 5.4 / 0.0 8,328,32 1191 / 1006 34.8 / 28.0 735 / 641 12.3 / 9.0 16,1616,16 3178 / 2013 101.2 / 58.0 964 / 841 21.7 / 17.0 32,832,8 7481 / 4902 218.1 / 147.5 1124 / 937 27.7 / 21.0 64,464,4 9676 / 5811 274.5 / 171.0 1387 / 1064 37.7 / 26.0 128,2128,2 5217 / 3934 152.8 / 117.0 839 / 712 17.8 / 12.5 The starting point πinit _ init is also randomly generated, and the required precision is ϵ=10−5ε=10^-5. We solve the problems until gapi(π)<ϵ gap_i(π)<ε rather than gap⁡(π)=∑igapi(π)<ϵ gap(π)= _i gap_i(π)<ε. For dimensions, we fix the player number m=8m=8 and vary the action number n from 22 to 3232, and fix the action number n=8n=8 and vary the player number m from 22 to 3232. Since the algorithm operates in dimension mnmn, we also fix mn=256mn=256 and test (m,n)(m,n) ranging from (2,128)(2,128) to (128,2)(128,2). For each data point, we run 200 instances, totaling 5600 instances. We test the algorithm only with the regularized Newton corrector (5.7). Table 1 reports the mean and median iteration counts and singularity avoidance times. The algorithm succeeds on all 5600 instances. When m is fixed, the iteration count and singularity avoidance count increase mildly as n increases; whereas when n is fixed, they increase dramatically as m increases. When mnmn is fixed, the peak counts appear in the middle rather than at the endpoints (2,128)(2,128) or (128,2)(128,2), indicating that both m and n affect problem difficulty for a fixed total dimension mnmn. In addition, solving VI⁡(F,Δnm) VI(F, _n^m) with payoff F is significantly easier than with neural network F, because neural networks produce greater nonlinearity and a more twisted singular manifold, causing much more singularity avoidance. 7 Conclusion This paper generalizes the fixed-point bundle framework in Paper 1 for VIs with simplex domain to VIs with product-of-simplex domain. The fixed-point bundle E→Δnm×Δm∘→ΔnmE→ _n^m× _m → _n^m of VI⁡(F,Δnm) VI(F, _n^m) has a composite fiber bundle structure. We construct a VI⁡(F¯,Δmn+) VI( F, _mn^+) with simplex domain from VI⁡(F,Δnm) VI(F, _n^m) that preserves the solutions. The central innovation of this paper is to establish the equivalence between their fixed-point bundle frameworks, based on E¯→Δmn+ E→ _mn^+ and E→Δnm×Δm∘E→ _n^m× _m , via the bundle isomorphism (Φ:E→E¯,ϕ:Δnm×Δm∘→Δmn+)( :E→ E,φ: _n^m× _m → _mn^+). The path-following algorithms on the fixed-point bundles keep w constant. The map F¯ F restricted to the slice w=winitw=w_ init can be extended to a real-analytic map F~ F on the closed simplex Δmn _mn. Then, all the results in Paper 1 apply to VI⁡(F~,Δmn) VI( F, _mn). Thus, the path-following algorithm for VI⁡(F,Δnm) VI(F, _n^m) has the same convergence guarantee as in Paper 1. Numerical experiments on 5600 randomly generated problems with dimensions ranging from 2-player 128-action to 128-player 2-action confirm universal success. The singularity avoidance in the framework involves arbitrarily selecting a new w, and we currently adopt the most basic random selection method. Although simple and effective in experiments, computing w based on the state of the path-following process could further improve practical performance. References [1] John Nash. Non-cooperative games. Annals of mathematics, 54(2):286–295, 1951. [2] David M Kreps. Game theory and economic modelling. Oxford University Press, 1990. [3] Zhu Han. Game theory in wireless and communication networks: theory, models, and applications. Cambridge university press, 2012. [4] Tanmoy Hazra and Kushal Anjaria. Applications of game theory in deep learning: a survey. Multimedia Tools and Applications, 81(6):8963–8994, 2022. [5] Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003. [6] Francisco Facchinei, Andreas Fischer, and Veronica Piccialli. On generalized nash games and variational inequalities. Operations Research Letters, 35(2):159–164, 2007. [7] Giuseppe Belgioioso and Sergio Grammatico. Projected-gradient algorithms for generalized equilibrium seeking in aggregative games are preconditioned forward-backward methods. arXiv preprint arXiv:1803.10441, 2018. [8] Peng Yi and Lacra Pavel. Distributed generalized nash equilibria computation of monotone games via double-layer preconditioned proximal-point algorithms. IEEE Transactions on Control of Network Systems, 6(1):299–311, 2018. [9] Axel Dreves, Anna von Heusinger, Christian Kanzow, and Masao Fukushima. A globalized newton method for the computation of normalized nash equilibria. Journal of Global Optimization, 56(2):327–340, 2013. [10] Axel Dreves, Francisco Facchinei, Christian Kanzow, and Simone Sagratella. On the solution of the kkt conditions of generalized nash equilibrium problems. SIAM Journal on Optimization, 21(3):1082–1108, 2011. [11] P Jean-Jacques Herings and Ronald Peeters. Homotopy methods to compute equilibria in game theory. Economic Theory, 42(1):119–156, 2010. [12] Peng Yi and Lacra Pavel. An operator splitting approach for distributed generalized nash equilibria computation. Automatica, 102:111–121, 2019. [13] Nguyen The Vinh and Le Dung Muu. Inertial extragradient algorithms for solving equilibrium problems. Acta Mathematica Vietnamica, 44(3):639–663, 2019. [14] Barbara Franci and Sergio Grammatico. Stochastic generalized nash equilibrium seeking under partial-decision information. Automatica, 137:110101, 2022. [15] Hongbo Sun. A path-following framework on fiber bundle for variational inequalities, 2026. [16] Peter M Gruber. Convex and discrete geometry. Springer, 2007. [17] Steven George Krantz. Function theory of several complex variables, volume 340. American Mathematical Soc., 2001. [18] Walter Rudin. Real and complex analysis. McGraw-Hill Education, 1974. [19] R Tyrrell Rockafellar and Roger JB Wets. Variational analysis. Springer, 1998. [20] Eugene L Allgower and Kurt Georg. Introduction to numerical continuation methods. SIAM, 2003. [21] Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3):455–500, 2009.

Instant research discovery