USA - 2022
For fundamental contributions to algorithmic game theory, mechanism design, sublinear algorithms and theoretical machine learningPress Release
ACM Grace Murray Hopper Award
USA - 2018
For seminal contributions to the complexity of Nash Equilibria.
Strategic behavior greatly complicates our large-scale technological systems: online advertising, kidney exchanges, cryptocurrencies, sharing-economy applications such as Uber and Airbnb, and social platforms such as Twitter and Facebook. To analyze such complex systems, economists have long relied on the concept of equilibrium, which has been the pillar of economics. For real-life interactions among strategic agents to end in equilibrium, the agents should be able to compute their equilibrium strategies.
Unfortunately, disregarding special cases, equilibrium existence is non-constructive. Famously, Nash's proof used Brouwer's fixed-point theorem, for which no efficient algorithm is known. In itself, this non-constructiveness did not threaten the universal applicability of Nash equilibrium: perhaps, equilibria could be easier to find than fixed-points. Constantinos proved that the computational complexity of finding Nash equilibria is the same as that of finding Brouwer fixed points.
Constantinos's work has had great impact on Computer Science and Economics, and earned 1000 citations and many awards from both fields, including the SIAM Outstanding Paper Prize, the Kalai prize from the Game Theory Society, and the ACM Doctoral Dissertation Award. By challenging equilibrium theory, his work has triggered the on-going reshaping of our understanding of strategic behavior, proving that computation must play an essential role in laying new and firmer foundations for Economics.
ACM Doctoral Dissertation Award
USA - 2008
For his dissertation "The Complexity of Nash Equilibria" nominated by the University of California at Berkeley.