I am a Researcher at Microsoft Research, New England. I received my Ph.D. from the Computer Science Department of Cornell University, where I had the privilege to be advised by Eva Tardos and then spent two years as a postdoc researcher at the Microsoft Research, NYC Lab, where I was part of the Algorithmic Economics and the Machine Learning group. I defended my Ph.D. thesis on Efficiency of Mechanisms in Complex Markets in August 2014. Prior, I obtained my diploma in Electrical Engineering and Computer Science at the National Technical University of Athens, Greece.

My research interests lie at the intersection of the areas of algorithms, game theory, auction theory and mechanism design, econometrics, data science, machine learning theory and computational complexity of games. On the application side, I am interested in the game theoretic foundations of electronic markets and electronic platforms where incentives are a primary aspect of their functionality, with an emphasis on the design and analysis of simple incentive schemes and mechanisms.

[ Resume | Research Statement ] [ DBLP | Google Scholar | Arxiv | SSRN ]

[Contact]

641 Avenue of the Americas
New York, NY, 10011
Email: vasy [at] microsoft.com

News

Representative Publications


Learning in Auctions: Regret is Hard, Envy is Easy

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

Abstract

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

Abstract

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.

The Price of Anarchy in Large Games

48th Annual Symposium on the Theory of Computing, STOC'16

Abstract

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

Abstract

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.

Econometrics for Learning Agents

16th ACM Conference on Economics and Computation, EC'15
Best Paper Award

Abstract

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.

Abstract

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

Abstract

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 ]

Abstract

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


Improved Regret Bounds for Adversarial Contextual Bandits
Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, Robert E. Schapire

Robust Data-Driven Efficiency Guarantees in Auctions
Darrell Hoy, Denis Nekipelov, Vasilis Syrgkanis
Preliminary version at 1st Workshop on Algorithmic Game Theory and Data Science, in conjunction with EC’15

Multi-parameter Auctions with Online Supply
Nikhil Devanur, Balasubramanian Sivan, Vasilis Syrgkanis

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

Optimal Auctions with Convex Perceived Payments
Amy Greenwald, Takehiro Oyakawa, Vasilis Syrgkanis

Pricing Queries Approximately Optimally
Vasilis Syrgkanis, Johannes Gehrke

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

Surveys

Price of Anarchy in Auctions
Tim Roughgarden, Vasilis Syrgkanis, Eva Tardos
Invited survey to the Journal of Artificial Intelligence, under preparation, 2015

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.

Theses

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

Program Committee: EC 2013, AdAuctions 2014, EC 2015, IJCAI 2015, WINE 2015, AdAuctions 2015, ICML 2016, EC 2016, NIPS 2016, WINE 2016
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