2018/08/04 by Stefano Coniglio, Nicola Gatti, Coniglio, Stefano +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.1808.01438
openalex publication_date 2018/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The search problem of computing a leader-follower equilibrium has been widely investigated in the scientific literature in, almost exclusively, the single-follower setting. Although the optimistic and textitpessimistic versions of the problem are solved with different methodologies, both cases allow for efficient, polynomial-time algorithms based on linear programming. The situation is different with multiple followers, where results are only sporadic and depend strictly on the nature of the followers' game. In this paper, we investigate the setting of a normal-form game with a single leader and multiple followers who, after observing the leader's commitment, play a Nash equilibrium. The corresponding search problem, both in the optimistic and pessimistic versions, is known to be not in Poly-\textsfAPX unless \textsfP=\textsfNP and exact algorithms are known only for the optimistic case. We focus on the case where the followers play in pure strategies under the assumption of pessimism. After casting this search problem as a \italicpessimistic bilevel programming problem, we show that, with two followers, the problem is \textsfNP-hard and, with three or more followers, it is not in Poly-\textsfAPX unless \textsfP=\textsfNP. We propose a single-level mathematical programming reformulation which calls for the maximisation of a nonconcave quadratic function over an unbounded nonconvex feasible region defined by linear and quadratic constraints. Since, due to admitting a supremum but not a maximum, only a restricted version of this formulation can be solved to optimality with state-of-the-art methods, we propose an exact ad hoc algorithm, which we also embed within a branch-and-bound scheme, capable of computing the supremum of the problem.