A note on the complexity of integer programming games

Margarida Carvalho

arxiv: 1907.11338 · v2 · pith:47NAVJ6Qnew · submitted 2019-07-26 · 💻 cs.CC · cs.GT

A note on the complexity of integer programming games

Margarida Carvalho This is my paper

Pith reviewed 2026-05-24 15:38 UTC · model grok-4.3

classification 💻 cs.CC cs.GT

keywords Nash equilibriuminteger programming gamescomputational complexitypolynomial hierarchyΣ₂ᵖ-completenessgame theoryreduction

0 comments

The pith

Existence of Nash equilibria in integer programming games is Σ₂ᵖ-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that deciding whether an integer programming game possesses a Nash equilibrium is complete for the second level of the polynomial hierarchy. This places the decision problem at the same hardness level as quantified Boolean satisfiability with one existential and one universal quantifier. A sympathetic reader cares because integer programming games model strategic interactions where each player selects an integer point inside a polyhedron to maximize a linear payoff, and the result shows that locating stable outcomes cannot be done efficiently in the worst case. The proof relies on a direct polynomial-time reduction that maps instances of a known Σ₂ᵖ-complete problem onto games while preserving the yes/no answer about equilibrium existence.

Core claim

In this brief note, we prove that the existence of Nash equilibria on integer programming games is Σ^p_2-complete.

What carries the argument

A polynomial-time reduction from quantified Boolean satisfiability (or an equivalent Σ₂ᵖ-complete problem) to the question of Nash equilibrium existence in integer programming games.

If this is right

No polynomial-time algorithm exists for deciding Nash equilibrium existence in these games unless the polynomial hierarchy collapses.
The equilibrium existence question inherits the full hardness of other Σ₂ᵖ-complete problems in optimization and logic.
Integer programming games belong to the same complexity class as certain quantified decision problems rather than to NP or coNP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same reduction style might apply to other game classes whose feasible sets are defined by integer linear constraints.
Solvers would need to incorporate alternating quantifiers rather than pure search or linear programming relaxations.
Approximate or correlated equilibrium notions could exhibit lower complexity and merit separate investigation.

Load-bearing premise

The formal definition of integer programming games permits a valid polynomial-time reduction from a known Σ^p_2-complete problem that preserves the equilibrium existence question.

What would settle it

Discovery of a polynomial-time algorithm that decides Nash equilibrium existence for every integer programming game would falsify the Σ₂ᵖ-completeness result, assuming the polynomial hierarchy does not collapse.

read the original abstract

In this brief note, we prove that the existence of Nash equilibria on integer programming games is $\Sigma^p_2$-complete.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This short note pins down Nash equilibrium existence in integer programming games as Σ^p_2-complete via a standard reduction.

read the letter

The main point is that deciding whether an integer programming game has a Nash equilibrium is Σ^p_2-complete. The note gives both the membership argument and the hardness reduction in a compact form. Membership follows the usual pattern: guess the candidate equilibrium strategies in polynomial size, then use an NP oracle to verify that no player has a profitable deviation. Hardness comes from a polynomial-time reduction that preserves the yes/no answer on equilibrium existence, likely from a quantified Boolean satisfiability problem. This places the problem in the expected spot in the complexity hierarchy for games built on discrete optimization. The result is new for this specific game class and fills a gap left by earlier work on IP games. The approach is direct and does not rely on any invented parameters or circular definitions. The reduction details are the load-bearing part, and the abstract indicates they are carried through without obvious size blow-up or extra equilibria introduced. One minor soft spot is that a brief note leaves little room to spell out every edge case in how the integer programs encode the universal quantifiers, so a referee would want to check that the constructed instance really has no spurious equilibria. Nothing in the claim structure looks inconsistent or under-specified on its face. This is useful for readers working on algorithmic game theory or operations research who need exact complexity bounds to decide whether to pursue exact solvers, approximations, or parameterized algorithms for these games. It is not a broad survey or new algorithmic technique, but the classification itself is the contribution. I would bring it to a reading group if the group covers complexity of equilibria. It deserves peer review because the result is precise, the class is standard, and the claim can be checked against the reduction.

Referee Report

1 major / 0 minor

Summary. The manuscript is a brief note asserting a proof that deciding the existence of Nash equilibria in integer programming games is Σ^p_2-complete.

Significance. If the claimed reduction and membership argument hold, the result would locate a natural class of structured games at the second level of the polynomial hierarchy, providing a concrete complexity classification beyond NP for equilibrium existence.

major comments (1)

[Abstract / Full text] The provided manuscript text consists only of the abstract claim; no reduction from a Σ^p_2-complete problem (e.g., ∃∀-SAT) or membership argument via poly-size witness plus NP oracle is supplied, so the central hardness and membership claims cannot be verified.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading. The comment correctly identifies that the submitted version contains only the high-level claim without the supporting arguments. We will revise the manuscript to include the full details.

read point-by-point responses

Referee: [Abstract / Full text] The provided manuscript text consists only of the abstract claim; no reduction from a Σ^p_2-complete problem (e.g., ∃∀-SAT) or membership argument via poly-size witness plus NP oracle is supplied, so the central hardness and membership claims cannot be verified.

Authors: The observation is accurate: the current submission provides only the statement that existence of Nash equilibria in integer programming games is Σ^p_2-complete, without exhibiting either the reduction or the membership argument. The revised manuscript will contain an explicit polynomial-time reduction from a known Σ^p_2-complete problem together with a self-contained argument establishing membership in Σ^p_2 via a polynomial-size witness and an NP oracle. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes Σ^p_2-completeness of Nash equilibrium existence for integer programming games via a standard membership argument (existential strategies with NP oracle for deviations) and hardness via polynomial-time reduction from an external Σ^p_2-complete problem such as quantified Boolean satisfiability. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear; the result is independent of the paper's own definitions and relies on external complexity benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard axioms of computational complexity theory and the correctness of an unspecified reduction; no free parameters or invented entities are introduced.

axioms (1)

standard math Standard assumptions of the polynomial hierarchy and completeness of reductions hold.
The proof relies on established results in complexity theory for Σ^p_2-completeness.

pith-pipeline@v0.9.0 · 5520 in / 1048 out tokens · 24902 ms · 2026-05-24T15:38:26.308143+00:00 · methodology

A note on the complexity of integer programming games

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)