[Model] EquilibriumPoint

[isPANN]

Motivation

EQUILIBRIUM POINT (P234) from Garey & Johnson, A7 AN15. Given a set of variables with finite range sets and a collection of product polynomials (one per variable), determine whether there exists an assignment where each variable simultaneously maximizes its own polynomial — a discrete Nash equilibrium. NP-complete by reduction from 3SAT (Sahni, 1974). Remains NP-complete even when all range sets are binary ({0, 1}). Connects computational complexity to game theory and nonlinear programming.

Associated reduction rules:

• R178: 3SAT → EquilibriumPoint (this model is the target)

Definition

Name: EquilibriumPoint
Reference: Garey & Johnson, Computers and Intractability, A7 AN15

Mathematical definition:

INSTANCE: Set X = {x₁, x₂, …, xₙ} of variables, collection {Fᵢ : 1 ≤ i ≤ n} of product polynomials over X and the integers, and a finite range set Mᵢ ⊆ Z for each variable xᵢ.

A product polynomial is a polynomial expressible as a product of factors, each of which is a polynomial in the variables x₁, …, xₙ with integer coefficients. For example, F = x₁ · (1 − x₂) · (x₃ + 2) is a product of three factors.

QUESTION: Does there exist an assignment (y₁, y₂, …, yₙ) with yᵢ ∈ Mᵢ such that for all 1 ≤ i ≤ n and all y ∈ Mᵢ:

Fᵢ(y₁, …, yᵢ₋₁, yᵢ, yᵢ₊₁, …, yₙ) ≥ Fᵢ(y₁, …, yᵢ₋₁, y, yᵢ₊₁, …, yₙ)?

In game-theoretic terms: each Fᵢ is player i's payoff function, and the assignment is a pure-strategy Nash equilibrium if no player can unilaterally improve their payoff.

This is a satisfaction (feasibility) problem: Value = Or.

Variables

• Count: n (one variable per player)
• Per-variable domain: |Mᵢ| (size of the range set for player i)
• Meaning: yᵢ is the strategy chosen by player i from Mᵢ. The evaluate function checks whether every player's choice is a best response (no unilateral improvement possible).

dims() returns [|M₁|, |M₂|, …, |Mₙ|].

Schema (data type)

Type name: EquilibriumPoint
Variants: none

Field	Type	Description	Getter
polynomials	Vec<Vec<Vec<i64>>>	Product polynomials: polynomials[i] is a list of factors for Fᵢ. Each factor is a vector of coefficients [a₀, a₁, …, aₙ] representing a₀ + a₁x₁ + … + aₙxₙ. Fᵢ is the product of all its factors.	num_players() → self.polynomials.len()
range_sets	Vec<Vec<i64>>	Finite range set Mᵢ ⊆ Z for each variable xᵢ

Problem type: Satisfaction (feasibility)
Value type: Or

Product polynomial representation: Each Fᵢ is stored as a list of linear factors. Factor [a₀, a₁, …, aₙ] represents the polynomial a₀ + a₁·x₁ + … + aₙ·xₙ. The value of Fᵢ at an assignment is the product of all its factors evaluated at that assignment.

Example: F = x₁ · (1 − x₃) is stored as [[0, 1, 0, 0], [1, 0, 0, -1]].

Complexity

• Decision complexity: NP-complete (Sahni, 1974; transformation from 3SAT). Remains NP-complete even for binary range sets Mᵢ = {0, 1}.
• Best known exact algorithm: Brute-force enumeration of all Π|Mᵢ| assignments, checking the equilibrium condition for each. Time O(Π|Mᵢ| · n · max|Mᵢ|).
• Complexity string for declare_variants!: "2^num_players" (worst case with binary range sets)
• Related results: Computing Nash equilibria in continuous games is PPAD-complete (Daskalakis, Goldberg, Papadimitriou, 2009). The discrete version with finite range sets is in NP.
• References:
  • [Sahni, 1974] S. Sahni, "Computationally related problems", SIAM J. Computing 3(4), pp. 262-279, 1974.

Extra Remark

Full book text:

INSTANCE: Set x = {x_1, x_2, . . . , x_n} of variables, collection {F_i: 1 ≤ i ≤ n} of product polynomials over X and the integers, and a finite "range-set" M_i ⊆ Z for 1 ≤ i ≤ n.
QUESTION: Does there exist a sequence y_1, y_2, . . . , y_n of integers, with y_i ∈ M_i, such that for 1 ≤ i ≤ n and all y ∈ M_i,

F_i(y_1, y_2, . . . , y_{i-1}, y_i, y_{i+1}, . . . , y_n) ≥ F_i(y_1, y_2, . . . , y_{i-1}, y, y_{i+1}, . . . , y_n)?

Reference: [Sahni, 1974]. Transformation from 3SAT.
Comment: Remains NP-complete even if M_i = {0,1} for 1 ≤ i ≤ n.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all Π|Mᵢ| assignments; for each, check whether every player's choice is a best response by comparing against all alternatives in Mᵢ.
• It can be solved by reducing to integer programming. (Product polynomials yield nonlinear constraints; not directly expressible as ILP.)
• Other: For binary range sets, reduce to SAT by encoding equilibrium conditions as Boolean constraints.

Example Instance

Input:
n = 3 players, Mᵢ = {0, 1} for all i (binary range sets, 2³ = 8 configurations).

Product polynomials (in factor form):

• F₁ = x₁ · x₂ · x₃ — factors: [[0,1,0,0], [0,0,1,0], [0,0,0,1]]
• F₂ = (1 − x₁) · x₂ — factors: [[1,-1,0,0], [0,0,1,0]]
• F₃ = x₁ · (1 − x₃) — factors: [[0,1,0,0], [1,0,0,-1]]

Analysis of all 8 assignments:

(x₁,x₂,x₃)	F₁	F₂	F₃	P1 BR?	P2 BR?	P3 BR?	Equilibrium?
(0, 0, 0)	0	0	0	✓	✗	✓	No
(0, 0, 1)	0	0	0	✓	✗	✓	No
(0, 1, 0)	0	1	0	✓	✓	✓	Yes ✓
(0, 1, 1)	0	1	0	✗	✓	✓	No
(1, 0, 0)	0	0	1	✓	✓	✓	Yes ✓
(1, 0, 1)	0	0	0	✓	✓	✗	No
(1, 1, 0)	0	0	1	✓	✓	✓	Yes ✓
(1, 1, 1)	1	0	0	✓	✓	✗	No

Best-response analysis for (0, 1, 0):

• Player 1: F₁(0,1,0) = 0, F₁(1,1,0) = 0. Tie (0 ≥ 0). ✓
• Player 2: F₂(0,1,0) = 1, F₂(0,0,0) = 0. Best response (1 ≥ 0). ✓
• Player 3: F₃(0,1,0) = 0, F₃(0,1,1) = 0. Tie (0 ≥ 0). ✓

Answer: Or(true). Three equilibria exist: (0,1,0), (1,0,0), (1,1,0). Five non-equilibria provide negative coverage for round-trip testing.

Expected outcome: Or(true)

Reduction Rule Crossref

• R178: Satisfiability (3SAT) → EquilibriumPoint

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no source reductions planned — risk of orphan node
Non-trivial	✅ Pass	Distinct feasibility semantics (Nash equilibrium condition) unlike any existing problem
Correctness	⚠️ Warn	Sahni 1974 reference verified; minor issues with "product polynomial" terminology in example
Well-written	❌ Fail	Example F_2 is not a product polynomial; Schema lacks ProductPolynomial definition; complexity section has no specific algorithm citation beyond brute-force

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not exist in the codebase — it is a novel addition. The Garey & Johnson classification (A7 AN15) and the Sahni 1974 NP-completeness proof confirm it is a well-studied problem. However:

• No source reductions are planned ("As source: (none known)"). The only planned connection is as a target from 3SAT. Without outgoing reductions, this risks being a leaf node with limited utility in the reduction graph.
• The Motivation section does mention connections to game theory and nonlinear programming, which is reasonable, but could be more specific about what downstream reductions this enables.

Result: Warn — novel and legitimate, but graph connectivity is minimal.

Non-trivial

The equilibrium point problem has a genuinely distinct feasibility constraint: an assignment is feasible iff every player simultaneously maximizes their own payoff given the others' choices. This is structurally different from all existing problems in the codebase (SAT, graph problems, set problems, algebraic problems). No existing problem captures this "simultaneous best-response" semantics.

Result: Pass.

Correctness

Sahni 1974 reference: Verified. The paper "Computationally Related Problems" (SIAM J. Comput., Vol. 3, No. 4, pp. 262–279, 1974) by Sartaj Sahni does prove the equilibrium point problem (called "Problem GT1" in the paper) is P-Complete (= NP-complete) in Theorem 2.4.1 (p. 274). The reduction is from Satisfiability with exactly 3 literals per clause, which is equivalent to 3SAT. This confirms the issue's claim.

Minor concerns:

1. The issue says "reduction from 3SAT" — technically Sahni reduces from "Satisfiability (3 literals/clause)" which is the same thing, so this is acceptable.
2. The complexity section cites brute-force O(2^n · n · max|M_i|) but does not cite a specific better algorithm. This is acceptable for an NP-complete problem with no known faster exact algorithm, but the phrasing could be tighter.
3. The example uses F_2(x_1, x_2) = (1 - x_1)·x_2 + x_1·(1 - x_2) = x_1 + x_2 - 2·x_1·x_2. This is a sum of products, not a single "product polynomial" as required by the G&J definition. A product polynomial should be expressible as a product of polynomial factors. F_2 does not factor into such a form over the integers. This means the example may not be a valid instance of the problem as defined.

Result: Warn — core reference is solid, but the example may not match the formal definition.

Well-written

Issues found:

1. Example inconsistency with definition (Fail): The definition requires "product polynomials" but F_2 in the example is x_1 + x_2 - 2·x_1·x_2, which is NOT a product polynomial. Either the example needs to use actual product polynomials (e.g., F_2 = x_1 · (1 - x_2) could work as a single product), or the definition needs to clarify what "product polynomial" means in G&J's sense. The example as written is a valid game theory instance but may not satisfy the "product polynomial" constraint.

2. Schema incomplete (Fail): The schema references ProductPolynomial as a type but never defines it. What fields does it have? How is a product polynomial represented in memory — as a list of factors, as coefficient arrays, as an expression tree? This is critical for implementation.

3. Complexity section vague: The complexity section discusses brute-force and mentions PPAD-completeness of continuous Nash equilibria (Daskalakis et al. 2009), but this is for a different problem (continuous mixed strategies, not discrete pure strategies). The discrete binary case likely has specialized algorithms — no search was done for better bounds.

4. Missing getter methods for overhead expressions: The Schema does not specify what size fields / getter methods this problem would expose (e.g., num_variables(), num_polynomials(), max_range_size()). These are needed for the declare_variants! macro and any future reduction overhead expressions.

5. Variable domain representation: The issue says range_sets: Vec<Vec<i64>> but the binary case (M_i = {0,1}) is the NP-complete core. The schema should clarify whether the general case or binary case is being implemented, since the general case requires variable-size domains in dims().

Result: Fail.

Recommendations

• Fix the example to use actual product polynomials, or clarify the G&J definition of "product polynomial" (it may include multilinear polynomials that are products of linear factors — verify against the book text).
• Define the ProductPolynomial type explicitly in the Schema section.
• Add size field getters (num_variables, num_polynomials, max_range_size).
• Consider whether to implement the general case or restrict to binary range sets.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but only inbound reduction planned (3SAT); no outbound reductions
Non-trivial	✅ Pass	Distinct feasibility semantics (simultaneous best-response / Nash equilibrium)
Correctness	⚠️ Warn	Sahni 1974 reference verified; example F_2 is not a product polynomial as defined
Well-written	❌ Fail	Example uses non-product-polynomial F_2; ProductPolynomial type undefined; example too small for round-trip testing; missing size field getters; complexity lacks concrete expression

Overall: 1 passed, 2 warnings, 1 failed

Re-check note: Previous check was posted on 2026-03-12. This re-check confirms the same core issues remain. The PoorWritten label from the previous check is still applicable.

---

Usefulness

The problem does not exist in the codebase (pred show EquilibriumPoint fails). The Garey & Johnson classification (A7 AN15) and NP-completeness proof by Sahni (1974) confirm it is a well-studied problem.

However, the issue only plans one inbound reduction (3SAT → EquilibriumPoint) and explicitly states "As source: (none known)." Without outbound reductions this would be a leaf node with limited utility in the reduction graph.

Result: Warn — novel and legitimate, but graph connectivity is minimal.

Non-trivial

The equilibrium point problem has a genuinely distinct feasibility constraint: an assignment is feasible iff every player simultaneously maximizes their own payoff given the others' choices. This "simultaneous best-response" semantics is structurally different from all existing problems in the codebase (SAT variants, graph problems, set problems, algebraic problems).

Result: Pass.

Correctness

Sahni 1974 reference: Verified. The paper "Computationally Related Problems" (SIAM J. Comput., Vol. 3, No. 4, pp. 262–279, 1974) by Sartaj Sahni exists and is already in the project bibliography (docs/paper/references.bib, key sahni1974). The reduction from Satisfiability (3 literals/clause) to Equilibrium Point is a known result, consistent with the issue's claim.

Daskalakis, Goldberg, Papadimitriou 2009 (PPAD-completeness): This reference is for continuous mixed-strategy Nash equilibria, which is a different problem from the discrete pure-strategy equilibrium point. The issue correctly notes this distinction but the mention may confuse readers since it applies to a different problem formulation.

Example correctness: Python verification confirms the example's numerical claims are correct — (1, 0) is indeed the unique equilibrium point among the 4 configurations, and all table entries match.

Product polynomial issue: F_2(x_1, x_2) = x_1 + x_2 − 2·x_1·x_2 is a sum of products, not a product polynomial. A "product polynomial" (as used by Garey & Johnson) should be expressible as a product of polynomial factors. F_2 does not factor into such a form. This means the example may not be a valid instance of the problem as formally defined.

Result: Warn — core reference is solid, but the example may violate the formal definition's constraint on polynomial form.

Well-written

Issues found:

1. Example inconsistency with definition (Fail): The definition requires "product polynomials" but F_2 in the example is x_1 + x_2 − 2·x_1·x_2, which is NOT a product polynomial. Either the example needs to use actual product polynomials, or the definition needs to clarify what "product polynomial" means in Garey & Johnson's sense. The issue should also clarify whether the implementation will enforce the product structure or accept general polynomials.

2. Schema incomplete (Fail): The schema references ProductPolynomial as a type but never defines it. What fields does it have? How is a product polynomial represented in memory — as a list of factors, as coefficient arrays, as an expression tree? This is critical for implementation.

3. Example too small for round-trip testing (Fail): With only n=2 binary variables, there are just 4 total configurations and 1 equilibrium. The skill requires "at least 2 suboptimal feasible solutions in addition to the optimal one" for satisfaction problems (here: at least 2 non-equilibrium configs that could be confused for equilibria). While 3 non-equilibria exist, the instance is so small that a buggy implementation could trivially pass. A larger example (e.g., n=3 or n=4 with non-binary range sets) would be much more effective for catching bugs.

4. Missing size field getters: The schema does not specify what getter methods this problem would expose (e.g., num_variables(), num_polynomials(), max_range_size()). These are needed for declare_variants! and reduction overhead expressions.

5. Complexity lacks concrete expression (Fail): The complexity section discusses brute-force O(2^n · n · max|M_i|) in prose but does not provide a concrete complexity string suitable for declare_variants! (e.g., "2^num_variables * num_variables * max_range_size"). It also references PPAD-completeness (Daskalakis et al. 2009) which applies to a different problem (continuous Nash equilibria).

6. Missing Expected Outcome format: The example provides an analysis table and answer but does not clearly separate the "Expected Outcome" as required by the template — it should state: "Answer: YES. Witness: (x_1, x_2) = (1, 0). Justification: [brief]."

Result: Fail.

Recommendations

• Fix the example to use actual product polynomials for both F_1 and F_2, or clarify the G&J definition and scope the implementation accordingly (e.g., "general multilinear polynomials" if that is the intent).
• Define the ProductPolynomial type explicitly in the Schema with fields and representation.
• Provide a larger example (n ≥ 3) with multiple non-trivial configurations to enable meaningful round-trip testing.
• Add size field getters: num_variables, num_polynomials, max_range_size.
• Add a concrete complexity expression string for declare_variants!.
• Consider whether to implement the general case (arbitrary finite range sets) or restrict to binary (M_i = {0,1}).

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but only inbound reduction planned (3SAT); no outbound reductions
Non-trivial	✅ Pass	Distinct feasibility semantics (simultaneous best-response / Nash equilibrium)
Correctness	⚠️ Warn	Sahni 1974 verified; F_2 is actually a valid product polynomial over binary domain (see below), but issue presentation is misleading
Well-written	❌ Fail	ProductPolynomial type undefined; example too small for round-trip testing; missing size field getters; complexity lacks concrete expression

Overall: 1 passed, 2 warnings, 1 failed

Re-check comparison: Two previous checks (2026-03-12, 2026-03-29) found the same verdict: 1 pass, 2 warnings, 1 fail. The issue body has not been edited since. This re-check confirms the PoorWritten failure still applies. One nuance changed: the "F_2 is not a product polynomial" concern from previous checks is partially resolved — see Correctness section below.

---

Usefulness

The problem does not exist in the codebase (pred show EquilibriumPoint returns "Unknown problem"). The Garey & Johnson classification (A7 AN15) and NP-completeness proof by Sahni (1974) confirm it is a well-studied problem.

However, the issue only plans one inbound reduction (3SAT → EquilibriumPoint) and explicitly states "As source: (none known)." Without outbound reductions this would be a leaf node with limited utility in the reduction graph.

Result: Warn — novel and legitimate, but graph connectivity is minimal.

Non-trivial

The equilibrium point problem has a genuinely distinct feasibility constraint: an assignment is feasible iff every player simultaneously maximizes their own payoff given the others' choices. This "simultaneous best-response" semantics is structurally different from all existing problems in the codebase (SAT variants, graph problems, set problems, algebraic problems).

Result: Pass.

Correctness

Sahni 1974 reference: Verified. The paper "Computationally Related Problems" (SIAM J. Comput., Vol. 3, No. 4, pp. 262–279, 1974) by Sartaj Sahni is already in the project bibliography (docs/paper/references.bib, key sahni1974). The reduction from Satisfiability (3 literals/clause) to Equilibrium Point is consistent with the issue's claim.

Example numerical verification (Python): All table entries are correct. (1, 0) is the unique equilibrium among the 4 configurations.

Product polynomial concern — partially resolved: Previous checks flagged F_2 = x_1 + x_2 − 2·x_1·x_2 as "not a product polynomial." However, over the binary domain (where x² = x), F_2 factors as (x_1 − x_2)² = (x_1 − x_2)·(x_1 − x_2), which IS a product of two linear factors. This was verified numerically for all binary inputs. So F_2 is a valid product polynomial — the issue just presents it in misleading expanded form rather than factored form.

Remaining concern: The issue should present F_2 in its product form F_2 = (x_1 − x_2)·(x_1 − x_2) to make the product polynomial structure explicit.

Result: Warn — core reference is solid; example is numerically correct; the product polynomial form exists but is obscured by the presentation.

Well-written

Issues found (unchanged from previous checks):

1. Schema incomplete (Fail): The schema references ProductPolynomial as a type but never defines it. What fields does it have? How is a product polynomial represented in memory — as a list of factors, as coefficient arrays, as an expression tree? This is critical for implementation.

2. Example too small for round-trip testing (Fail): With only n=2 binary variables, there are just 4 total configurations. The skill requires examples complex enough that a round-trip test can catch implementation bugs. A larger example (n ≥ 3, or non-binary range sets) would be much more effective.

3. Missing size field getters (Fail): The schema does not specify what getter methods this problem would expose (e.g., num_variables(), num_polynomials(), max_range_size()). These are needed for declare_variants! and reduction overhead expressions.

4. Complexity lacks concrete expression (Fail): The complexity section discusses brute-force in prose but does not provide a concrete complexity string suitable for declare_variants! (e.g., "2^num_variables * num_variables * max_range_size").

5. Example F_2 presentation: F_2 should be written in product form (x_1 − x_2)² rather than expanded form to match the "product polynomial" definition.

6. Missing Expected Outcome format: The example provides an analysis table but does not clearly separate the "Expected Outcome" as the template requires (witness + justification).

Result: Fail.

Recommendations

• Define the ProductPolynomial type explicitly in the Schema with fields and representation.
• Present F_2 = (x_1 − x_2)·(x_1 − x_2) in factored product form.
• Provide a larger example (n ≥ 3) with enough structure to enable meaningful round-trip testing.
• Add size field getters: num_variables, num_polynomials, max_range_size.
• Add a concrete complexity expression string for declare_variants!.
• Consider whether to implement the general case (arbitrary finite range sets) or restrict to binary (M_i = {0,1}).

[isPANN]

Fix-issue changelog

• Defined ProductPolynomial type: Vec<Vec<i64>> (list of linear factors, each as coefficient vector)
• Replaced 2-player example with 3-player binary instance (8 configs: 3 equilibria, 5 non-equilibria)
• All polynomials presented in proper product/factor form with storage representation
• Added getter method (num_players())
• Added complexity string 2^num_players for declare_variants!
• Added explicit problem type: satisfaction, Value = Or
• Added dims() mapping: [|M₁|, …, |Mₙ|]
• Included full best-response analysis table
• Noted ILP is not directly applicable (product polynomials yield nonlinear constraints)
• Removed "Unverified" markers from verified content

Applied by /fix-issue.