The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations

Author name not available (Why is that?)

Publication date: 10 November 2021

Abstract: We introduce the Cut-and-Play, an efficient algorithm for computing equilibria in simultaneous non-cooperative games where players solve nonconvex and possibly unbounded optimization problems. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the original game and refines them with techniques from integer programming, for instance, cutting planes and branching operations. We test our algorithm on two families of challenging nonconvex games involving discrete decisions and bilevel programs, and we empirically demonstrate that it efficiently computes equilibria and outperforms existing game-specific algorithms.

Has companion code repository: https://github.com/ds4dm/zero

This page was built for publication: The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382693)