A branch-and-prune algorithm for discrete Nash equilibrium problems

We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player's strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player's objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. This results in a synchronous branching and pruning method. Numerical tests are performed on randomly generated instances with convex polyhedral strategy sets and convex quadratic as well as non-convex quadratic objective functions.

Citation

Optimization Online, Preprint ID 2022-03-8836, 2022.

Article

Download

View A branch-and-prune algorithm for discrete Nash equilibrium problems