ӣ��Ӱ��

Topic

Hardness and Totality of Problems Related to Nash Equilibrium

Department of Computer Science

Date & location

• Thursday, December 4, 2025

• 9:30 A.M.

• Virtual Defence

Reviewers

Supervisory Committee

• Dr. Bruce Kapron, Department of Computer Science, ӣ��Ӱ�� (Supervisor)

• Dr. Sajin Koroth, Department of Computer Science, UVic (Member)

• Dr. David Scoones, Department of Economics, UVic (Outside Member) 

External Examiner

• Dr. Margarida Carvalho, Department of Computer Science and Operations Research, Université de Montréal 

Chair of Oral Examination

• Dr. Ke Xu, Department of Economics, UVic

   

Abstract

We investigate the computational complexity of various equilibrium problems and their applications—a central topic in algorithmic game theory. While the existence of solutions for classical equilibrium notions, such as generalized Nash equilibria and multi-leader–follower games with convex constraints, is well established via foundational fixed-point theorems, the complexity of computing such equilibria remained largely unresolved, especially in settings involving uncertainty. In particular, we study the computational complexity of approximating both Nash and generalized Nash equilibria in more complex formats of games under general convexity assumptions, encompassing broad settings with both differentiable and non-differentiable utility functions. To be specific, building on and extending the computational framework for Kakutani’s fixed-point theorem, we establish PPAD completeness results for several classes of variational inequality problems and extend the results to multi-leader–follower games and resilient equilibria, and some other relevant definitions in games with or without uncertainty. Moreover, we propose a family of natural, yet specific, non-convex constraints—termed strategic constraints—and investigate their computational complexity as well as their potential applications.