I am a PhD Student in the Theory of Computation group at MIT where I am advised by Constantinos Daskalakis.
I am interested in Algorithmic Game Theory, Learning Theory as well as in the Design, Analysis and Theory of Algorithms.
Room 32-G630
The Stata Center
32 Vassar Street
Cambridge, MA 02139
I joined the graduate program of MIT on September 2011 in the Theory of Computation group at CSAIL. My PhD advisor is Costis Daskalakis and I enjoy working with him on a wide range of problems from auction theory to learning theory.
I grew up in Athens, Greece where I also had my undergraduate studies at the National Technical University of Athens (Sept. 2006 - June 2011). During my time there, I had the opportunity to work with my advisor Dimitris Fotakis on different problems in mechanism design without money.
I spent the summer of 2014 as a research intern at Yahoo! Labs, Sunnyvale working with Chris Wilkens on multiple research and practical questions regarding online ad auctions. I also interned for Google, Cambridge in the mobile search team during summer 2012.
Show moreAbstract. We provide a duality-based framework for revenue maximization in a multiple-good monopoly. Our framework shows that every optimal mechanism has a certificate of optimality that takes the form of an optimal transportation map between measures. Our framework improves previous partial results, by establishing a strong duality theorem between optimal mechanism design and optimal transportation, and is enabled by an extension of the Monge-Kantorovich duality that accommodates convexity constraints. Using our framework, we prove that grand-bundling mechanisms are optimal if and only if two stochastic dominance conditions hold between specific measures induced by the type distribution. This result strengthens several results in the literature, where only sufficient conditions have been provided. As a corollary of our tight characterization of bundling optimality, we show that the optimal mechanism for n independent uniform items each supported on [c,c+1] is a grand bundling mechanism, as long as c is sufficiently large, extending Pavlov's result for 2 items [Pavlov11]. Finally, we provide a partial characterization of general two-item mechanisms, and use our characterization to obtain optimal mechanisms in several settings, including an example with two independently distributed items where a continuum of lotteries is necessary for revenue maximization.
@inproceedings{daskalakis2014complexity, title={The complexity of optimal mechanism design}, author={Daskalakis, Constantinos and Deckelbaum, Alan and Tzamos, Christos}, booktitle={Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms}, pages={1302--1318}, year={2014}, organization={SIAM} }
Abstract. Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless ZPP contains P^{#P}. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated.
We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint.
@inproceedings{daskalakis2013mechanism, title={Mechanism design via optimal transport}, author={Daskalakis, Constantinos and Deckelbaum, Alan and Tzamos, Christos}, booktitle={Proceedings of the fourteenth ACM conference on Electronic commerce}, pages={269--286}, year={2013}, organization={ACM} }
Abstract. Optimal mechanisms have been provided in quite general multi-item settings [Cai et al. 2012b, as long as each bidder's type distribution is given explicitly by listing every type in the support along with its associated probability. In the implicit setting, e.g. when the bidders have additive valuations with independent and/or continuous values for the items, these results do not apply, and it was recently shown that exact revenue optimization is intractable, even when there is only one bidder [Daskalakis et al. 2013]. Even for item distributions with special structure, optimal mechanisms have been surprisingly rare [Manelli and Vincent 2006] and the problem is challenging even in the two-item case [Hart and Nisan 2012]. In this paper, we provide a framework for designing optimal mechanisms using optimal transport theory and duality theory. We instantiate our framework to obtain conditions under which only pricing the grand bundle is optimal in multi-item settings (complementing the work of [Manelli and Vincent 2006]), as well as to characterize optimal two-item mechanisms. We use our results to derive closed-form descriptions of the optimal mechanism in several two-item settings, exhibiting also a setting where a continuum of lotteries is necessary for revenue optimization but a closed-form representation of the mechanism can still be found efficiently using our framework.
@inproceedings{fotakis2013strategyproof, title={Strategyproof facility location for concave cost functions}, author={Fotakis, Dimitris and Tzamos, Christos}, booktitle={Proceedings of the fourteenth ACM conference on Electronic commerce}, pages={435--452}, year={2013}, organization={ACM} }
Abstract. We consider k-Facility Location games, where n strategic agents report their locations on the real line, and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents.
We present a randomized mechanism, called Equal Cost, which is group strategyproof and achieves a bounded approximation ratio for all k and n, for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost. To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with k > 2 facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k. On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser, which applies to instances with k facilities and n = k+1 agents, and for any given concave cost function, is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost.
@inproceedings{fotakis2013power, title={On the power of deterministic mechanisms for facility location games}, author={Fotakis, Dimitris and Tzamos, Christos}, booktitle={Proceedings of the 40th international conference on Automata, Languages, and Programming-Volume Part I}, pages={449--460}, year={2013}, organization={Springer-Verlag} }
Abstract. We consider K-Facility Location games, where n strategic agents report their locations in a metric space, and a mechanism maps them to K facilities. Our main result is an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with n ≥ 5 agents, any such mechanism either admits a unique dictator, or always places the facilities at the leftmost and the rightmost location of the instance. As a corollary, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating 2 facilities on the line to minimize the total connection cost is precisely n-2. Another rather surprising consequence is that the Two-Extremes mechanism of (Procaccia and Tennenholtz, EC 2009) is the only deterministic anonymous strategyproof mechanism with a bounded approximation ratio for 2-Facility Location on the line.
The proof of the characterization employs several new ideas and technical tools, which provide new insights into the behavior of deterministic strategyproof mechanisms for K-Facility Location games, and may be of independent interest. Employing one of these tools, we show that for every K ≥ 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for K-Facility Location on the line, even for simple instances with K+1 agents. Moreover, building on the characterization for the line, we show that there do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on more general metric spaces, which is true even for simple instances with 3 agents located in a star.
@incollection{daskalakis2012optimal, title={Optimal pricing is hard}, author={Daskalakis, Constantinos and Deckelbaum, Alan and Tzamos, Christos}, booktitle={Internet and Network Economics}, pages={298--308}, year={2012}, publisher={Springer} }
Abstract. We show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in single-item settings where the buyer's value distribution is a sum of independently distributed attributes, or multi-item settings where the buyer's values for the items are independent. We also show that it is intractable to optimally price the grand bundle of multiple items for an additive bidder whose values for the items are independent. These difficulties stem from implicit definitions of a value distribution. We provide three instances of how different properties of implicit distributions can lead to intractability: the first is a #P-hardness proof, while the remaining two are reductions from the SQRT-SUM problem of Garey, Graham, and Johnson. While simple pricing schemes can oftentimes approximate the best scheme in revenue, they can have drastically different underlying structure. We argue therefore that either the specification of the input distribution must be highly restricted in format, or it is necessary for the goal to be mere approximation to the optimal scheme's revenue instead of computing properties of the scheme itself.
@incollection{fotakis2010winner, title={Winner-imposing strategyproof mechanisms for multiple facility location games}, author={Fotakis, Dimitris and Tzamos, Christos}, booktitle={Internet and Network Economics}, pages={234--245}, year={2010}, publisher={Springer} }
Abstract. We study Facility Location games, where a number of facilities are placed in a metric space based on locations reported by strategic agents. A mechanism maps the agents' locations to a set of facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may misreport their location. We are interested in mechanisms that are strategyproof, i.e., ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and approximate the optimal social cost. We focus on the closely related problems of k-Facility Location and Facility Location with a uniform facility opening cost, and mostly study winner-imposing mechanisms, which allocate facilities to the agents and require that each agent allocated a facility should connect to it. We show that the winner-imposing version of the Proportional Mechanism (Lu et al., EC '10) is stategyproof and 4k-approximate for the k-Facility Location game. For the Facility Location game, we show that the winner-imposing version of the randomized algorithm of (Meyerson, FOCS '01), which has an approximation ratio of 8, is strategyproof. Furthermore, we present a deterministic non-imposing group strategyproof O(log n)-approximate mechanism for the Facility Location game on the line.
Abstract. An (n, k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set {e_{1},...,e_{k}} of standard basis vectors in R_{k}. We prove a structural characterization of these distributions, showing that, for all ε > 0, any (n,k)-Poisson multinomial random vector is ε-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/ε), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements ε. In particular, it overcomes factors depending on logn and, importantly, the minimum eigenvalue of the PMD's covariance matrix from the distance to a multidimensional Gaussian random variable. We use our structural characterization to obtain an ε-cover, in total variation distance, of the set of all (n, k)-PMDs, significantly improving the cover size of Daskalakis and Papadimitriou, and obtaining the same qualitative dependence of the cover size on n and ε as the k = 2 cover of Daskalakis and Papadimitriou. We further exploit this structure to show that (n, k)-PMDs can be learned to within ε in total variation distance from O_{k}(1/ε^{2}) samples, which is near-optimal in terms of dependence on ε and independent of n. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas, and Servedio for Poisson Binomials to arbitrary dimension.
Abstract. Many auction settings implicitly or explicitly require that bidders are treated equally ex-ante. This may be because discrimination is philosophically or legally impermissible, or because it is practically difficult to implement or impossible to enforce. We study so-called anonymous auctions to understand the revenue tradeoffs and to develop simple anonymous auctions that are approximately optimal.
We consider digital goods settings and show that the optimal anonymous, dominant strategy incentive compatible auction has an intuitive structure --- imagine that bidders are randomly permuted before the auction, then infer a posterior belief about bidder i's valuation from the values of other bidders and set a posted price that maximizes revenue given this posterior.
We prove that no anonymous mechanism can guarantee an approximation better than O(n) to the optimal revenue in the worst case (or O(log n) for regular distributions) and that even posted price mechanisms match those guarantees. Understanding that the real power of anonymous mechanisms comes when the auctioneer can infer the bidder identities accurately, we show a tight O(k) approximation guarantee when each bidder can be confused with at most k "higher types". Moreover, we introduce a simple mechanism based on n target prices that is asymptotically optimal and build on this mechanism to extend our results to m-unit auctions and sponsored search.
Abstract. We introduce a general approach based on selective exact verification and obtain approximate mechanisms without money for maximizing the social welfare in general domains. Having a good allocation in mind, a mechanism with verification selects few critical agents and detects, using a verification oracle, whether they have reported truthfully. If yes, the mechanism produces the desired allocation. Otherwise, the mechanism ignores any misreports and proceeds with the remaining agents. We obtain randomized truthful mechanisms without money that verify only lnm/ε agents, where m is the number of outcomes, independently of the total number of agents, and are (1-ε)-approximate for the social welfare. A remarkable property of our mechanisms is robustness, namely that their outcome depends only on the reports of the truthful agents. Robustness allows our mechanisms to deal with unpredictable or malicious agents, a case where ordinary truthful mechanisms may completely fail.