The central result in game theory due to Nash ensures that every finite strategic game has an equilibrium. However, all the known proofs of the Nash theorem are non-constructive and, as of today, there is no polynomial time algorithm for finding a Nash equilibrium. Some recent works have tried to explain this status by showing lower bounds for finding Nash equilibria under strong cryptographic assumptions such as the notion of secure code obfuscation. These initial results leave open the natural question of establishing similar lower bounds under weaker and more well-believed assumptions.
In my talk, I will describe our recent results that highlight a curious relation between the Nash equilibrium problem, as well as other search problems with guaranteed solutions, and the hierarchy of general cryptographic assumptions ranging from the weakest (e.g. one-way functions) up to the most structured (e.g. secure code obfuscation).
Based on joint works with Moni Naor and Eylon Yogev.
Pavel Hubáček, IDC Herzliya