The ubiquitous concept of Nash Equilibrium enlightens the structure of rational behavior in multi-agent settings. However, as Daskalakis et al. [SIAM Journal on Computing, 39 (1), Jan. 2009] rule, the concept is as helpful as one may compute it efficiently. This work introduces a cutting plane algorithm to compute equilibria for non-simultaneous games where each player's objective is quadratic in its variable and bi-linear in the other players' variables. Starting from a polyhedral relaxation of the original game, we build an increasingly tight sequence of relaxations. As to establish the feasibility of any strategy for the original game, we introduce an ideal enhanced separation oracle, Equilibrium Oracle. This object enables the separation of a point \(\tilde{x}\) from the convexified (closure) of an input set \(\mathcal{X}\). Despite its theoretical soundness, we provide a practical \(\mathcal{V}\)-polyhedral implementation whenever the closure of the convexification of \(\mathcal{X}\) is polyhedral. This algorithmic rationale drops any assumption of finiteness over the players' strategy sets and can (in theory) extended to drop the polyhedral assumption on the convexified strategy sets. We couple a new family of general bounding inequalities -- valid for a player's mixed-strategy set -- with \(\mathcal{V}\)-polyhedral cuts and provide a sharp game-theoretical interpretation for them. We showcase extensive computational results for (i.) Integer Programming Games, where we incorporate well-known families of cutting planes (ii.) Nash Games among Leaders of Stackelberg Games, where the players are leaders of a bilevel game.

Stay tuned! :-)


While waiting for the latest Oracle's computational results, I found out I could have "optimized" my time by playing with Logic Pro X.

Gabriele Dragotto Β· L'Amour Toujours est un test πŸ‘€
Take me back