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 organizing an ACM EC Workshop on Economic Aspects of Cloud Computing. Submission deadline is May 17th.
Mentees (Interns and Postdocs)
Selected Recent Publications
  • Linear Contextual Bandits with Knapsacks [ NIPS pdf | Supplement | Show/Hide Abstract]
    with Shipra Agrawal. In Proc. NIPS 2016
  • The Sample Complexity of Auctions with Side Information [arXiv pdf| Show/Hide Abstract]
    with Zhiyi Huang and Christos-Alexandros Psomas. In Proc. STOC 2016
  • A Duality Based Unified Approach to Bayesian Mechanism Design [pdf| Show/Hide Abstract]
    with Yang Cai and Matt Weinberg. In Proc. STOC 2016
  • An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives [arXiv pdf| Show/Hide Abstract]
    with Shipra Agrawal and Lihong Li. In Proc. COLT 2016
  • ProjecToR: Agile Reconfigurable Datacenter Interconnect [ Show/Hide Abstract]
    with M. Ghobadi, R. Mahajan, A. Phanishayee, H. Rastegarfar, P. Blanche, M. Glick, D. Kilper, J. Kulkarni and G. Ranade. In Proc. SIGCOMM 2016
  • Multi-Score Position Auctions [pdf| Show/Hide Abstract]
    with Denis X. Charles and Balasubramanian Sivan. In Proc. WSDM 2016.
  • Simple Pricing Schemes For Consumers With Evolving Values [pdf| Show/Hide Abstract]
    with Shuchi Chawla, Anna Karlin and Balasubramanian Sivan. In Proc. SODA 2016.
  • Speed Scaling in the Non-clairvoyant Model [pdf| Show/Hide Abstract]
    with Yossi Azar, Zhiyi Huang and Debmalya Panigrahi. In Proc. SPAA 2015. Winner of the Best Paper award.
  • Simple Auctions with Simple Strategies [pdf| Show/Hide Abstract]
    with Jamie Morgenstern, Vasilis Syrgkanis and Matt Weinberg. In Proc. EC 2015
  • Revenue Maximization and Ex-Post Budget Constraints [pdf| Show/Hide Abstract]
    with Constantinos Daskalakis and Matt Weinberg. In Proc. EC 2015
  • Fast Algorithms for Online Stochastic Convex Programming [Arxiv pdf |Show/Hide Abstract]
    with Shipra Agrawal. In Proc. SODA 2015
  • Perfect Bayesian Equilibria in Repeated Sales [Arxiv pdf | Show/Hide Abstract]
    with Yuval Peres and Balasubramanian Sivan. In Proc. SODA 2015
  • Budget Constraints in Prediction Markets [pdf| Show/Hide Abstract]
    with Miro Dudik, Zhiyi Huang and Dave Pennock. In Proc. UAI 2015
  • Envy freedom and prior-free mechanism design [JET | Arxiv pdf | Show/Hide Abstract]
    with Jason D. Hartline and Qiqi Yan. In Journal of Economic Theory, 2014
  • Bandits with concave rewards and convex knapsacks [Arxiv pdf | Show/Hide Abstract]
    with Shipra Agrawal. In Proc. ACM EC 2014
  • Removing Arbitrage from Wagering Mechanisms [pdf | Show/Hide Abstract]
    with Yiling Chen, David Pennock, Jennifer Wortman Vaughan. In Proc. ACM EC 2014
  • Primal dual gives optimal energy efficient online algorithms [pdf | Show/Hide Abstract]
    with Zhiyi Huang. In Proc. SODA 2014
  • 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
  • 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
  • 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
  • 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
  • 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
  • A Rational Convex Program for Linear Arrow-Debreu Markets [pdf| Show/Hide Abstract]
    with Jugal Garg and Laszlo A. Vegh .
  • On the Approximation of Submodular Functions [pdf| Show/Hide Abstract]
    with Shaddin Dughmi, Roy Schwartz, Ankit Sharma and Mohit Singh.
  • Sequential Auctions of Identical Items with Budget-Constrained Bidders [pdf| Show/Hide Abstract]
    with Zhiyi Huang and David Malec.
  • 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. 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.