A branch-and-prune algorithm for discrete Nash equilibrium problems
提出一种分支剪枝算法求解离散纳什均衡问题，利用单个变量的严格凸性剪枝策略集，适用于凸二次和非凸二次目标函数，并通过随机实例验证。
Abstract 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. An algorithmic implementation and numerical tests are presented for randomly generated instances with convex polyhedral strategy sets and convex quadratic as well as non-convex quadratic objective functions.