I am an Associate Professor at MIT's Electrical Engineering and Computer Science department, a member of CSAIL, and affiliated with 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.
MIT's Theory of Computation Colloquium.
Current students: Alan Deckelbaum, Matt Weinberg, Christos Tzamos, Gautam Kamath.
Past students: Yang Cai (MIT -> UC Berkeley (postdoc) -> McGill (assistant professor)).
2013 Best Paper and Best Student Paper Award in the 14th Conference on Electronic Commerce
2012 Microsoft Research Faculty Fellowship
2012 Best Student Paper Award in the 13th Conference on Electronic Commerce
2011 X-Window Consortium Chair
2011 Ruth and Joel Spira Award for Distinguished Teaching
2011 SIAM Outstanding Paper Prize
2010 Sloan Research Fellowship in Computer Science
2009 NSF Career Award
2008 ACM Doctoral Dissertation Award
2008 Game Theory and Computer Science Prize, awarded by the Game Theory Society
2007 Microsoft Research Ph.D. Fellowship
2006 Best Paper Award in the 7th Conference on Electronic Commerce
Technology Review: Gaming the System
MIT news piece on auctions
MIT news piece on complexity of equilibria
If you speak or like Greek, check out my 2011 TEDx Athens talk, and you may also volunteer to add subtitles ;)
My research focus is on algorithmic game theory, computational biology and applied probability. Publications.
Complexity of Equilibria:
My Ph.D. research
examines 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 defined it, and is traditionally used in Game Theory as a mathematical way of predicting the behavior of people in conflict situations. Together with Paul Goldberg and Christos Papadimitriou we show
that in complex systems the 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 report
from the congress by Paul. In 2011, our same paper was awarded the 2011 SIAM Outstanding Paper Prize
- 6.891: Games, Decision, and Computation - Part A, Fall 2013
- 6.046/18.410: Design and Analysis 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
Program Committees: SODA 2008
, EC 2009
, SAGT 2009
, WAOA 2009
, STOC 2010
, ICALP 2010
, EC 2011
, EC 2012
, EC 2013
, STOC 2013
, ITCS 2014
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)
since September 2009.