Approximate variational inequalities and equilibria

Giancarlo Bigi, Lorenzo Lampariello, Simone Sagratella and valerio Giuseppe Sasso

Summary

Nash Equilibrium Problems (NEP) are well-suited to capture the interactions between multiple agents in non-cooperative settings, hence they have been largely used in economics, finance, transportation and engineering. They are strictly connected to other mathematical models of variational nature. In particular NEPs can be reformulated as Variational Inequalities (VI) and Minty Variational Inequalities (MVI) under standard assumptions. In turn, fixed point techniques have been extensively exploited to tackle such problems by relying on to the Natural Map problem (NM). Therefore, it is reasonable to analyze these problems together and to investigate their interplay.
As some degree of inexactness arises quite naturally, both in modeling and in algorithms, we find it convenient to consider also approximate versions of the above problems. In fact, approximation is inherent in numerical algorithms when devising practical stopping criteria and, clearly, complexity guarantees are closely related to the magnitude of inexactness. For example, projection type techniques are widely used to solve VIs, where the fulfillment of a NM-related condition provides a valuable stopping criterion. Inexactness on MVI-based stopping criteria and related complexity guarantees arises when relying on averaging techniques on projection iterates or cutting plane type algorithms. On the other hand, introducing inexactness in NEPs amounts to some degree of inaccuracy in each player problem's equilibrium condition.The relations we present are aimed at providing a connection between the inexactness that is inevitably associated to algorithmic procedures commonly used to address NEPs and the corresponding degree of sub-optimality that is achieved in each player's problem.
Theoretical works concerning inexactness on the above problems are mainly focused on existence of approximate solutions and their limit behavior as inexactness vanishes. Some connections between inexact versions of VIs and MVIs have already been investigated: we aim at deepening this analysis, while expanding it to NEPs and NMs as well. Given some level of inexactness in the solution of a problem, we are able to give an estimate of the degree of inexactness up to which any other problem is solved. These estimates depend only on problem-related constants and on the level of inexactness in the solution of the original problem.
The paper is organized into two sections. In Section 2 we introduce exact versions of VI, MVI, NM, NEP. While we review well-known relations, we also obtain some other connections between MVIs and NEPs and MVIs and NMs. In Section 3 we address the inexact versions of the above four problems and study the links between them. Just a few of them follow in the footsteps of the exact case, while others require additional assumptions. Furthermore, the corresponding degrees of inexactness in the relations may turn out to be different.

The original paper is available at http://dx.doi.org/10.1007/s10287-023-00476-w.

My Home Page