Computing Approximated Nash Equilibria for Integer Programming Games with Nonlinear Payoffs
Aloïs Duguet  1@  , Margarida Carvalho  2@  , Gabriele Dragotto, Sandra Ulrich Ngueveu  3@  
1 : LAAS-CNRS, Toulouse INP, Université fédérale de Toulouse
LAAS-CNRS, Université de Toulouse, Institut National Polytechnique de Toulouse - INPT
2 : Department of Computer Science and Operations Research [Montreal]
Université de Montréal Pavillon André-Aisenstadt CP 6128 succ Centre-Ville Montréal QC H3C 3J7 -  Canada
3 : Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Centre National de la Recherche Scientifique : UPR8001, Institut National Polytechnique [Toulouse]

The Nash equilibrium (NE) is a widely accepted solution concept for non-cooperative games. An NE models the following notion of stability: a profile of strategies is an NE if no players has incentive to unilaterally deviate from it.
When players are allowed to deviate from an NE up to a small quantity $\delta \geq 0$, we obtain a relaxed solution concept of a game:
$\bar{x}$ is a $\delta$-equilibrium of a game $G$ if for each player $p$:
$$\Pi^p(\bar{x}) + \delta \geq \max_{x^p \in X^p} \Pi^p(x^p,\bar{x}^{-p})$$
where $x^{-p}$ denotes the variables $x$ of the players other than $p$, $\Pi^p$ and $X^p$ are the payoff function and the set of feasible strategies for player p, respectively. In other words, $\bar{x}$ is a best response up to $\delta$ for each player $p$. If $\delta=0$, we recover the definition of NE.

The goal of our work is to establish a method for finding effectively $\delta$-equilibria in a subclass of integer programming games (IPG), namely, simultaneous, complete-information and non-cooperative games among $N$ players where each player $p$ solves the optimization problem:

\begin{align} \nonumber
(\mathcal{P}_p) \left\{\begin{array}{ll}
\max_{x^p} &\Pi^p(x^p,x^{-p}) = f^p(x^p) + g^p(x^p,x^{-p}) \\
s.t. &A^p x^p \leq b^p \\
&x^p \in \mathbb{R}^{n_p}_{+} \times \mathbb{N}^{k_p}
\end{array}\right.
\end{align}

\noindent where $f^p$ and $g^p$ are continuous functions, and $A^p$ and $b^p$ are a matrix and a vector of appropriate dimension, respectively.


Personnes connectées : 2 Vie privée
Chargement...