All reports by Author Constantinos Daskalakis:

__
TR18-002
| 31st December 2017
__

Constantinos Daskalakis, Gautam Kamath, John Wright#### Which Distribution Distances are Sublinearly Testable?

__
TR17-006
| 15th December 2016
__

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath#### Testing Ising Models

Revisions: 2

__
TR11-172
| 20th December 2011
__

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg#### An Algorithmic Characterization of Multi-Dimensional Mechanisms

__
TR11-170
| 16th December 2011
__

Constantinos Daskalakis, S. Matthew Weinberg#### On Optimal Multi-Dimensional Mechanism Design

__
TR05-139
| 21st November 2005
__

Constantinos Daskalakis, Christos H. Papadimitriou#### Three-Player Games Are Hard

__
TR05-115
| 27th September 2005
__

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou#### The complexity of computing a Nash equilibrium

Constantinos Daskalakis, Gautam Kamath, John Wright

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent ... more >>>

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg

We obtain a characterization of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting.

Our characterization is enabled by a novel, constructive proof of Border's theorem [Border ... more >>>

Constantinos Daskalakis, S. Matthew Weinberg

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder's values for the items are sampled from a ... more >>>

Constantinos Daskalakis, Christos H. Papadimitriou

We prove that computing a Nash equilibrium in a 3-player

game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

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

more >>>