pith. sign in

arxiv: 2604.22495 · v1 · submitted 2026-04-24 · 🧮 math.OC · cs.GT

On the equivalence of semidefinite programming and zero-sum semidefinite games

Jesse Elliott , Constantin Ickstadt , Thorsten Theobald , Elias Tsigaridas This is my paper

Pith reviewed 2026-05-08 11:04 UTC · model grok-4.3

classification 🧮 math.OC cs.GT
keywords semidefinite programmingzero-sum gamesdualityconstraint qualificationequivalencelinear programminginfeasibility certificates
0
0 comments X

The pith

Under a natural constraint qualification, solving a semidefinite program is equivalent to finding optimal strategies in an associated zero-sum semidefinite game.

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

The paper establishes that, when either strongly optimal primal-dual solutions exist or a strictly unbounded direction is present, the task of solving a semidefinite program reduces exactly to computing optimal strategies in a specially constructed zero-sum game with semidefinite strategy sets. This result completes an earlier incomplete reduction for semidefinite programs, mirroring how linear programs reduce to bimatrix games. A reader would care because the game value directly certifies optimality when it is zero and supplies an infeasibility certificate otherwise, linking optimization duality to game equilibria in a concrete way.

Core claim

Under the stated constraint qualification, computing the solution of a semidefinite program is equivalent to finding optimal strategies in an associated zero-sum semidefinite game. The proof uses a semidefinite generalization of von Stengel's extension of Dantzig's construction, techniques for general duality phenomena, and an explicit bound on solution coordinates. The game value is zero precisely when strongly optimal primal-dual solutions exist; otherwise the optimal strategies yield a certificate of primal or dual infeasibility.

What carries the argument

The associated zero-sum semidefinite game constructed from the primal-dual SDP pair, whose optimal strategies recover the program solutions precisely when the constraint qualification holds.

If this is right

  • The game value equals zero exactly when strongly optimal primal-dual solutions exist for the semidefinite program.
  • Optimal strategies in the game supply an explicit infeasibility certificate for the primal or dual program when the value is nonzero.
  • An explicit bound on the coordinates of semidefinite program solutions follows from the game construction.
  • The reduction covers all programs meeting the constraint qualification, including those outside the scope of the prior incomplete result.

Where Pith is reading between the lines

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

  • The explicit coordinate bound could support finite-precision algorithms that guarantee exact recovery of solutions.
  • Game-solving methods might be adapted to produce the certificates for SDP feasibility without solving the program directly.
  • The same style of reduction may apply to other conic programs where duality gaps can occur.
  • The game formulation unifies the treatment of bounded and unbounded semidefinite programs under one equilibrium concept.

Load-bearing premise

The semidefinite program must satisfy the natural constraint qualification of either having strongly optimal primal-dual solutions or possessing a strictly unbounded direction.

What would settle it

A concrete semidefinite program violating the constraint qualification for which the constructed game yields strategy values that do not match the program's optimal or infeasible status.

read the original abstract

By results of Dantzig (1951) and Adler (2013), computing the optimal solutions of a linear program is equivalent to finding optimal strategies in zero-sum bimatrix games. Dantzig's original result was incomplete, in the sense that the reduction of a linear program to a zero-sum game did not work for all possible linear programs. We show that, under a natural constraint qualification requiring either the existence of strongly optimal primal-dual solutions or of a strictly unbounded direction, computing the solution of a semidefinite program is equivalent to finding optimal strategies in an associated zero-sum semidefinite game. Our work builds upon Ickstadt, Theobald, and Tsigaridas (2024), where, similar to Dantzig's work, the proposed reduction cannot handle a certain subclass of semidefinite programs. Our main proof ingredients for the equivalence result include: (i) a semidefinite generalization of von Stengel's (2023) extension of Dantzig's construction; (ii) techniques for handling more general duality phenomena in the semidefinite setting; and (iii) an explicit bound for the (coordinates) of the solutions of a semidefinite program. As a by-product, the game value provides a certificate: it is zero if and only if strongly optimal solutions exist, and otherwise optimal strategies yield an infeasibility certificate for the primal or dual program.

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.

Referee Report

0 major / 2 minor

Summary. The paper shows that, under a natural constraint qualification requiring either the existence of strongly optimal primal-dual solutions or a strictly unbounded direction, computing the solution of a semidefinite program is equivalent to finding optimal strategies in an associated zero-sum semidefinite game. This extends Dantzig-Adler type results from linear programming to SDPs, completing the incomplete reduction from Ickstadt, Theobald, and Tsigaridas (2024) via three ingredients: an SDP generalization of von Stengel's construction, techniques for general duality phenomena, and an explicit bound on the coordinates of SDP solutions. The game value serves as a certificate that is zero precisely when strongly optimal solutions exist, and otherwise yields an infeasibility certificate.

Significance. If the conditional equivalence holds, the result provides a game-theoretic interpretation of SDP solving that parallels the classical LP-bimatrix game equivalence, potentially enabling new algorithmic approaches and certificates. The explicit coordinate bound and SDP-specific duality handling address the precise gap left by the 2024 predecessor, strengthening the contribution. The certificate byproduct is a concrete practical benefit for feasibility verification.

minor comments (2)
  1. The abstract lists the three proof ingredients clearly, but the introduction would benefit from a numbered outline of how each ingredient is used in the main proof to improve readability.
  2. Notation for the zero-sum semidefinite game (e.g., the payoff operator and strategy sets) should be introduced with a small comparison table to the classical bimatrix case to help readers unfamiliar with the SDP setting.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of our contributions, and the recommendation for minor revision. We appreciate the recognition that our work completes the reduction left open by Ickstadt, Theobald, and Tsigaridas (2024) and provides a practical certificate via the game value.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation establishes conditional equivalence between SDP solutions and zero-sum SDP games under the stated constraint qualification by supplying three independent ingredients: an SDP lift of von Stengel's 2023 construction, SDP-specific duality techniques, and an explicit coordinate bound. The reference to the authors' own 2024 predecessor is acknowledged as incomplete but is not load-bearing, since the current manuscript supplies the missing elements rather than deriving the result from the prior citation alone. No self-definitional reductions, fitted inputs renamed as predictions, ansatz smuggling, or renaming of known results occur in the proof chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard convex-optimization duality and game-theory existence theorems without introducing new free parameters or postulated entities.

axioms (2)
  • standard math Standard SDP duality theorems (strong duality under Slater-type conditions)
    Invoked to relate primal and dual SDPs and to define strong optimality.
  • standard math Existence of optimal strategies in finite zero-sum games
    Used to guarantee that the constructed game possesses a value and optimal strategies.

pith-pipeline@v0.9.0 · 5562 in / 1372 out tokens · 61547 ms · 2026-05-08T11:04:56.654361+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    I. Adler. The equivalence of linear programs and zero-sum games.Internat. J. Game Theory, 42(1):165–177, 2013

    work page 2013

  2. [2]

    Blekherman, P

    G. Blekherman, P. A. Parrilo, and R. R. Thomas, editors.Semidefinite optimization and convex algebraic geometry, volume 13 ofMOS-SIAM Series on Optimization. SIAM, Philadelphia, 2012

    work page 2012

  3. [3]

    Boyd and L

    S. Boyd and L. Vandenberghe.Convex optimization. Cambridge University Press, Cambridge, 2004

    work page 2004

  4. [4]

    Brooks and P

    B. Brooks and P. J. Reny. A canonical game – 75 years in the making – showing the equivalence of matrix games and linear programming.Econ. Theory. Bull., 1:171–180, 2023

    work page 2023

  5. [5]

    G. B. Dantzig. A proof of the equivalence of the programming problem and the game problem. In T. Koopmans, editor,Activity Analysis of Production and Allocation, volume 13 ofCowles Commission Monographs. John Wiley & Sons, 1951

    work page 1951

  6. [6]

    N. Dimou. On the equivalence of zero-sum games and conic programs.Math. Oper. Res., ahead of print, 2026

    work page 2026

  7. [7]

    D¨ ur, B

    M. D¨ ur, B. Jargalsaikhan, and G. Still. Genericity results in linear conic programming—a tour d’horizon.Math. Oper. Res., 42(1):77–94, 2017

    work page 2017

  8. [8]

    Emiris, B

    I. Emiris, B. Mourrain, and E. Tsigaridas. Separation bounds for polynomial systems.J. Sym- bolic Comput., 101:128–151, 2020

    work page 2020

  9. [9]

    M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.J. Assoc. Comput. Mach., 42(6):1115– 1145, 1995

    work page 1995

  10. [10]

    Gutoski and J

    G. Gutoski and J. Watrous. Toward a general theory of quantum games. InProc. 39th Annual ACM Symp. Theory of Computing, pages 565–574, 2007

    work page 2007

  11. [11]

    Ickstadt, T

    C. Ickstadt, T. Theobald, and E. Tsigaridas. Semidefinite games.Internat. J. Game Theory, 53:827–857, 2024

    work page 2024

  12. [12]

    Ickstadt, T

    C. Ickstadt, T. Theobald, E. Tsigaridas, and A. Varvitsiotis. Nash equilibria in semidefinite games and Lemke-Howson paths. Preprint, arXiv:2506.11940, 2025

    work page arXiv 2025

  13. [13]

    Ickstadt, T

    C. Ickstadt, T. Theobald, E. Tsigaridas, and A. Varvitsiotis. Semidefinite network games: mul- tiplayer minimax and complementarity problems.J. Optim. Theory Applic., 2026

    work page 2026

  14. [14]

    Lov´ asz

    L. Lov´ asz. On the Shannon capacity of a graph.IEEE Trans. Inform. Theory, 25(1):1–7, 1979

    work page 1979

  15. [15]

    G. Pataki. The geometry of semidefinite programming. InHandbook of Semidefinite Program- ming: Theory, Algorithms, and Applications, pages 29–65. Springer, 2000

    work page 2000

  16. [16]

    G. Pataki. Bad semidefinite programs: They all look the same.SIAM J. Optim., 27(1):146–172, 2017

    work page 2017

  17. [17]

    Pataki and A

    G. Pataki and A. Touzov. How do exponential size solutions arise in semidefinite programming? SIAM J. Optim., 34(1):977–1005, 2024

    work page 2024

  18. [18]

    Porkolab and L

    L. Porkolab and L. Khachiyan. On the complexity of semidefinite programs.J. Global Optim., 10(4):351–365, 1997

    work page 1997

  19. [19]

    M. V. Ramana. An exact duality theory for semidefinite programming and its complexity im- plications.Math. Program., 77(1):129–162, 1997

    work page 1997

  20. [20]

    Theobald.Real algebraic geometry and optimization, volume 241 ofGraduate Studies Math

    T. Theobald.Real algebraic geometry and optimization, volume 241 ofGraduate Studies Math. Amer. Math. Soc., 2024

    work page 2024

  21. [21]

    Tun¸ cel.Polyhedral and semidefinite programming methods in combinatorial optimization

    L. Tun¸ cel.Polyhedral and semidefinite programming methods in combinatorial optimization. Amer. Math. Soc., 2016

    work page 2016

  22. [22]

    von Neumann

    J. von Neumann. A model of general economic equilibrium.The Review of Economic Studies, 13(1):1–9, 1945. 24 J. ELLIOTT, C. ICKSTADT, T. THEOBALD, AND E. TSIGARIDAS

    work page 1945

  23. [23]

    von Stengel

    B. von Stengel. Computing equilibria for two-person games.Math. of Oper. Res., 49(2):1091– 1108, 2024

    work page 2024

  24. [24]

    Watrous.The theory of quantum information

    J. Watrous.The theory of quantum information. Cambridge University Press, 2018

    work page 2018

  25. [25]

    Wolkowicz, R

    H. Wolkowicz, R. Saigal, and L. Vandenberghe, editors.Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, volume 27 ofInternational Series in Operations Research &Management Science. Kluwer Academic Publishers, Boston, 2000. Jesse Elliott: Sorbonne Universit´e and Inria Paris. IMJ-PRG, 4 place Jussieu, 75005 Paris, France Email add...

    work page 2000