PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing Equilibria in Integer Programming Games with Shared Constraints

Bainian Hao, Hyunwoo Lee, Robert Hildebrand, Carla Michini

arXiv:2610.04279v1math.OCcs.GT

TL;DR

In shared-constraint integer games, a deviation’s feasibility depends on opponents, so equilibrium tests must be conditional. The paper introduces conditional equilibrium inequalities and reports that GZR computes socially optimal equilibria and certifies nonexistence.

  • Problem

    In shared-constraint games, a deviation may be feasible against one opponent profile and infeasible against another, requiring conditional equilibrium comparisons.

    Source: §1 · p. 2

  • Method

    The paper introduces conditional equilibrium inequalities with activation terms that distinguish feasible from infeasible deviations.

    Source: §7 · p. 20

  • Results

    The computational study reports that GZR computes socially optimal equilibria and certifies nonexistence; 16 nonexistence results were certified.

    Source: §7 · p. 20

  • Takeaways & Limitations

    A bisection procedure produces certified bounds on the smallest achievable approximation factor.

    Source: §7 · p. 20

    The one-hot lift limits the capacities and demands that can be handled directly.

    Source: §7 · p. 20

Abstract

from arXiv · show

We develop a cutting-plane algorithm for computing pure Nash equilibria in finite integer games with shared constraints, where a deviation may be feasible against one opponent profile and infeasible against another. Conditional equilibrium inequalities capture this dependence through an explicit activation term. We give affine encodings of costs and activation conditions and prove that the resulting inequalities characterize the equilibrium set exactly. Embedded as lazy constraints in branch-and-cut, they yield the Generalized Zero-Regret algorithm for optimizing a linear objective over exact or approximate equilibria; a bisection procedure maintains certified bounds on the smallest achievable approximation factor. We also prove that, when the conditional polytopes have integral vertices, a concave cost is constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies; for uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity. We give formulations for bin packing, network formation, and knapsack games with shared capacities and evaluate the algorithm on 3,300 instances, computing a socially optimal equilibrium on all but 43, certifying nonexistence on 16, and certifying approximation factors within a few percent where no exact equilibrium exists.

1 Introduction

The introduction frames shared constraints as making deviation feasibility depend on opponents’ strategies, motivating conditional equilibrium inequalities and structural results for computing and optimizing equilibria. It also uses a linear generalized knapsack benchmark to measure the cost of separating equilibrium constraints from equilibrium selection.

1 Introduction

  • In a GIPG, a deviation may be feasible against one opponent profile and infeasible against another, so equilibrium inequalities must condition the no-regret comparison on feasibility.The paper defines the target as pure Nash equilibrium and also considers α-approximate equilibria, where no player can lower cost by more than a factor α ≥ 1.Source: §1 · p. 2

1.1 Literature Review

  • GZR extends the Zero-Regret approach of Dragotto and Scatamacchia (2023) to shared constraints by explicitly accounting for conditional deviation feasibility.The introduction identifies bin packing, network formation, and generalized knapsack games with linear or bilinear costs as application classes.Source: §1.1 · p. 3, §1.2 · p. 4
  • The network model contains integer-splittable bin-packing instances without a PNE, so classical existence results do not automatically carry over to this setting.The cited limitation concerns the sharing rules and feasibility assumptions of those results.Source: §1.1 · p. 3

1.2 Contributions

  • Conditional equilibrium inequalities compare a current strategy with a fixed deviation, switch off when it is infeasible, and exactly characterize equilibria in a MILP for optimizing linear objectives.Costs and activation conditions use affine functions of lifted variables; inequalities can be generated on the fly by best-response computations.Source: §1.2 · pp. 3–4
  • With concave costs, an equilibrium strategy is a vertex or the player is indifferent across strategies on its containing face; strict concavity forces vertex strategies.For uniform integer-splittable bin packing, vertex equilibria exist even without strict concavity.Source: §1.2 · p. 4
  • The structural results yield additional master-problem inequalities, distinguishing cuts valid for every equilibrium from those that only preserve an optimal equilibrium.That distinction matters when certifying nonexistence or optimality.Source: §1.2 · p. 4
  • Across 3,300 instances, GZR computed socially optimal equilibria and certified nonexistence within minutes on most; it identified 15 regular bin-packing instances without PNE.The bisection procedure closed approximation gaps to within a few percent where exact equilibria did not exist, and structural cuts measurably sped up instances where the stronger restriction applied.Source: §1.2 · p. 4
  • The linear generalized knapsack benchmark of Duguet et al. (2025b) is an exact potential game whose social optimum is already an equilibrium, so it measures the cost of separating equilibrium constraints rather than equilibrium selection.Source: §1.2 · p. 4

2 Conditional Equilibrium Inequalities

Conditional equilibrium inequalities encode whether a deviation is feasible against the current opponents, allowing exact equilibrium constraints in a lifted formulation. GZR uses these constraints in branch-and-cut to optimize over exact or approximate equilibria and certify optimality or infeasibility when its search completes.

2 Conditional Equilibrium Inequalities

  • A conditional equilibrium inequality enforces the cost comparison when a candidate deviation is jointly feasible and is automatically satisfied when it is infeasible.An activation function is zero when the deviation is feasible and at least one otherwise.Source: §2 · p. 5

2.1 Lifted Formulation

  • The lifted formulation represents costs and deviation feasibility with affine functions of master variables, enabling the conditional inequalities to be embedded in a mixed-integer model.Feasibility is characterized by the existence of auxiliary variables in the lifted formulation.Source: §2.1 · p. 6

2.2 CEI Exactness

  • Under the affine-representation assumption, the CEI system has vertices in the equilibrium set, and its integer points are lifted α-PNE.The uniqueness of each profile’s auxiliary representation ensures the equilibrium set is finite for the stated closure result.Source: §2.2 · pp. 6–7

2.3 Generalized Zero-Regret Algorithm

  • GZR solves a branch-and-cut master problem, checks each candidate with one best-response problem per player, and adds a violated CEI as a lazy constraint.A candidate with no improving deviation beyond factor α is accepted as an α-PNE when the best-response problems are solved optimally.Source: §2.3 · p. 7
  • With optimal best responses and valid initial inequalities, GZR accepts only α-PNE, and completed searches certify an objective-minimizing equilibrium or prove that none exists.If stopped unresolved before accepting a profile, the search establishes neither existence nor nonexistence.Source: §2.3 · p. 7

3 Vertex Equilibrium Structure

With concave costs and integral vertices in each conditional polytope, an equilibrium strategy’s cost is constant on its minimal face. Strict concavity then forces equilibrium strategies to be vertices, while separability further restricts variation along nontrivial faces.

3 Vertex Equilibrium Structure

  • The face-constancy result applies to arbitrary conditional polytopes, while the later explicit inequalities specialize to equality-and-bound polytopes.The paper also states that strict concavity forces vertex strategies.Source: §3 · p. 8
  • Under concavity and integral vertices, each player’s cost is constant on the minimal face of the conditional polytope containing an equilibrium strategy.Integral vertices ensure each vertex is a feasible integer deviation, so equilibrium implies the strategy minimizes cost over the polytope.Source: §3 · pp. 8–9
  • Under strict concavity and integral vertices, every equilibrium strategy is a vertex of its conditional polytope.This follows because strict concavity is incompatible with cost being constant on a nontrivial face.Source: §3 · p. 9
  • For separable costs, affine behavior in a coordinate’s neighborhood is used to characterize which coordinates can vary along a nontrivial equilibrium face.The result is stated for separable concave functions under the integral-vertices assumption.Source: §3 · p. 9

4 Complementary Solution Algorithms

The complementary procedures use best-response dynamics to find equilibria and α-bisection search to bound the smallest achievable approximation factor. ABS maintains certified bounds when its GZR tests resolve and stops at a target width or resource limit.

4 Complementary Solution Algorithms

  • Adapted random-restart best-response dynamics preserve joint feasibility by choosing responses from conditional strategy sets, and a no-update round certifies a PNE under optimal best responses.Attempts that do not certify a PNE within the prescribed rounds restart from a fresh random profile.Source: §4 · pp. 9–10
  • The initial approximation factor is evaluated against one common final profile, and the resulting finite factor supplies ABS’s initial upper bound.Earlier best-response values from profiles that changed during a round cannot generally be reused.Source: §4 · p. 10
  • ABS maintains certified bounds αL ≤ α* ≤ αU and an αU-PNE, updating the bounds with GZR feasibility tests at trial factors.An accepted equilibrium lowers the upper bound; a proof of infeasibility raises the lower bound, while an unresolved test changes neither certified bound.Source: §4 · p. 10
  • ABS stops when the certified interval is at most ε wide or the resource budget is exhausted; if every test resolves, its width halves at each iteration.The method returns the bounds together with an αU-PNE.Source: §4 · p. 10

5 Applications

The applications instantiate conditional equilibrium inequalities in shared-capacity bin-packing, network-formation, and generalized knapsack games. They use one-hot formulations and capacity-based activation, and derive equilibrium-related cuts and vertex conditions while distinguishing potential and non-potential knapsack variants.

5.1 Integer Splittable Bin Packing (ISBP)

  • Players split integer-sized items across capacity-constrained bins, paying proportional shares of bin costs while assigning all units without exceeding capacities.Source: §5.1 · pp. 10–11

5.1.1 One-hot Encoding and Lifted Formulation

  • A joint-state one-hot lift linearizes ISBP costs as an affine function, enforces consistency and capacities, and uses O(nmuw) variables for maximum capacity u and item size w.The encoding is exact for binary variables.Source: §5.1.1 · p. 11

5.1.2 CEI Encoding and Activation

  • The lifted CEI uses joint states (s, t) to distinguish opponent load t − s, activating big-M when a candidate deviation exceeds bin capacity.Total load alone cannot distinguish whether the deviation fits.Source: §5.1.2 · p. 11

5.1.3 VEST in ISBP

  • In non-uniform ISBP, if a player uses two unsaturated bins at equilibrium, neither is shared; weak VEST inequalities are valid for every PNE and forbid such sharing.This generalizes the cited result of Hao and Michini (2025) to arbitrary instances.Source: §5.1.3 · p. 12
  • In uniform ISBP, every PNE has a same-cost vertex PNE, enabling an optimality-preserving cut requiring at most one unsaturated bin per player, but only for cost-based objectives.The cut may exclude PNE profiles and should not be imposed for arbitrary allocation objectives.Source: §5.1.3 · pp. 12–13

5.2.1 Game Definition

  • The capacitated network formation game lets players split integer demands across paths with proportional flow costs; even parallel-edge instances can lack a PNE.The model restricts attention to directed acyclic networks.Source: §5.2.1 · p. 13

5.2.2 One-hot Encoding and Lifted Formulation

  • For network games, the one-hot lifted-cost construction adds node-balance equations, and fixed-opponent deviation separation is a separable concave-cost integer-flow problem.Source: §5.2.2 · p. 14

5.2.3 CEI Encoding and Activation

  • In NFG, deviation activation is triggered when the deviation exceeds the residual capacity of an edge it uses.The explicit activation formula is given in §C.4 as (C.7).Source: §5.2.3 · p. 14

5.2.4 VEST in NFG

  • At a PNE, every cycle in a player’s undirected free-edge subgraph consists entirely of solo edges, so every shared free edge is a bridge.The implementation adds cycle inequalities for a fixed fundamental cycle basis, a valid subfamily that does not enforce the full condition without separating violated cycles.Source: §5.2.4 · p. 14

5.3.1 Game Definitions

  • GKG is an exact potential game: every jointly feasible unilateral deviation changes the potential by the deviator’s cost change, making every social optimum a PNE.When minimum social cost is positive, its price of stability equals one; a binary MILP can obtain a socially optimal PNE directly.Source: §5.3.1 · pp. 14–15
  • GKGB adds reciprocally bilinear interactions from Dragotto and Scatamacchia (2023), making it non-potential; its enlarged offset preserves nonnegative costs without changing exact equilibria.The offset affects multiplicative approximation factors and cost-based welfare ratios.Source: §5.3.1 · pp. 14–15

5.3.2 CEI Encoding

  • GKG and GKGB CEIs need no one-hot lift: binary fullness indicators encode deviation feasibility, and fixing a deviation makes its cost affine, with McCormick variables linearizing incumbent bilinear terms.The indicator system, CEIs, and big-M values are specified in §C.5.Source: §5.3.2 · p. 15

6 Computational Study

The computational study evaluates GZR across benchmark classes, including equilibrium discovery and optimization on generalized knapsack instances, and uses α-bisection to certify approximation bounds for ISBP instances without a found exact equilibrium. It also examines approximate-equilibrium certificates and structural cuts, reporting that outcomes and benefits vary by instance family and task, with conditions limiting interpretation of some results.

6.2 Results

  • GZR found PNEs in 820 of 842 regular and all 842 non-regular ISBP instances, averaged under nine seconds, and certified nonexistence in 15 regular cases.The 22 regular instances without a found exact PNE comprised 15 certified nonexistence cases and seven unresolved at the time limit.Source: Table 1 · p. 17, §6.2 · p. 18
  • GZR found PNEs in all 128 NFG instances (average POS 1.005 under loose and 1.015 under tight capacities) and all 156 GKG scalability instances through 50 players (POS 1.000 throughout).GKG average times across the three weight–profit correlation levels were 3.3, 72.3, and 303.0 seconds; 27 time-limit terminations lacked only an optimality certificate.Source: Table 1 · p. 17, §6.2 · p. 18
  • For GKGB, GZR found PNEs in 24/24 Type B, 16/24 Type BC, and 11/24 Type C instances, with average POS values of 1.012, 1.057, and 1.072, respectively.GKGB was the hardest class, and computation became more difficult as the share of adversarial interaction coefficients increased.Source: Table 1 · p. 17, §6.2 · p. 18

6.3 Approximate Equilibria

  • Among 22 regular ISBP instances entering ABS, seven were fully verified; of the other 15, seven lacked a certified lower bound and eight ended at certified widths of 0.013–0.037.The lower-bound calls timed out particularly for item sizes w ≥ 11.Source: §6.3 · p. 18
  • ABS reported certified upper bounds from αUB = 1.009 to 1.081, with most below 1.05; it performed 5–7 bisection iterations per instance.For (7, 6, 8, 11), seven iterations and 3,629 seconds—roughly 518 seconds per call against the 600-second limit—moved the certified upper bound only once, from 1.073 to 1.037.Source: §6.3 · p. 18
  • Of 21 GKGB instances entering ABS, six were fully verified; certified upper bounds ranged from 1.000 to 1.034, while the others lacked certified lower bounds.Five of the six were verified because ABS's larger warm start found an exact PNE missed in Experiment 1, raising known-PNE counts to 20 Type BC and 12 Type C instances out of 24; certified approximate equilibria within a few percent of the exact factor were attainable even without an exact PNE.Source: §6.3 · pp. 18–19

6.4 Comparison with Prior Intersection-Cut Methods

  • All 1,260 instances: GZR found a PNE within 10 minutes (0.066 seconds and 22.9 CEIs on average), while the prior method solved 471 within one hour (2,337 seconds and 41,275 cuts).On the 471 instances both methods solved, the median ratio of prior-method time to GZR time was 139; across all instances, the median cut-count ratio was 1,325. Cut counts are not directly comparable because the methods separate inequalities at different search points.Source: §6.4 · p. 19
  • With a warm start and zero master gap, GZR returned socially optimal PNEs on all 1,260 instances, averaging 0.15 seconds at a price of stability of 1.000.For this family, the social optimum is automatically a PNE; a reference MILP averaged 0.06 seconds versus 0.15 for GZR.Source: §6.4 · p. 19

6.5 Impact of Structural Cuts

  • On regular ISBP, strong VEST cut (9) reduced average runtime from 13.0 to 8.4 seconds (1.55× aggregate speedup) and time-limit terminations from 16 to 9.Because configurations used independent RRR-BRD warm starts, the results do not fully isolate cut effects; they support a family-specific benefit on regular ISBP.Source: §6.5 · pp. 19–20
  • Weak VEST inequalities did not pay off: non-regular ISBP had 0.888 aggregate speedup and 1.001 per-instance ratio, while both NFG metrics favored no cuts (0.923 and 0.865).NFG cycle inequalities are a large static family added a priori and retained whether or not they prune, explaining the overhead.Source: §6.5 · p. 19

7 Conclusion

The conclusion presents conditional equilibrium inequalities and the Generalized Zero-Regret algorithm as tools for optimizing over exact or approximate equilibria, with certified bounds on the best approximation factor. Structural results justify vertex restrictions in specified settings, while experiments demonstrate equilibrium optimization and nonexistence certification alongside computational limits.

7 Conclusion

  • The Generalized Zero-Regret algorithm optimizes a linear objective over exact or approximate equilibria, and bisection certifies bounds on the smallest achievable approximation factor.Its conditional inequalities distinguish feasible from infeasible deviations through activation terms; best-response computations can separate the inequalities.Source: §7 · p. 20
  • Concavity and integrality make each player's cost constant on the minimal face containing an equilibrium strategy, so strict concavity forces vertex strategies.For uniform integer-splittable bin packing, a cost-preserving transformation yields vertex equilibria even without strict concavity.Source: §7 · p. 20
  • Added structure does not automatically improve running times: the strong VEST cut helps on regular bin packing, whereas weaker valid inequalities do not.The conclusion distinguishes inequalities preserving every equilibrium from those preserving only an optimal one, a distinction relevant to certification.Source: §7 · p. 20
  • 16 nonexistence results were certified, including 15 regular bin-packing instances; the authors identify these as the first such computational certificates for these games.The study also reports socially optimal equilibria and nonexistence certification across cost-sharing and knapsack games.Source: §7 · p. 20
  • The one-hot lift limits the capacities and demands that cost-sharing games can handle directly.Reducing the lift and separating rather than enumerating cycle inequalities are identified as future directions.Source: §7 · p. 20

A Omitted Proofs

  • The e-companion section contains proofs omitted from the main text and a remark on equilibrium-preserving restrictions.It records material supporting the restrictions used in Section 6.Source: A Omitted Proofs · p. 22

A.1 Proof of Proposition 1

The proof establishes that conditional equilibrium inequalities hold at lifted approximate equilibria and reject feasible profitable deviations. Under an additional representation hypothesis, linear optimization over the lifted equilibrium set has an optimal vertex.

A.1 Proof of Proposition 1

  • At a lifted α-PNE, feasible deviations satisfy their conditional equilibrium inequalities through the equilibrium condition and affine cost identities.For an infeasible deviation, the right-hand side is at least M_i, bounding the incumbent cost.Source: §A.1 · p. 22
  • Conversely, a feasible profitable deviation from a nonequilibrium profile has zero activation and violates its conditional equilibrium inequality.The deviation's exact affine cost representation makes the inequality fail.Source: §A.1 · pp. 22–23
  • Under the additional representation hypothesis, the lifted equilibrium set is finite and rational, and a linear objective on its nonempty convex hull attains an optimum at a vertex belonging to the set.The convex hull is a rational polytope whose vertices are in the equilibrium set.Source: §A.1 · p. 23

A.2 Proof of Proposition 2

The proof relates best-response checks and equilibrium-preserving restrictions to objective and nonexistence certificates. It also establishes vertex criteria for bounded simplices and derives restrictions on equilibrium strategies from concavity and feasible directions.

A.2 Proof of Proposition 2

  • Accepted α-equilibrium profiles satisfy each player's best-response inequality, and every initial or separated cut preserves all equilibria.Completed master optimization establishes objective optimality; a complete infeasibility search proves nonexistence.Source: §A.2 · p. 23
  • Restrictions preserve nonexistence certificates if they retain an equilibrium whenever one exists, but preserve an optimal objective value only if they retain an optimal equilibrium.Theorem 2 supplies cost-preserving representatives in uniform ISBP; the stated combined restrictions are justified for regular instances with w ≤ u.Source: §A.2 · p. 23

A.3 Vertices of a bounded simplex

  • In a bounded simplex, a feasible strategy is a vertex if and only if it has at most one free coordinate.Two free coordinates allow a feasible perturbation in opposite directions, while the sum constraint fixes the sole possible free coordinate.Source: §A.3 · p. 23

A.4 Proof of Corollary 2

  • For a feasible direction within the minimal face containing an equilibrium strategy, the proof uses local concavity gaps and cost constancy on that face to constrain its free coordinates.It concludes that the relevant coordinate functions are affine; a nonzero free coordinate would contradict the definition used in the proof.Source: §A.4 · p. 24

A.5 Proof of Corollary 3

  • In the bin argument, moving load between two free bins gives a feasible direction that contradicts the coordinate restriction, ruling out the specified shared-bin case.The proof invokes the bounded-simplex vertex criterion after identifying two free coordinates.Source: §A.5 · p. 24

B Instance Generation

  • The instance generators are seeded, and the scripts that produce the instances accompany the code in the repository.Source: B Instance Generation · p. 24

B.1 Integer splittable bin packing

The appendix describes generated instances for integer-splittable bin packing, network formation, and knapsack games, then gives application-specific lifted formulations and conditional inequalities. The encodings represent costs affinely and condition deviations on feasibility, while network cycle inequalities require separation beyond a fixed basis.

B.1 Integer splittable bin packing

  • 842 regular and 842 non-regular bin-packing instances were generated; regular instances use identical item weights, capacities, and costs, while non-regular instances introduce 20% heterogeneity.The regular family enumerates tuples with n from 4 to 10 players and m from n−2 to n+3 bins.Source: §B.1 · p. 24

B.2 Network formation games

  • The network-formation dataset contains 128 layered directed-network instances, varying capacity regime, player count, layer count, and width.Players route integer-splittable flow from a common source to a common sink.Source: §B.2 · p. 25

B.3 Generalized knapsack games

  • The knapsack benchmarks use 1,260 published instances for comparison on identical data, while the bilinear-coefficient extension comprises 72 instances across three types.The latter uses Type B and Type C datasets with shared per-item capacities.Source: §B.3 · p. 25, §B.4 · pp. 25–26

C.1 ISBP formulation

  • The ISBP lifted cost is affine in the y variables and equals the original nonlinear cost on the mixed-integer feasible set, using O(nmuw) binary variables.The formulation size grows with capacities and demands.Source: §C.1 · p. 27

C.2 ISBP CEI formulation

  • For an ISBP deviation, the last term deactivates the inequality precisely when the deviation exceeds residual capacity on a used bin.Source: §C.2 · p. 27

C.3 NFG formulation

  • The network formulation replaces the bin-packing demand equation with node balance, and its affine lifted cost equals the original cost on the mixed-integer feasible set.Source: §C.3 · pp. 27–28

C.4 NFG conditional equilibrium and cycle inequalities

  • A fixed fundamental cycle basis supplies only a subfamily of valid inequalities; enforcing the full condition requires separation on the player's free-edge subgraph.A violating cycle need not be a basis cycle, and basis cycles may contain non-free edges.Source: §C.4 · p. 28

C.5 GKG and GKGB CEI formulations

  • The knapsack formulations linearize binary-strategy feasibility indicators and bilinear interaction terms, while a big-M term deactivates a conditional inequality for an infeasible deviation.For GKGB, a fixed deviation's interaction terms are affine in opponents' master variables.Source: §C.5 · p. 29

D Symmetry and Compatibility in ISBP

The section uses bin and player relabeling to obtain equilibrium representatives with ordered loads and preserved costs. Under specific regular-instance conditions, these reductions can also satisfy vertex and compatibility restrictions while preserving minimum social cost.

Bin-load ordering

  • Relabeling bins within identical-capacity, identical-cost classes yields an α-PNE that preserves every player’s cost.The relabeled profile satisfies the bin-load ordering condition (D.1).Source: D Symmetry and Compatibility in ISBP · p. 29

Player anchoring

  • For regular instances with w ≤ u, relabeling bins and players gives a PNE satisfying (D.1) and (D.2), with individual costs permuted and social cost preserved.These restrictions preserve minimum social cost among exact equilibria, but anchoring need not preserve a player-specific weighted objective; no claim is made for w > u or α > 1.Source: D Symmetry and Compatibility in ISBP · p. 30

Simultaneous compatibility

  • Every PNE of a regular instance with w ≤ u has an equal-social-cost representative satisfying (9), (D.1), and (D.2) simultaneously.The construction first uses vertex strategies with the same individual costs, then applies player anchoring.Source: D Symmetry and Compatibility in ISBP · p. 30
  • Combining the restrictions preserves the minimum social cost among exact equilibria, although player anchoring need not preserve player-specific weighted objectives.The cost vector is only permuted, and no anchoring assertion is used for w > u or α > 1.Source: D Symmetry and Compatibility in ISBP · p. 30

E ABS Certificates

The ABS certificates report verification outcomes for instances where Experiment 1 did not find a PNE, while the VEST comparison summarizes matched-instance averages with and without those cuts. For GKGB, six of 21 cases were verified; the remaining cases did not receive certified lower bounds.

E ABS Certificates

  • Table E.1 reports instance-level ABS results for 22 regular ISBP cases where Experiment 1 found no exact PNE, with Verified evaluated at ε = 10^-2.An αLB = 1.000 entry certifies nonexistence of an exact PNE; Iters includes time-limit calls that advance the interval without contributing a certificate.Source: E ABS Certificates · p. 30, Table E.1 · p. 31
  • Six of 21 GKGB instances were verified: five because the ABS warm start found an exact PNE and one through bisection; the rest obtained no certified lower bound.For the five warm-start cases, αUB = 1 and αLB = 1 is the trivial bound, not a nonexistence certificate.Source: E ABS Certificates · p. 30, Table E.2 · p. 31

F Impact of VEST Cuts: Detailed Comparison

  • Table F.1 compares CEI–GZR with and without VEST cuts using averages over matched instances.Its speedup ratios use unrounded averages and may differ slightly from ratios of the displayed rounded times.Source: Table F.1 · p. 32

G GKG Benchmark Results by Cell

On the published GKG benchmark instances, CEI–GZR found a PNE in every case across all cells. The benchmark reports results by (n, m) cell, while the comparison has limits because the methods were run under different conditions.

GKG benchmark

  • CEI–GZR found a PNE in all 60 instances in every cell, with a maximum time of 0.85 seconds and 172 separated CEIs over the full set.The benchmark uses the instance files of Duguet et al. (2025b).Source: G GKG Benchmark Results by Cell · p. 32, Table G.1 · p. 32
  • The single-threaded mean time was 0.066 seconds, and the setting made little difference in this benchmark.The comparison cited for context reports 0.072 seconds with 16 threads.Source: G GKG Benchmark Results by Cell · p. 32
  • The single-threaded comparison is described as reasonably even on matched dimensions, but solver version and language could not be matched.The methods ran on different machines, and the one-hour limit favors one method; the supplied passage does not identify which one.Source: G GKG Benchmark Results by Cell · p. 32
  • The benchmark groups 60 instances per (n, m) cell and reports #S and Cuts for the prior method versus mean time and CEI for CEI–GZR.The prior method’s #S is instances solved within one hour; CEI–GZR’s mean time is wall-clock seconds under a single-threaded ten-minute limit.Source: Table G.1 · p. 32
Loading 2610.04279v1…