Constantinos Daskalakis Homepage

Education

UNIVERSITY OF CALIFORNIA, BERKELEY
Ph.D. in Computer Science 2004-2008
Microsoft Fellowship 2007 - now
UC Berkeley Fellowship 2004-2005
Advisor: Christos H. Papadimitriou
GPA: 4.000/4 (Summa Cum Laude)
Courses: Complexity Theory, Statistical Learning Theory, Reading the Classics, Foundations of Parallel and Distributed Systems, Computational Geometry, Combinatorial Optimization, Randomness and Computation, Pseudorandomness and Extractors, Polynomials of Random Variables, Markov chain Monte Carlo, Great Algorithms, Topics in Probability, Gibbs Measures, Probability Theory, Probability for Applications, Computer Architecture

NATIONAL TECHNICAL UNIVERSITY of ATHENS (NTUA), GREECE
Diploma in Electrical Engineering and Computer Science, 1999-2004
Thesis: On the Existence of Pure Nash Equilibria in Graphical Games with succinct description
Advisor: Stathis Zachos
GPA: 9.98/10.00 (Summa Cum Laude)

VARVAKIOS HIGH SCHOOL, ATHENS, GREECE
GPA: 20.0/20

Research Interests

My research interests lie in the area of theoretical computer science, in particular computational game theory, computational biology and applied probability.

Publications - Research

Game Theory

Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant, On the Complexity of Nash Equilibria of Action-Graph Games,
Submitted, 2008.

We consider the problem of computing Nash Equilibria of action-graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, is a succinct representation of games that encapsulates both "local" dependencies as in graphical games, and partial indifference to other agents' identities as in anonymous games, which occur in many natural settings. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant treewidth and a constant number of agent types (and an arbitrary number of strategies), together with hardness results for the cases when either the treewidth or the number of agent types is unconstrained. In particular, we show that even if the action graph is a tree, but the number of agent-types is unconstrained, it is NP-complete to decide the existence of a pure-strategy Nash equilibrium and PPAD-complete to compute a mixed Nash equilibrium (even an approximate one); similarly for symmetric AGGs (all agents belong to a single type), if we allow arbitrary treewidth. These hardness results suggest that, in some sense, our PTAS is as strong of a positive result as one can expect.
```
@inproceedings{DSVV:actiongraph08,
  title = "On the Complexity of Nash Equilibria of Action-Graph Games",
  author = "Constantinos Daskalakis and Grant Schoenebeck and Gregory Valiant and Paul Valiant",
  year = "2008",
  booktitle = "submitted",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis and Christos H. Papadimitriou, On the Exhaustive Method for Nash Equilibria,
Submitted, 2008.

Constantinos Daskalakis, Alexandros G. Dimakis and Elchanan Mossel, Connectivity and Equilibrium in Random Games,
Submitted, 2008.

We study how the structure of the interaction graph affects the Nash equilibria of the resulting game. In particular, for a fixed interaction graph, we are interested if there exist Nash equilibria which arise when random utility tables are assigned to the players. We provide conditions for the structure of the graph under which equilibria are likely to exist and complementary conditions which make the existence of equilibria highly unlikely. Our results have immediate implications for many deterministic graphs and generalize known results for games on the complete graph. In particular, our results imply that the probability that bounded degree graphs have Nash equilibria is exponentially small in the size of the graph and yield a simple algorithm that finds small non-existence certificates for a large family of graphs.

In order to obtain a refined characterization of the degree of connectivity associated with the existence of equilibria, we study the model in the random graph setting. In particular, we look at the case where the interaction graph is drawn from the Erdos-Renyi, G(n,p), model where each edge is present independently with probability p. For this model we establish a double phase transition for the existence of pure Nash equilibria as a function of the average degree p n consistent with the non-monotone behavior of the model. We show that when the average degree satisfies n p > (2 + Omega(1)) log n, the number of pure Nash equilibria follows a Poisson distribution with parameter 1. When 1/n << n p < (0.5 -Omega(1)) log n, pure Nash equilibria fail to exist with high probability. Finally, when n p << 1/n, a pure Nash equilibrium exists with high probability.
```
@inproceedings{DDM:random games,
  title = "Connectivity and Equilibrium in Random Games",
  author = "Constantinos Daskalakis and Alexandros G. Dimakis and Elchanan Mossel",
  year = "2008",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis and Christos H. Papadimitriou, Computing Equilibria in Anonymous Games,
In the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007.

We present efficient approximation algorithms for finding Nash equilibria in anonymous games, that is, games in which the players utilities, though different, do not differentiate between other players. Our results pertain to such games with many players but few strategies. We show that any such game has an approximate pure Nash equilibrium, computable in polynomial time, with approximation O(s^2 L), where s is the number of strategies and L is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an eps-approximate Nash equilibrium when the number of strategies is two.
```
@inproceedings{DP:anonymous07,
  title = "Computing Equilibria in Anonymous Games",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2007",
  booktitle = "FOCS",
}
```
[abstract] [bib] [arXiv]

Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou, Progress in Approximate Nash Equilibria,
In the 8th ACM Conference on Electronic Commerce, EC 2007.

It is known [Daskalakis, Mehta, Papadimitriou 2006] that an additively eps-approximate Nash equilibrium (with supports of size at most two) can be computed in polynomial time in any 2-player game with eps= .5. It is also known that no approximation better than .5 is possible unless equilibria with support larger than log n are considered, where n is the number of strategies per player. We give a polynomial algorithm for computing an eps-approximate Nash equilibrium in 2-player games with eps= .38; our algorithm computes equilibria with arbitrarily large supports.
```
@inproceedings{DMP:approximate nash 2,
  title = "Progress in Approximate Nash Equilibria",
  author = "Constantinos Daskalakis and Aranyak Mehta and Christos H. Papadimitriou",
  year = "2007",
  booktitle = "EC",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, Aranyak Mehta and Christos H. Papadimitriou, A Note on Approximate Nash Equilibria,
In the 2nd international Workshop on Internet & Network Economics, WINE 2006. Invited to Algorithmica Special Issue.

In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [Lipton, Markakis, Mehta 2003], and no approximation better than 1/4 is possible by any algorithm that examines equilibria involving fewer than log n strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a 1/2 -approximate Nash equilibrium in any 2-player game. For the more demanding notion of well-supported approximate equilibrium due to Daskalakis, Goldberg, Papapdimitriou 2006 no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0-1), and that an approximation of 5/6 is possible contingent upon a graph-theoretic conjecture.
```
@inproceedings{DMP:approximate nash 1,
  title = "A Note on Approximate Nash Equilibria",
  author = "Constantinos Daskalakis and Aranyak Mehta and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "WINE",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, Alex Fabrikant and Christos Papadimitriou, The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games,
In the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006.

A recent sequence of results (see below) established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result --- even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known.
```
@inproceedings{DFP:succinct games,
  title = "The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games",
  author = "Constantinos Daskalakis and Alex Fabrikant and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "ICALP",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis and Christos Papadimitriou, Computing Pure Nash Equilibria via Markov Random Fields,
In the 7th ACM Conference on Electronic Commerce, EC 2006. Best Student Paper Award.

We present a reduction from graphical games to Markov random fields so that pure Nash equilibria in the former can be found by statistical inference on the latter. Our result, when combined with the junction tree algorithm for statistical inference, yields a unified proof of all previously known tractable cases of the NP-complete problem of finding pure Nash equilibria in graphical games, but also implies efficient algorithms for new classes, such as the games with O(log n) treewidth. Furthermore, this important problem becomes susceptible to a wealth of sophisticated and empirically successful techniques from Machine Learning.
```
@inproceedings{DP: nash via MRFs,
  title = "Computing Pure Nash Equilibria via Markov Random Fields",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "EC",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis and Christos H. Papadimitriou, Three-Player Games Are Hard,
Manuscript 2005.

We prove that computing a Nash equilibrium in a 3-player game is PPAD-complete, solving a problem left open in our result on the complexity of Nash equilibria.
```
@inproceedings{DP: three players,
  title = "Three-Player Games Are Hard",
  author = "Constantinos Daskalakis and Christos H. Papadimitriou",
  year = "2005",
  booktitle = "ECCC Report",
}
```
[abstract] [bib] [ECCC Report 2005]

Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou, The Complexity of Computing a Nash Equilibrium,
In the 38th ACM Symposium on Theory of Computing, STOC 2006. Invited to SIAM Journal on Computing special issue for STOC.

We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial-time solvability of normal-form games and graphical games, and shows that these kinds of games can implement arbitrary members of a PPAD-complete class of Brouwer functions.
```
@inproceedings{DP: complexity of nash equilibria,
  title = "The Complexity of Computing a Nash Equilibrium",
  author = "Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou",
  year = "2006",
  booktitle = "STOC",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis and Christos Papadimitriou, The Complexity of Games on Highly Regular Graphs,
In the 13th Annual European Symposium on Algorithms, ESA 2005.

We study the complexity of computing equilibria in succinct games defined on highly regular graphs. Surprisingly, the problem of deciding whether there exists a pure Nash equilibrium in a one-dimensional highly-regular game is NL-complete, whereas if the game is multi-dimensional it is NEXP-complete. Such a dichotomy does not exist for the problem of computing mixed Nash and correlated equilibria. By taking advantage of the regularities of the game we construct a deterministic exponential time algorithm that computes a (succinct description of a) mixed Nash equilibrium of any given highly regular game and a polynomial time algorithm that computes a (succinct description of a) correlated equilibrium.
```
@inproceedings{DP: regular games,
  title = "The Complexity of Games on Highly Regular Graphs",
  author = "Constantinos Daskalakis  and Christos H. Papadimitriou",
  year = "2005",
  booktitle = "ESA",
}
```
[abstract] [bib] [pdf]

Constantinos Daskalakis, On the Existence of Pure Nash Equilibria in Graphical Games with succinct description,
National Technical University of Athens, 2004 (In Greek).

My diploma thesis at NTUA. My advisor was Stathis Zachos
```
@inproceedings{DP: regular games,
  title = "The Complexity of Games on Highly Regular Graphs",
  author = "Constantinos Daskalakis",
  year = "2005",
  booktitle = "ESA",
}
```
[abstract] [pdf]

Computational Biology

Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch, Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep,
In progress, 2007.

Constantinos Daskalakis, Elchanan Mossel and Sebastien Roch, Optimal Phylogenetic Reconstruction,
In the 38th ACM Symposium on Theory of Computing, STOC 2006.

We resolve an important problem in systematic biology, namely that of reconstructing phylogenies from few characters. It is well known that, in order to reconstruct a tree on n taxa, sequences of length at least log n are needed. It was conjectured by Mike Steel that for the Cavender-Farris-Neyman model of evolution, if the mutation probability p on all edges of the tree satisfies 2(1-2p)^2<1, then the tree can be recovered from sequences of length O(log n). We resolve this conjecture in the positive way by describing a phylogenetic reconstruction algorithm that uses O(log n) characters. The algorithm is tight for the Cavender-Farris-Neyman model, since, if the mutation probability does not satisfy 2(1-2p)^2<1, there is a lower bound of polynomially many characters. Finally, our algorithm extends to reconstructing phylogenies from O(log n) taxa in the Jukes-Cantor model and it is tight for the robust reconstruction problem.
```
@inproceedings{DMR: optimal phylo,
  title = "Optimal Phylogenetic Reconstruction",
  author = "Constantinos Daskalakis and Elchanan Mossel and Sebastien Roch",
  year = "2006",
  booktitle = "STOC",
}
```
[abstract] [bib] [arXiv]

C. Daskalakis, C. Hill, A. Jaffe, R. Mihaescu, E. Mossel and S. Rao, Maximal Accurate Forests From Distance Matrices,
In the 10th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2006.

We present a fast converging method for distance-based phylogenetic inference, which is novel in two respects. First, it is the only method (to our knowledge) to guarantee accuracy when knowledge about the model tree, i.e bounds on the edge lengths, is not assumed. Second, our algorithm guarantees that, with high probability, no false assertions are made. The algorithm produces a maximal edge-disjoint subforest of the model tree, with running time O(n^4) in the worst case. Empirical testing has been promising, comparing favorable to Neighbor Joining and Maximum Parsimony, with the advantage of making no false assertions about the topology of the model tree; guarantees against false positives can be controlled as a parameter by the user.
```
@inproceedings{DHJMMR: maximal forests,
  title = "Maximal Accurate Forests From Distance Matrices",
  author = "C. Daskalakis and C. Hill and A. Jaffe and R. Mihaescu and E. Mossel and S. Rao",
  year = "2006",
  booktitle = "RECOMB",
}
```
[abstract] [bib] [pdf]

Applied Probability

Constantinos Daskalakis, Alexandros G. Dimakis, Richard Karp and Martin Wainwright, Probabilistic Analysis of Linear Programming Decoding,
In the 18th Annual ACM-SIAM Symposium On Discrete Algorithms, SODA 2007. To appear in IEEE Transactions on Information Theory.

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses all prior non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting by-product of our analysis is to establish the existence of "almost expansion" in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, with expansion coefficients much larger than the classical case.
```
@inproceedings{DDKW: LP decoding,
  title = "Probabilistic Analysis of Linear Programming Decoding",
  author = "Constantinos Daskalakis and Alexandros G. Dimakis and Richard Karp and Martin Wainwright",
  year = "2007",
  booktitle = "SODA",
}
```
[abstract] [bib] [arXiv]

Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis and Sebastien Roch, An Analysis of Preferential Attachment with Fitness,
In the 39th ACM Symposium on Theory of Computing, STOC 2007.

We provide a rigorous analysis of preferential attachment with fitness, suggested by Bianconi and Barabasi and studied by Motwani and Xu, in which the degree of a vertex is scaled by its quality to determine its attractiveness. Including quality considerations in the classical preferential attachment model provides a much more realistic description of many complex networks, such as the web graph, and allows to observe a much richer behavior in the growth dynamics of these networks. Specifically, depending on the shape of the distribution from which the qualities of the vertices are drawn, we observe three distinct phases, namely a first-mover-advantage phase, a fit-get-richer phase and an innovation-pays-off phase. We precisely characterize the properties of the quality distribution that result in each of these phases and we compute the exact growth dynamics for each phase. The dynamics provide rich information about the quality of the vertices, which can be very useful in many practical contexts, including ranking algorithms for the web, recommendation algorithms, as well as the study of social networks.
```
@inproceedings{BCDR: pref attachment fitness,
  title = "An Analysis of Preferential Attachment with Fitness",
  author = "Christian Borgs and Jennifer T. Chayes and Constantinos Daskalakis and Sebastien Roch",
  year = "2007",
  booktitle = "STOC",
}
```
[abstract] [bib] [pdf]

Other

Kamalika Chaudhuri, Constantinos Daskalakis, Robert Kleinberg and Henry Lin Online Bipartite Perfect Matching With Augmentation,
Submitted, 2008.
[abstract] [bib] [arxiv]

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin Sorting and Ranking in Partially Ordered Sets,
Submitted.

We study algorithms for sorting and ranking in partially ordered sets. In particular, we present an algorithm for sorting a width w poset of size n with query complexity O(n(w + log n)), which is within a constant factor of the information-theoretic lower bound. We also show that a variant of Mergesort has query complexity O(wn log (n/w) ) and total complexity O(w^2 n log(n/w) ).

Two problems related to sorting are the problems of finding the minimal elements in a poset and its generalization of finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(wn) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. We also derive upper bounds on the total complexity of some other problems of a similar flavor, such as computing a linear extension of a poset and computing the heights of all elements.
```
@inproceedings{DKMRV: sorting posets,
  title = "Sorting and Ranking in Partially Ordered Sets",
  author = "Constantinos Daskalakis and Richard M. Karp and Elchanan Mossel and Samantha Riesenfeld and Elad Verbin ",
  year = "2006",
}
```
[abstract] [bib] [arxiv]

Stergios Stergiou, Constantinos Daskalakis and George K. Papakonstantinou, Fast and Efficient Heuristic ESOP Minimization Algorithm,
IEEE Great Lakes Symposium on VLSI (GLSVLSI 2004).

We present an algorithm that solves a fundamental theoretical problem in logic synthesis, the problem of Exclusive-Sum-of-Products Minimization. Our algorithm is compared to the state-of-the art algorithm used in most CAD-programs. The experiments show that our algorithm matches and in some cases surpasses the performance of the state of the art algorithm.
```
@inproceedings{SDP: esop minimization,
  title = "Fast and Efficient Heuristic ESOP Minimization Algorithm",
  author = "Stergios Stergiou and Constantinos Daskalakis and George K. Papakonstantinou",
  year = "2004",
  booktitle = "GLSVLSI",
}
```
[abstract] [bib] [pdf]

Awards

Here is a list of some awards for which my parents are proud:).