I am a Researcher at Microsoft Research, New England. My research lies at the intersection of theoretical computer science, machine learning and economics/econometrics. I received my Ph.D. in Computer Science from Cornell University, where I had the privilege to be advised by Eva Tardos and then spent two years as a postdoc researcher at Microsoft Research, NYC, as part of the Algorithmic Economics and the Machine Learning groups. I obtained my diploma in EECS at the National Technical University of Athens, Greece.

At MSR I have had the opportunity to work with an amazing set of summer interns including Nika Haghtalab, Gautam Kamath, Jieming Mao, Jonas Mueller, Yichen Wang, Steven Wu, Juba Ziani. We start looking at internship applications for the summer in late fall. (List me as a contact to make sure I see your application.) Typically our interns are Ph.D. students with strong publication records in areas relevant to our lab.


1 Memorial Dr.
Cambridge, MA, 02142
vasy [at] microsoft.com


Representative Publications

Robust Optimization for Non-Convex Objectives

Robert Chen, Brendan Lucier, Yaron Singer, Vasilis Syrgkanis
31st Annual Conference on Neural Information Processing Systems, NIPS'17
Oral Presentation


We consider robust optimization problems, where the goal is to optimize in the worst case over a class of objective functions. We develop a reduction from robust improper optimization to Bayesian optimization: given an oracle that returns alpha-approximate solutions for distributions over objectives, we compute a distribution over solutions that is α-approximate in the worst case. We show that derandomizing this solution is NP-hard in general, but can be done for a broad class of statistical learning tasks. We apply our results to robust neural network training and submodular optimization. We evaluate our approach experimentally on corrupted character classification, and robust influence maximization in networks.

Oracle Efficient Learning and Auction Design

Miro Dudik, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jenn Wortman Vaughan
58th Annual IEEE Symposium on Foundations of Computer Science, FOCS'17


We consider the design of computationally efficient online learning algorithms in an adversarial setting in which the learner has access to an offline optimization oracle. We present an algorithm called Generalized Follow-the-Perturbed-Leader and provide conditions under which it is oracle-efficient while achieving vanishing regret. Our results make significant progress on an open problem raised by Hazan and Koren, who showed that oracle-efficient algorithms do not exist in general and asked whether one can identify properties under which oracle-efficient online learning may be possible. Our auction-design framework considers an auctioneer learning an optimal auction for a sequence of adversarially selected valuations with the goal of achieving revenue that is almost as good as the optimal auction in hindsight, among a class of auctions. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in single-parameter settings, (2) envy-free item pricing in multi-item auctions, and (3) s-level auctions of Morgenstern and Roughgarden for single-item settings. The last result leads to an approximation of the overall optimal Myerson auction when bidders' valuations are drawn according to a fast-mixing Markov process, extending prior work that only gave such guarantees for the i.i.d. setting. Finally, we derive various extensions, including: (1) oracle-efficient algorithms for the contextual learning setting in which the learner has access to side information (such as bidder demographics), (2) learning with approximate oracles such as those based on Maximal-in-Range algorithms, and (3) no-regret bidding in simultaneous auctions, resolving an open problem of Daskalakis and Syrgkanis.

Learning in Auctions: Regret is Hard, Envy is Easy

Constantinos Daskalakis, Vasilis Syrgkanis
57th Annual IEEE Symposium on Foundations of Computer Science, FOCS'16


A line of recent work provides welfare guarantees of simple combinatorial auction formats, such as selling m items via simultaneous second price auctions (SiSPAs) (Christodoulou et al. 2008, Bhawalkar and Roughgarden 2011, Feldman et al. 2013). These guarantees hold even when the auctions are repeatedly executed and players use no-regret learning algorithms. Unfortunately, off-the-shelf no-regret algorithms for these auctions are computationally inefficient as the number of actions is exponential. We show that this obstacle is insurmountable: there are no polynomial-time no-regret algorithms for SiSPAs, unless RP⊇ NP, even when the bidders are unit-demand. Our lower bound raises the question of how good outcomes polynomially-bounded bidders may discover in such auctions. To answer this question, we propose a novel concept of learning in auctions, termed "no-envy learning." This notion is founded upon Walrasian equilibrium, and we show that it is both efficiently implementable and results in approximately optimal welfare, even when the bidders have fractionally subadditive (XOS) valuations (assuming demand oracles) or coverage valuations (without demand oracles). No-envy learning outcomes are a relaxation of no-regret outcomes, which maintain their approximate welfare optimality while endowing them with computational tractability. Our results extend to other auction formats that have been studied in the literature via the smoothness paradigm. Our results for XOS valuations are enabled by a novel Follow-The-Perturbed-Leader algorithm for settings where the number of experts is infinite, and the payoff function of the learner is non-linear. This algorithm has applications outside of auction settings, such as in security games. Our result for coverage valuations is based on a novel use of convex rounding schemes and a reduction to online convex optimization.

Efficient Algorithms for Adversarial Contextual Learning

33rd International Conference on Machine Learning, ICML'16
Best Spotlight Talk award at 10th Annual Machine Learning Symposium


We provide the first oracle efficient sublinear regret algorithms for adversarial versions of the contextual bandit problem. In this problem, the learner repeatedly makes an action on the basis of a context and receives reward for the chosen action, with the goal of achieving reward competitive with a large class of policies. We analyze two settings: i) in the transductive setting the learner knows the set of contexts a priori, ii) in the small separator setting, there exists a small set of contexts such that any two policies behave differently in one of the contexts in the set. Our algorithms fall into the follow the perturbed leader family \cite{Kalai2005} and achieve regret O(T^(3/4) \sqrt{K log(N)}) in the transductive setting and O(T^(2/3)d^(3/4)K\sqrt{log(N)}) in the separator setting, where K is the number of actions, N is the number of baseline policies, and d is the size of the separator. We actually solve the more general adversarial contextual semi-bandit linear optimization problem, whilst in the full information setting we address the even more general contextual combinatorial optimization. We provide several extensions and implications of our algorithms, such as switching regret and efficient learning with predictable sequences.


Game-theoretic models relevant for computer science applications usually feature a large number of players. The goal of this paper is to develop an analytical framework for bounding the price of anarchy in such models. We demonstrate the wide applicability of our framework through instantiations for several well-studied models, including simultaneous single-item auctions, greedy combinatorial auctions, and routing games. In all cases, we identify conditions under which the POA of large games is much better than that of worst-case instances. Our results also give new senses in which simple auctions can perform almost as well as optimal ones in realistic settings.

Fast Convergence of Regularized Learning in Games

29th Annual Conference on Neural Information Processing Systems, NIPS'15
Best Paper Award


We show that natural classes of regularized learning algorithms with a form of recency bias achieve faster convergence rates to approximate efficiency and to coarse correlated equilibria in multiplayer normal form games. When each player in a game uses an algorithm from our class, their individual regret decays at O(T^{−3/4}), while the sum of utilities converges to an approximate optimum at O(T^{−1})--an improvement upon the worst case O(T^{−1/2}) rates. We show a black-box reduction for any algorithm in the class to achieve O~(T^{−1/2}) rates against an adversary, while maintaining the faster rates against algorithms in the class. Our results extend those of [Rakhlin and Shridharan 2013] and [Daskalakis et al. 2014], who only analyzed two-player zero-sum games for specific algorithms.


The main goal of this paper is to develop a theory of inference of player valuations from observed data in the generalized second price auction without relying on the Nash equilibrium assumption. Existing work in Economics on inferring agent values from data relies on the assumption that all participant strategies are best responses of the observed play of other players, i.e. they constitute a Nash equilibrium. In this paper, we show how to perform inference relying on a weaker assumption instead: assuming that players are using some form of no-regret learning. Learning outcomes emerged in recent years as an attractive alternative to Nash equilibrium in analyzing game outcomes, modeling players who haven't reached a stable equilibrium, but rather use algorithmic learning, aiming to learn the best way to play from previous observations. In this paper we show how to infer values of players who use algorithmic learning strategies. Such inference is an important first step before we move to testing any learning theoretic behavioral model on auction data. We apply our techniques to a dataset from Microsoft's sponsored search ad auction system.


We consider common-value hybrid auctions among two asymmetrically informed bidders, where the winning bidder pays his bid with some positive probability k and the losing bid otherwise. Under the assumption of discrete and affiliated signals, we give an explicit characterization of the (unique) equilibrium, based on a simple recurrence relation. We show that equilibrium revenue is decreasing in k, and that the limit second-price equilibrium that is selected entails extensive free-riding by uninformed bidders. We further show that the Linkage Principle can fail to hold even in a pure first-price auction with binary signals: public revelation of a signal to both bidders may decrease the auctioneer's revenue. Lastly, we analyze the effects of public acquisition of additional information on bidder utilities and exhibit cases in which both bidders strictly prefer for a specific bidder to receive additional information.

Bayesian Incentive-Compatible Bandit Exploration

16th ACM Conference on Economics and Computation, Portland, OR, USA, June 15-19, 2015, EC'15


Individual decision-makers consume information revealed by the previous decision makers, and produce information that may help in future decisions. This phenomenon is common in a wide range of scenarios in the Internet economy, as well as in other domains such as medical decisions. Each decision-maker would individually prefer to "exploit": select an action with the highest expected reward given her current information. At the same time, each decision-maker would prefer previous decision-makers to "explore", producing information about the rewards of various actions. A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance the exploration and exploitation so as to maximize social welfare. We formulate this problem as a multi-armed bandit problem (and various generalizations thereof) under incentive-compatibility constraints induced by the agents' Bayesian priors. We design an incentive-compatible bandit algorithm for the social planner whose regret is asymptotically optimal among all bandit algorithms (incentive-compatible or not). Further, we provide a black-box reduction from an arbitrary multi-arm bandit algorithm to an incentive-compatible one, with only a constant multiplicative increase in regret. This reduction works for very general bandit setting that incorporate contexts and arbitrary auxiliary feedback.

Composable and efficient mechanisms

44th Symposium on Theory of Computing Conference, STOC'13
Price of Anarchy in Auctions: [ Slide Show | PDF Slides ]
Tutorial on PoA in Auctions at WINE 2013 with Jason Hartline: [ Slide Show | PDF Slides ]


We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome in equilibrium both in the full information setting and in the Bayesian setting with uncertainty about participants, as well as in learning outcomes. Our main result is to show that such mechanisms compose well: smoothness locally at each mechanism implies efficiency globally. For mechanisms where good performance requires that bidders do not bid above their value, we identify the notion of a weakly smooth mechanism. Weakly smooth mechanisms, such as the Vickrey auction, are approximately efficient under the no-overbidding assumption. Similar to smooth mechanisms, weakly smooth mechanisms behave well in composition, and have high quality outcome in equilibrium (assuming no overbidding) both in the full information setting and in the Bayesian setting, as well as in learning outcomes. In most of the paper we assume participants have quasi-linear valuations. We also extend some of our results to settings where participants have budget constraints.

Working Papers

Inference on Auctions with Weak Assumptions on Information
Vasilis Syrgkanis, Elie Tamer, Juba Ziani

A Proof of Orthogonal Double Machine Learning with Z-Estimators
Vasilis Syrgkanis

Dynamic Information Acquisition from Multiple Sources
Annie Liang, Xiaoseng Mu, Vasilis Syrgkanis

Simple vs Optimal Mechanisms in Auctions with Convex Payments
Amy Greenwald, Takehiro Oyakawa, Vasilis Syrgkanis

Empirical Estimation of User Behavior in Sponsored Search
Matt Goldman, Justin Rao, Vasilis Syrgkanis, working paper, 2015

Pricing Queries Approximately Optimally
Vasilis Syrgkanis, Johannes Gehrke

Price of Stability in Games of Incomplete Information
Vasilis Syrgkanis, under submission


The Price of Anarchy in Auctions
Tim Roughgarden, Vasilis Syrgkanis, Eva Tardos
Journal of Artificial Intelligence Research, May 2017

Algorithmic Game Theory and Econometrics
Vasilis Syrgkanis, SIGecom Exchanges, June 2015

The Dining Bidder Problem: a la russe et a la francaise
Renato Paes Leme, Vasilis Syrgkanis, Eva Tardos, SIGecom Exchanges, December 2012
A review of recent results in simultaneous and sequential item auctions.


Efficiency of Mechanisms in Complex Markets
PhD Thesis, Cornell University, Computer Science Department, August 2014

Equilibria in Congestion Game Models: Existence, Complexity and Efficiency
Vasilis Syrgkanis
Undergraduate Diploma Thesis, National Technical University of Athens, July 2009 (title is in Greek but main content, p. 6 and on, is in English)

Professional Service

Senior Program Committee: EC 2017
Organizing Committee: 2nd Workshop on Algorithmic Game Theory and Data Science 2016, 3nd Workshop on Algorithmic Game Theory and Data Science 2017, NIPS17 Workshop on Learning in the Presence of Strategic Behavior
Program Committee: EC 2013, AdAuctions 2014, EC 2015, IJCAI 2015, WINE 2015, AdAuctions 2015, ICML 2016, EC 2016, NIPS 2016, HCOMP 2016, WINE 2016, SAGT 2017, NIPS 2017, ALT 2018, ICLR 2018
Journal Reviewer: Journal of the ACM, SIAM Journal on Computing, ACM Transactions on Economics and Computation, Journal of Machine Learning Research, IEEE Transactions on Automatic Control