Objectives
Many noncooperative multi-agent systems can be modeled as generalized Nash equilibrium problems (GNEPs) with mixed-integer strategy sets, i.e., games in which the players have integrality constraints. Nevertheless in the literature there is a lack of general algorithms to compute solutions of mixed-integer GNEPs. We develop new enumerative and best-response solution methods for mixed-integer GNEPs, and we apply them to compute equilibria of noncooperative games from machine learning and transportation problems.
Methodology
The enumerative solution methods we consider include both branch-and-bound methods based on merit functions for the mixed-integer GNEP, and branch-and-prune ones that exploit the concept of dominance to make effective cuts. Moreover, we intend to define suitable assumptions based on monotonicity and metric regularity properties in order to obtain variants of these enumerative procedures to compute the whole equilibrium set and to perform a general equilibrium selection for the game.
As a second line of research, and besides potential and 2-groups partitionable games, we want to define new classes of mixed-integer problems, namely P-upsilon games, for which player best-response methods converge to equilibria, and thus solutions exist.
Expected results
We want to develop new theoretical results in order to improve the literature on mixed-integer GNEPs.
We expect to develop new powerful enumerative and best-response algorithms for the solution of mixed-integer GNEPs. Suitable variants of these methods, such as the equilibrium selection algorithm, will be employed to tackle important applications in machine learning and transportation problems. Specifically, we intend to define and solve new generalizations of the multi-agent models stemmed from generative adversarial networks.
Moreover we want to study other fundamental applications of our games, i.e., noncooperative fixed charge transportation problems.
Our research starts from the results obtained for Nash equilibrium problems with completely discrete strategy sets, see [1]. We plan to extend these theoretical results in order to give an important contribution to the field of generalized Nash equilibrium problems (GNEPs) with mixed integer strategy sets. It is widely acknowledged that GNEPs are much more complex problems rather than simple Nash games [2].
We point out that general methods to solve mixed integer GNEPs have not been proposed in the literature. Therefore, now, it is not clear how it is possible to compute equilibria of many non-cooperative game models that are designed so that their variables represent indivisible quantities. With our research we want to fill this gap. Moreover, in order to define enumerative methods for computing the whole euilibrium set, or equilibrium selection algorithms, we intend to define some necessary conditions for optimality and we want to show that, under mild assumptions, the equilibrium set of the mixed-integer GNEP is finite. Furthermore, dealing with the continuous relaxation of the GNEP, we want to show how the classical reformulations of the continuous relaxation, like the quasi variational inequality or the gap function, cannot be directly used to solve the mixed-integer GNEP. These facts are in contrast with what happens for classical optimization problems. These results constitute the first theoretical fundations on mixed-integer GNEPs.
Our study on P-upsilon games (see [3] for a formal definition of these problems) will be useful to define new classes of mixed-integer GNEPs that can be considered as "easy problems". Indeed, for these problems solutions can be computed by simply using best-response algorithms that are much faster than enumerative ones.
Our new solution methods will be used to tackle different generalizations of Nash games stemmed from machine learning applications. Specifically, the generalizations of the generative adversarial networks (GANs) (see [4]) will give the possibility to consider more complex formulations for the optimization problems faced by the agents. For example the problem of the so called discriminator agent could be strengthen to consider also different quality standards.
Finally, the game-theoretic extension of the noncooperative fixed charge transportation problem we introduce (see [5] for some references), will be presented and studied intensively. In particular, we want to prove existence of Nash equilibria for all the models and suggest numerical methods for their computation. We underline that these games are really important in practice because they can be interpreted from both, a descriptive and a normative point of view. But, so far, no solution methods have been proposed in the literature.
[1] S. Sagratella. Computing all solutions of Nash equilibrium problems with discrete strategy sets.
SIAM JOURNAL ON OPTIMIZATION, 26 (2016), pp.
2190-2218.
[2] F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Ann. Oper. Res., 175 (2010), pp. 177-211.
[3] G. Scutari, et al. Real and complex monotone communication games. IEEE Transactions on Information Theory 60.7 (2014), pp. 4197-4231.
[4] I. Goodfellow, et al. Generative adversarial nets. Advances in neural information processing systems. 2014.
[5] O. Stein, N. Sudermann-Merx. The noncooperative transportation problem and linear generalized Nash games. European Journal of Operational Research 266.2 (2018), pp. 543-553.