Department of
Applied
Mathematics

Barriers in Algorithmic Game Theory Through the Cryptographic Lens (CSI candidate talk)

Pavel Hubáček

Abstract

The interplay between cryptography, computational complexity, and game theory offers a plethora of interesting problems ranging from the purely theoretical to the very applied. Some examples include: designing cryptographic protocols secure against rational adversaries, applying cryptographic techniques for achieving game theoretical equilibria without trusted mediation, or studying the computational complexity of problems from algorithmic game theory under cryptographic assumptions. In this talk, I will survey the landscape of various research directions in this area with emphasis on the ones that I have explored in my work. I will then present the recent progress on showing lower bounds for the problem of finding Nash equilibria in strategic games.

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 cryptographic assumptions ranging from the weakest (e.g. one-way functions) up to the most structured (e.g. secure code obfuscation).