A note on the complexity of integer programming games

2019/07/26 by Margarida Carvalho, Carvalho, Margarida
Computer Science · Engineering · #03D15 #91-XX #Advanced Graph Theory Research #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.1907.11338

openalex publication_date 2019/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems

Related

• Nash-equilibria and N-fold integer programming
• Integer Programming Games: A Gentle Computational Overview
• The ZERO Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming
• Computing Approximate Nash Equilibria for Integer Programming Games
• The Complexity of Computing a Nash Equilibrium