Analysis of a parametric quadratic game

25 Views Asked by At

I am solving a game theory problem for N players. At each step, each player solves a projection-based gradient descent $\operatorname{proj}_{X}\left(x_i^{(k)}-\eta F\left(x_{i}^{(k)}\right)\right)$ corresponding to its optimization problem

$$ J_{\lambda}(x_{-i}) := \begin{array}{ll}\underset{\mathrm{x}_i}{\operatorname{minimize}} & x_i^{\top}Ax_i + c(\lambda)^{\top}x_i + \sum_{j = 0, j\neq i}^{N} x_{j}Bx_{i}\\ \text { subject to } & Hx_i \le h , x_i \ge 0\end{array} $$ where $\lambda \in \mathbb{R}$ is a parameter and $x_{i} \in \mathbb{R}^{n+m}$ is the decision variable (consisting of strategy space $\mathbb{R}^{n}$ and auxiliary variable space $\mathbb{R}^{m}$). Here $F$ is the Jacobian matrix of the objective function and $X$ is the constraints $\{x_i \mid H x_i \le h, x_i \ge 0\}$. When $\lambda = 0$ or $\lambda = 1$ the optimization can be equivalently reformulated to an optimization without auxiliary variables, i.e. merely depends on the strategy space. For example when $\lambda = 0$, $$ J_{0}(x_{-i}) := \begin{array}{ll}\underset{\mathrm{u}_i}{\operatorname{minimize}} & u_i^{\top}A_0u_i + c_{0}^{\top}u_i + \sum_{j = 0, j\neq i}^{N} u_{j}B_0u_{i}\\ \text { subject to } & H_0u_i \le h_0 , u_i \ge 0\end{array} $$ where $u_i \in \mathbb{R}^{n}$ is player i's strategy.

Here since $A$ is not positive definite, I couldn't use strong monotonicity to analyse the convergence to the Nash equilibrium. However, I observed: (1) when $\lambda = 0$ or $1$, I know the quadratic matrix is positive definite in the equivalently reformulated optimization; hence a strongly monotone operator is acquired. (2) With the same $\eta$, the projection-based algorithm shows for some $\lambda$, the strategy $u:= [u_1 \cdots u_N]$ converges faster to an "equilibrium" point $u^{*}_{\lambda}$ than $\lambda = 0$ and $1$, where the equilibrium point $u^{*}_{\lambda}$ is close to $u^{*}_{0}$ and $u^{*}_{1}$.

Question: 1. How should I analyse this parametric quadratic game? 2. How should I show the continuity of the equilibrium points/convergence rate (if exist) corresponding to $\lambda$.

Any hints would be appreciated! Thanks in advance.