A Branch-and-Bound Algorithm for Nonconvex Nash Equilibrium Problems

Summary

This paper introduces a spatial branch-and-bound method for the computation of the set of all \varepsilon-Nash equilibria of continuous box-constrained nonconvex Nash equilibrium problems with an approximation guarantee. Thereby, the existence of \varepsilon-Nash equilibria is not assumed, but the algorithm is also able to detect their absence. We explain appropriate discarding and fathoming techniques, provide a termination proof for a prescribed approximation tolerance, and report our computational experience.