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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On The Computational Complexity of Games with Uncertainty

  • Bruce M. Kapron,
  • Koosha Samieefar

摘要

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.