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

• The product-of-simplex path-following algorithm inherits global convergence with linear gap reduction near solutions.Product-of-simplex domains are canonical for mixed strategies of finite normal-form games.Source: §1 · p. 2
• An equivalent simplex-domain VI connects the two frameworks through a fiber bundle isomorphism.The paper constructs an operator on the simplex domain that preserves the solutions.Source: §1 · pp. 2–3
• The gap function’s decomposable structure yields a composite fixed-point bundle for the product-of-simplex VI.The paper generalizes the three equivalent characterizations used in the simplex-domain framework.Source: §1 · p. 2
• Because the constructed operator is only defined on the open simplex, direct transfer of closed-simplex guarantees fails; a fixed-slice analytic extension restores the guarantee.The operator restricted to the slice determined by w_init can be extended analytically to the closed simplex.Source: §1 · p. 3
• 5,600 randomly generated problems spanning 2-player 128-action to 128-player 2-action all succeeded.The experiments report success in every tested instance.Source: §1 · p. 3

2 Approximate reduction to analytic VI on simplex product

• General VIs are approximately reduced to smooth VIs with real-analytic operators on a product of simplices.The section develops this reduction for both the feasible set and the continuous operator.Source: §2 · p. 3, Approximating continuous functions via… · pp. 4–5

Approximating convex bodies via simplex product

• A simplex-product linear image represents a Minkowski sum of polytopes and can compress the vertex budget from a product of counts to their sum.The resulting polytope can have at most the product of the summands’ vertex counts.Source: Approximating convex bodies via… · pp. 3–4
• For regular Cartesian products of convex bodies, Minkowski-sum approximation has strictly smaller error under the same vertex budget, but the paper does not identify which targets realize this advantage.The paper stops at the guarantee that a simplex-product image approximates at least as well as a simplex image.Source: Approximating convex bodies via… · p. 4
• The approximation guarantee does not establish which convex bodies benefit strictly or provide a mechanism for discovering useful decompositions.Source: Approximating convex bodies via… · p. 4

Approximating continuous functions via analytic functions on simplex product

• Product Dirichlet averaging smooths a continuous operator into a real-analytic operator on the product simplex.The smoothing uses one Dirichlet distribution for each simplex component.Source: Approximating continuous functions via… · pp. 4–5

3.1 Generalizing the three equivalent characterizations

• A product-of-simplex VI solution is equivalent to each component being a solution of its parametric simplex VI, with zero total gap exactly when every component gap is zero.The component gap is the gap function of a parametric VI with the other strategies as its parameter.Source: §3.1 · pp. 5–6
• The Brouwer function is continuous, and the Brouwer fixed-point theorem guarantees paths satisfying the fixed-point KKT system.It is computed by solving the bisection problem for every index.Source: §3.1 · pp. 6–7
• The fixed-point KKT system, Brouwer fixed-point formulation, and barriered mixed complementarity problem are equivalent for each variable-barrier pair.The complementarity problem at τ = 0 is the original problem, while τ > 0 gives its barrier problem.Source: §3.1 · pp. 6–7

3.2 The composite fixed-point bundle

• The composite bundle E is not the entire FPKKT solution space; it includes only points whose τ-component sums share a sign across indices.The construction excludes the case where the scalar v is zero.Source: §3.2 · p. 7
• The product-domain fixed-point bundle has a composite structure: each fiber over a strategy profile is itself a fiber bundle.The paper calls this structure the composite fixed-point bundle.Source: §3.2 · p. 8
• Within each fiber, excluding the point where v = 0 makes the component fibers disjoint; without that exclusion, they share a common point.The source identifies that common point as τ̃(π).Source: §3.2 · p. 8

4.1 Transforming VI(F, ∆m n ) into VI( ¯F, ∆+

• Under σ = ϕ(π, w), the simplex VI preserves zero gaps and solutions, but its operator is not smooth on the closed simplex, so prior guarantees do not apply directly.The construction excludes points where 1⊤σ_i = 0, and its operator blows up as σ approaches those points.Source: §4.1 · pp. 10–11

4.2 Isomorphism between fixed-point bundles

• The map Φ establishes a homeomorphism between the fixed-point bundles and, together with ϕ, a bundle isomorphism between their bases and total spaces.The homeomorphism also extends beyond the bundle solution sets, enabling comparison of characterization functions off solutions.Source: §4.2 · pp. 11–13

4.3 Equivalence between characterizations

• The characterizations correspond under Φ using an index-wise Brouwer-function variant, with transformed variables satisfying ˆσ_i = w_iˆπ_i, r̄_i = r_i/w_i, and equal MCP values.The variant gives each r̄_i an independent v̄_i and constrains each 1⊤ˆσ_i against 1⊤σ_i.Source: §4.3 · pp. 14–15

4.4 Equivalence between differential properties

• The differential-property comparison represents both π and σ with softmax variables to maintain their simplex constraints.The subsection begins deriving equivalence between the differential properties of the two fixed-point bundles.Source: §4.4 · p. 15
• Under the softmax representations, the sections τ̃(π) and μ̃(σ), and the bundle functions G(π, τ) and Ḡ(σ, μ), coincide when w(θ) = norm([1⊤τi]).Source: §4.4 · p. 15
• Softmax is invariant to adding a scaled 1, so the differential directions can be centered without changing dσ or dπ; f dθ = dθ is equivalent to dw = 0.Source: §4.4 · p. 16
• The section differentials agree, and the Jacobian-like matrices satisfy wi J̄ij(σ) = Jij(π), a relation central to the predictor-corrector algorithm.Theorem 11 gives dτ̃i(π) = dμ̃i(σ) = σi ◦ J̄i(σ)dθ = πi ◦ Ji(π)f dθ.Source: §4.4 · pp. 16–18

5.1 Transforming the predictor-corrector framework

• The product-domain and simplex-domain fixed-point equations yield corresponding differential and Newton equations under the established equivalence.Their fixed-point functions agree under the transformation, and the singularity conditions correspond as well.Source: §5.1 · p. 19

5.2 Transferring the convergence results

• A second-order correction keeps w exactly constant without changing the original predictor-corrector framework’s convergence rate.On the constant-w slice, replacing the operator with a real-analytic extension leaves the differential and Newton equations unchanged.Source: §5.2 · pp. 21–22
• The two algorithms produce the same iteration sequence, transferring the simplex-domain theoretical guarantees to the product-of-simplex problem.The extension to the closed simplex lets the results in Paper 1 apply.Source: §5.2 · pp. 20, 22

5.3 The complete path-following algorithm

• The algorithm uses a singularity-avoidance step that can modify w; experiments found random selection performed better than keeping w fixed.The implementation tests regularized Newton corrector (5.7), because corrector (5.6)'s τ/π term can overflow at large dimensions and increase iteration cost.Source: §5.3 · p. 23

Experiments

• The algorithm was tested on 5,600 random instances, including fixed-dimension cases from 2-player 128-action to 128-player 2-action.Each instance used precision ϵ = 10^-5 and the regularized Newton corrector (5.7).Source: §6 · pp. 24–25
• All 5,600 instances succeeded; counts rose mildly with action count, sharply with player count, and peaked at intermediate player/action splits when mn was fixed.The fixed-dimension peak was not at either endpoint, (2, 128) or (128, 2).Source: §6 · p. 25
• Payoff-tensor instances were significantly easier than neural-network instances, whose greater nonlinearity and more twisted singular manifold prompted more singularity avoidance.The neural-network operator used architecture [mn, 50, mn] with tanh activation.Source: §6 · pp. 24–25

Conclusion

• The product-of-simplex fixed-point bundle has a composite fiber bundle structure.Each fiber is itself a fiber bundle.Source: §7 · p. 25
• A bundle isomorphism establishes equivalence between the product-domain and simplex-domain fixed-point bundle frameworks.The simplex-domain operator is extended analytically from the constant-w slice to the closed simplex.Source: §7 · p. 25
• The product-domain path-following algorithm inherits the simplex-domain convergence guarantee, and all 5,600 tested instances succeeded.The randomly generated problems ranged from 2-player 128-action to 128-player 2-action.Source: §7 · p. 25
• Singularity avoidance currently selects a new w randomly; choosing w based on the path state could further improve practical performance.The paper describes random selection as the most basic method.Source: §7 · p. 25