I am an Associate Professor at MIT's Electrical Engineering and Computer Science department, a member of CSAIL, and affiliated with IDSS, LIDS and ORC.
Prior to joining MIT's faculty I was a postdoctoral researcher in Jennifer Chayes's group at Microsoft Research, New England. And before that I spent four wonderful years at UC Berkeley's theory of computation group advised by Christos Papadimitriou. I did my undergraduate studies in Greece at the National Technical University of Athens.
Research Interests: Algorithms, Game Theory, Learning, Statistics
MIT's Theory of Computation Colloquium
Short Bio
Current students: Christos Tzamos, Gautam Kamath, Manolis Zampetakis, Nishanth Dikkala
Graduated students:
Yang Cai (McGill CS Assistant Professor)
Matt Weinberg (Princeton CS Assistant Professor)
Alan Deckelbaum (Renaissance Technologies)
Postdocs:
Nick Gravin
Nima Haghpanah (Penn State Economics Assistant Professor)
[Awards]
[Press Coverage, Public Lectures]
[Research Highlights, Slides, Videos]
My research focuses on algorithms, game theory, probability, learning and statistics. See publications (all online).
Complexity of Equilibria: My Ph.D. research examined whether rational, self-interested individuals can arrive, through their interactions, at a state where no single one of them would be better off switching strategies unless others did so as well. Such a state is called a Nash equilibrium, in honor of John Nash, who showed that such a state always exists, and is traditionally used in Game Theory as a mathematical way of predicting the behavior of rational, strategic individuals in situations of conflict. Together with Paul Goldberg and Christos Papadimitriou we show that in complex systems Nash equilibrium can be computationally unachievable. This implies that it is not always relevant and/or justifiable to study the Nash equilibria of a system. Here is a simplified exposition of our article that we wrote for CACM's February 2009 Issue.
I also wrote a survey article on the complexity of Nash equilibria, which appeared in a Computer Science Review special volume dedicated to Christos Papadimitriou's work.
Finally, I recently showed that even arriving at an approximate Nash equilibrium can be computationally intractable.
My dissertation was awarded the 2008 ACM Doctoral Dissertation Award. Together with Paul Goldberg and Christos Papadimitriou, we also received the 2008 Game Theory and Computer Science Prize. The prize is awarded once every four years at the World Congress of the Game Theory Society. The citation for our paper reads in part as follows: "This paper made key conceptual and technical contributions in an illustrious line of work on the complexity of computing Nash equilibrium. It also highlights the necessity of constructing practical algorithms that compute equilibria efficiently on important subclasses of games." Here is a blog post from the congress by Paul. In 2011, our same paper was awarded the 2011 SIAM Outstanding Paper Prize.
SLIDES and VIDEO presentatation on Nash equilibrium complexity.
Bayesian Mechanism Design: Mechanism design in the presence of Bayesian priors has received much attention in Economics, focusing among other problems on generalizing Myerson's celebrated auction to multi-item settings. Nevertheless, only special cases have been solved, with a general solution remaining elusive. More recently, there has been an explosion of algorithmic work on the problem, focusing on computing optimal auctions, and understanding their structure. With Yang Cai and Matt Weinberg we provide a general algorithmic framework for computing optimal mechanisms in arbitrary settings (general objectives, types, allocation constraints). Our framework allows algorithmically generalizing Myerson's auction to selling multiple items, and designing approximately optimal mechanisms for non-linear objectives such as makespan minimization with strategic machines.
More recent work with Alan Deckelbaum and Christos Tzamos has provided analytical characterizations of multi-item mechanisms. See our forthcoming paper at Econometrica, whose preliminary form received the Best Paper Award at the ACM Conference on Economics and Computation in 2013.
SLIDES on Algorithmic Bayesian Mechanism Design from our EC 2014 tutorial.
Recent Surveys:
Statistics: Statistics has traditionally focused on the asymptotic analysis of tests, as the number of samples tends to infinity. Motivated by applications of Statistics in life sciences, where the sample size is commonly small, as well as applications in the analysis of high-dimensional distributions, where the sample size is small relative to the support of the underlying distributions, we re-think the foundations of Statistics in the small sample regime. With Jayadev Acharya and Gautam Kamath, we recently wrote a paper on testing properties of distributions which appeared in NIPS'15 as a spotlight talk. A video of the talk can be found here.
SLIDES from my tutorial at Greek Stochastics Theta.
[Teaching]
- 6.046/18.410: Design and Analysis of Algorithms, Spring 2016
- 6.891: Games, Decision, and Computation, Spring 2015
- 6.046/18.410: Design and Analysis of Algorithms, Fall 2014
- 6.S080: Introduction to Inference, Spring 2014
- 6.891: Games, Decision, and Computation, Fall 2013
- 6.046/18.410: Design and Analysis of Algorithms, Spring 2013
- 6.006: Introduction to Algorithms, Spring 2012
- 6.853: Topics in Algorithmic Game Theory, Fall 2011
- 6.896: Probability and Computation, Spring 2011
- 6.006: Introduction to Algorithms, Fall 2010
- 6.896: Topics in Algorithmic Game Theory, Spring 2010
- 6.006: Introduction to Algorithms, Fall 2009
[Editorial]
[Organization]
[Plenary Talks and Tutorials]
- semi-plenary talk; the Third World Congress of the Game Theory Society @Northwestern University; July 2008.
- plenary talk; the New York Computer Science and Economics Day (NYCE) 2008 @the New York Academy of Sciences; October 2008.
- tutorial; the ACM Conference on Electronic Commerce 2009 @Stanford University; July 2009.
- plenary talk; New York Theory Day; December 2009.
- tutorial; the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), May 2010.
- tutorial; summer school on algorithmic ecnomics, CMU, August 2012.
- plenary; the 6th International Symposium on Algorithmic Game Theory (SAGT), October 2013.
- tutorial; Fall school on Algorithmic Game Theory and Learning, Aachen University, October 2013.
- tutorial; the ACM Conference on Economics and Computation 2014 @Stanford University; June 2014.
- plenary talk; International Conference on Game Theory, Stony Brook; July 2015.
- plenary talk; the 14th Conference on Research on Economic Theory and Econometrics, Chania, Greece July 2015.
- plenary talk; the 26th International Symposium on Algorithms and Computation (ISAAC), Nagoya, Japan December 2015.
- plenary talk; the New York Computer Science and Economics Day (NYCE), NYU January 2016.
- tutorial; Greek stochastics theta, Tinos Island, Greece, July 2016.
- plenary talk; the 9th International Symposium on Algorithmic Game Theory (SAGT), September 2016.
Program Committees: SODA 2008,
EC 2009,
SAGT 2009,
WAOA 2009,
STOC 2010,
ICALP 2010,
EC 2011,
EC 2012,
EC 2013,
STOC 2013,
ITCS 2014,
EC 2014,
ITCS 2015,
STOC 2015,
EC 2015,
EC 2016
The Satrapy
What a misfortune, although you are made
for fine and great works
this unjust fate of yours always
denies you encouragement and success;
that base customs should block you;
and pettiness and indifference.
And how terrible the day when you yield
(the day when you give up and yield),
and you leave on foot for Susa,
and you go to the monarch Artaxerxes
who favorably places you in his court,
and offers you satrapies and the like.
And you accept them with despair
these things that you do not want.
Your soul seeks other things, weeps for other things;
the praise of the public and the Sophists,
the hard-won and inestimable Well Done;
the Agora, the Theater, and the Laurels.
How can Artaxerxes give you these,
where will you find these in a satrapy;
and what life can you live without these.
Constantine P. Cavafy (1910).
