A note on the complexity of integer programming games
Margarida Carvalho
cs.CC cs.GT 91-XX, 03D15

Image Enhancement by Recurrently-trained Super-resolution Network
    SAEM Park

Seoul National University, Seoul, Korea

LG Eletronics, Korea

parksaem2@snu.ac.kr






Nojun Kwak

Seoul National University, Seoul, Korea

nojunk@snu.ac.kr

    December 30, 2023
==============================================================================================================================================================================




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









§ INTRODUCTION


Integer programming games (s) model games in which there is a finite set of players M={ 1,2 …, m } and   each player p ∈ M has a set of feasible strategies X^p given by  lattice points inside a polytopes described  by  finite systems  of  linear  inequalities. Therefore, each players aims to solve 

    max_x^p ∈ X^P  Π^p(x^p,x^-p),

where x^p is player p's strategy and x^-p is the vector of strategies of all players, except player p.

A vector x ∈∏_p ∈ M X^p is called a pure profile of strategies.  If a pure profile of strategies x solves the optimization problem (<ref>) for all players, it is called pure Nash equilibrium.  A game may fail to have pure equilibria and, therefore, a broader  solution concept for a game must be introduced, the Nash equilibria. Under this concept, each player can assign probabilities to her pure strategies.  Let Δ^p denote the space of Borel probability measures over X^p and Δ = ∏_p ∈ MΔ^p. Each player p's expected payoff for a profile of strategies σ∈Δ is
 
    Π^p(σ) = ∫_X^pΠ^p(x^p,x^-p) d σ.

 A Nash equilibrium () is a profile of strategies σ∈Δ such that

    Π^p(σ)  ≥Π^p(x^p, σ^-p),      ∀ p ∈ M     ∀ x^p ∈ X^p .
 



 


In <cit.>, the authors discuss the existence of Nash equilibria for integer programming games. It is proven that the existence of pure Nash equilibria for s is  Σ^p_2-complete and that even the existence of Nash equilibria is  Σ^p_2-complete. However, the later proof seems incomplete in the “proof of only if”, since it does not support  why we can conclude that the leader cannot guarantee a payoff of 1. In the following section, we provide a correct proof using a completely new reduction. 



§ COMPUTATIONAL COMPLEXITY

In what follows, we show that even in the simplest case, linear integer programming games with two players, the existence of Nash equilibria is a  Σ^p_2-complete problem.


The problem of deciding if an  has a Nash equilibrium is Σ^p_2-complete problem.



The proof that this decision problem belongs to  Σ^p_2 can be found in <cit.>.

It remains to show that it is  Σ^p_2-hard. We will reduce the following to  Σ^p_2-complete problem to it (see<cit.>):







Problem: 




INSTANCE  A sequence q_1,q_2,…,q_k of positive integers; two positive integers R and r with r≤ k.




QUESTION Does there exist an integer S with R≤ S<R+2^r such that none of the
subsets I⊆{1,…,k} satisfies ∑_i∈ Iq_i=S?


Our reduction starts from an instance of . We construct the following instance of 


  * The game has two players, M={ Z, W }.

  * Player Z solves


  max_z        1/2z_0+∑_i=1^k q_i z_i + Qz(2w-z)

  s.t.       1/2z_0+∑_i=1^k q_i z_i ≤z

        z_0, z_1, …, z_k ∈{0,1 }

        R ≤z ≤R+2^r-1, z ∈𝐍




Add binary variables y ∈{ 0,1}^r and make z =R + ∑_i=0^r-1 2^i y_i. Note that z^2= Rz+∑_i=0^r-1 2^i y_iz. Thus, replace y_iz by h_i and add the respective McCormick constraints <cit.>. In this way, we can equivalently linearize the previous problem:


  max_z,y,h        1/2z_0+∑_i=1^k q_i z_i +2 Qzw-QRz-∑_i=0^r-1 2^i  h_i

  s.t.       1/2z_0+∑_i=1^k q_i z_i ≤z

        z_0, z_1, …, z_k ∈{0,1 }

        R ≤z ≤R+2^r-1, z ∈𝐍

        z = R+ ∑_i=0^r-1 2^i y_i

        y_0, y_1, …, y_r-1 ∈{0,1 }

        h_i ≥0    i=0,…,r-1

        h_i ≥z+(R+2^r-1)(y_i -1)     i=0,…,r-1 

        h_i ≤z+R(y_i-1)     i=0,…,r-1

        h_i ≤(R+2^r-1)y_i     i=0,…,r-1



For sake of simplicity, we consider the quadratic formulation (<ref>). The linearization above serves the purpose of showing that the proof is valid even under linear utility functions for the players. 

  * Player W solves 


  max_w        (1-z_0)w_0

  s.t.        R ≤w ≤R+2^r-1, z ∈𝐍

     w_0 ∈𝐑







(Proof of if).  Assume that the  instance has answer YES. Then, there is  R≤ S<R+2^r  such that for all subsets I⊆{1,…,k}, we have ∑_i∈ Iq_i≠ S. Let player W strategy be w^*=S and w_0^*=0. Note that the term Qz(2w-z) in player Z's utility is dominant and attains a maximum when z is equal to w. Thus, make z^*=w^*=S and since ∑_i=1^k q_i z_i is at most S-1, make z_0^*=1. Choose z_i^* such that the remaining utility of player Z is maximized. By construction, player Z is selecting her best response to (w^*,w_0^*). Sinze z_0^*=1, then player W is also selecting an optimal strategy. Therefore, we can conclude that there is an equilibrium.


(Proof of only if). Assume that the  instances has answer NO. Then, for all R≤ S<R+2^r, there is a subset I⊆{1,…,k} such that ∑_i∈ Iq_i=S. In this case, player Z will always make z_0=0 which gives incentive for player W to choose w_0 as  large as possible. Since w_0 has no upper bound, there is no equilibrium for the game.




§ ACKNOWLEDGEMENTS


The authors wish to thank Sriram Sankaranarayanan for bringing to our attention the incompleteness of our previous proof in <cit.>. 

We wish acknowledge the support of the Institut de valorisation des données and  the Canadian Natural Sciences and Engineering Research Council  under the discovery grants program.

unsrt  





1


Carvalho2018
Margarida Carvalho,  Andrea Lodi and João Pedro Pedroso.
Existence of Nash Equilibria on Integer Programming Games.
In Congress of APDIO 2017, the Portuguese Operational Research Society, pages 11–23. Springer International Publishing, 2018.


EgWo2012
Christian Eggermont and Gerhard J. Woeginger. 
Motion planning with pulley, rope, and baskets.
In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS'2012), 
Leibniz International Proceedings in Informatics 14, 374–383. 2012.

McCormick76
Garth P. McCormick.
Computability of global solutions to factorable nonconvex programs:
  Part I - convex underestimating problems.
Mathematical Programming, 10, pages 147–175, 1976.



