Nikhil R Devanur
I am a researcher in the theory group in Microsoft Research, Redmond.
I am interested in what I call Automated Economics, which studies the question of how technology can be used to improve the efficiency of economic systems. My other interest is in Algorithms: I am interested in designing algorithms that are faster, simpler, work online or in a distributed fashion, for some of the basic combinatorial optimization problems.
I am the Program Committee Chair of APPROX 2014 . Deadline to submit has passed. The list of accepted papers will be out on June 7th.

I am part of the team that is running a prediction market for Indian elections, 2014 . Do try it out if you are interested in these elections or in prediction markets.

I organized a workshop on Online matching at STOC in Palo Alto on June 1st 2013.

I gave a tutorial on Prior-Robust Optimization at EC in Philadelphia on June 16 2013.

I taught a course on online algorithms at UW this winter quarter, 2013.
Contact Information
One Microsoft way
Redmond, WA 98052
Ph:(work) 425.538.7509
Ph:(cell) 312.613.2773
Email: nikdev[AT]microsoft[DOT]com

Manuscripts
  • A new auction format for IPL players auctions [pdf].
  • Draft Auctions [pdf| Show/Hide Abstract]
    with Jamie Morgenstern and Vasilis Syrgkanis.
  • Fisher Markets and Convex Programs [pdf| Show/Hide Abstract].
  • DBLP page
  • Papers on Arxiv
Selected Recent Publications
2014
  • Bandits with concave rewards and convex knapsacks [pdf | Show/Hide Abstract]
    with Shipra Agrawal. In Proc. ECM EC 2014
  • Removing Arbitrage from Wagering Mechanisms
    with Yiling Chen, David Pennock, Jennifer Wortman Vaughan. In Proc. ECM EC 2014
  • Primal dual gives optimal energy efficient online algorithms [pdf | Show/Hide Abstract]
    with Zhiyi Huang. In Proc. SODA 2014
2013
  • Whole-page Optimization and Submodular Welfare Maximization with Online Bidders [pdf | Show/Hide Abstract]
    with Zhiyi Huang, Nitish Korula, Vahab Mirrokni and Qiqi Yan. In Proc. ACM EC 2013
  • Budget Smoothing for Internet Ad Auctions: A Game Theoretic Approach [pdf | Show/Hide Abstract]
    with Deeparnab Chakrabarty, Denis Charles, Max Chickering and Lei Wang. In Proc. ACM EC 2013
  • Prior-free Auctions for Budgeted Agents [pdf | Show/Hide Abstract]
    with Bach Q. Ha and Jason D. Hartline. In Proc. ACM EC 2013
  • Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue [pdf | Show/Hide Abstract]
    with Yun Kuen Cheung and Richard Cole. In Proc. STOC 2013
  • Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching [pdf | Show/Hide Abstract]
    with Kamal Jain and Bobby Kleinberg. In Proc. SODA 2013
2012
  • Asymptotically Optimal Algorithm for Stochastic Adwords [pdf | Show/Hide Abstract]
    with Balasubramanian Sivan and Yossi Azar. In Proc. EC 2012
  • Online Matching with Concave Returns [pdf | Show/Hide Abstract]
    with Kamal Jain. In Proc. STOC 2012
2011
  • Prior-Independent Multi-parameter Mechanism Design [pdf | Show/Hide Abstract]
    with Jason D. Hartline, Anna R. Karlin, C. Thach Nguyen In Proc. WINE 2011
  • Online Algorithms with Stochastic Input [pdf ]
    In ACM SIGEcom Exchanges, Vol. 10, No. 2, June 2011, Pages 40- 49.
  • Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems [pdf | Show/Hide Abstract]
    with Kamal Jain, Balasubramanian Sivan and Christopher A. Wilkens In Proc. ACM EC 2011
  • Distributed Algorithms via Gradient Descent for Fisher Markets [pdf | Show/Hide Abstract]
    with Benjamin Birnbaum and Lin Xiao. In Proc. ACM EC 2011
2010
  • Fast Algorithms for Finding Matchings in Lopsided Bipartite Graphs with Applications to Display Ads [pdf | Show/Hide Abstract]
    with Denis Charles, Max Chickering, Kamal Jain and Manan Sanghi. In Proc. ACM EC 2010
  • Monotonicity in Bargaining Networks [pdf | Show/Hide Abstract]
    with Yossi Azar, Kamal Jain and Yuval Rabani. In Proc. SODA 2010
2009
  • Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks [pdf | Show/Hide Abstract]
    with Yossi Azar, Benjamin Birnbaum, L. Elisa Celis and Yuval Peres. In Proc. FOCS 2009
  • The Price of Truthfulness for Pay-Per-Click Auctions [pdf | Show/Hide Abstract]
    with Sham Kakade. In Proc. ACM EC 2009.
  • The Adwords Problem: Online Keyword Matching with Budgeted Bidders under Random Permutations [pdf | Show/Hide Abstract]
    with Tom Hayes. In Proc. ACM EC 2009.
  • Limited and Online Supply and the Bayesian foundations of prior-free mechanism design [pdf | Show/Hide Abstract]
    with Jason Hartline. In Proc. ACM EC 2009.
Other Publications
  • Cloud Scheduling with Setup Cost [pdf| Show/Hide Abstract]
    with Yossi Azar, Naama Ben-Aroya and Navendu Jain. In Proc. SPAA 2013
  • An O(n log n) Algorithm for a Load Balancing Problem on Paths [pdf| Show/Hide Abstract]
    with Uri Feige. In Proc. WADS 2011
  • Real-Time Bidding Algorithms for Performance-Based Display Ad Allocation [pdf| Show/Hide Abstract]
    with Ye Chen, Pavel Berkhin and Bo Anderson . (To appear) In Proc. KDD 2011
  • Local Dynamics in Bargaining Networks via Random-Turn Games [pdf| Show/Hide Abstract]
    with Elisa Celis and Yuval Peres. In Proc. WINE 2010
  • Market Equilibrium with Transaction Costs [pdf| Show/Hide Abstract]
    with Sourav Chakraborty and Chinmay Karande. In Proc. WINE 2010
  • An Online Multi-unit Auction with Improved Competitive Ratio [pdf | Show/Hide Abstract]
    with Sourav Chakraborty. In Proc. WINE 2009.
  • A Computational Theory of Awareness and Decision Making [pdf | Show/Hide Abstract]
    with Lance Fortnow. In Proc. Theoretical Aspects of Rationality and Knowledge, TARK 2009
  • Market Equilibria in Polynomial time for fixed number of goods or agents [pdf | Show/Hide Abstract]
    with Ravi Kannan. In Proc. FOCS 2008.
  • New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem. [pdf | Show/Hide Abstract]
    with Deeparnab Chakrabarty, and Vijay Vazirani. To appear in Math Programming (Series A) Volume 122, Number 2 (April 2010). (Preliminary version in IPCO 2008. )
  • On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach [pdf | Show/Hide Abstract]
    with V. Arvind and Christine Cheng. In SIAM Journal on Discrete Mathematics, vol. 22, no. 4 (October 2008), pp. 1297-1324.
  • On the Equivalence of Competitive and Submodular markets [pdf | Show/Hide Abstract]
    with Deeparnab Chakrabarty. In Operations Research Letters, vol. 37, no. 3, pp. 155 - 158, 2009. Prelim. version in Proc. WINE 2007
  • Computing Market Equilibrium: Beyond Weak Gross Substitutes [pdf | Show/Hide Abstract]
    with Chinmay Karande. In Proc. WINE 2007
  • New results on Rationality and Strongly Poylnomial Solvability in Eisenberg-Gale markets [pdf | Show/Hide Abstract]
    with Deeparnab Chakrabarty and Vijay Vazirani. In Proc. WINE 2006
  • Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems [pdf | Show/Hide Abstract]
    with Subhash A. Khot, Rishi Saket and Nisheeth K. Vishnoi. In Proc. STOC 2006.
  • Price of Anarchy, Locality Gap, and a Network Service Provider Game [pdf | Show/Hide Abstract]
    with Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Amin Saberi, and Vijay V. Vazirani. In Proc. WINE 2005
  • On the complexity of Hilbert's 17th problem [pdf | Show/Hide Abstract]
    with Richard J. Lipton and Nisheeth Vishnoi. In Proc. FSTTCS 2004.
  • The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness results [pdf | Show/Hide Abstract]
    with Vijay V. Vazirani. In Proc. STOC 2004.
  • An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case [pdf | Show/Hide Abstract]
    with Vijay Vazirani. In Proc. FSTTCS 2003.
  • Strategyproof cost-sharing Mechanisms for Set Cover and Facility Location Games [pdf | Show/Hide Abstract]
    with Milena Mihail and Vijay Vazirani. Decision Support Systems 39 (March 2005), pp 11--22. Prelim. version in Proc. ACM EC 2003
  • Market Equilibrium via a Primal-Dual-Type Algorithm [pdf | Show/Hide Abstract]
    with Christos H. Papadimitriou, Amin Saberi and Vijay V.Vazirani. In The Journal of the ACM, vol. 55, no. 5 (October 2008), pp 1--18. Prelim version appeared in FOCS 2002.