On The Computational Complexity of Games with Uncertainty
摘要
We investigate the computational complexity of several equilibrium problems involving uncertain data in distribution-free models. Primarily, we focus on L/F-equilibrium in multi-leader-follower games and resilient Nash equilibrium-concepts that are traditionally known for their lack of general equilibrium solutions. In the presence of uncertain data, we adopt an approach rooted in robust optimization that considers the robust version of these equilibrium notions. We also present a more general formulation that encompasses existing remedial approaches that address the problem of the lack of solutions for multi-leader-follower games. Building on recent advancements in the computational complexity of generalized quasi-variational inequalities, we prove these equilibrium problems are PPAD-complete under reasonable assumptions.