Nikhil R Devanur
We are hiring! Please apply.
Bio: Nikhil R. Devanur is a senior researcher and manager of the Algorithms group in Microsoft Research, Redmond. He is interested in what he calls Automated Economics, which studies the question of how technology can be used to improve the efficiency of economic systems. His other interest is in Algorithms: he is interested in designing algorithms that are faster, simpler, work online or in a distributed fashion, for some of the basic combinatorial optimization problems.
Mentees (Interns and Postdocs)
News
Manuscripts
Selected Recent Publications
2018
  • A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications [arXiv pdf| Show/Hide Abstract].
    with Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod. In Proc. SODA 2018.
  • Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination [arXiv pdf| Show/Hide Abstract].
    with Balasubramanian Sivan and Vasilis Syrgkanis. In Proc. SODA 2018.
  • Bubble Execution: Resource-aware Reliable Analytics at Cloud Scale. [pdf| Show/Hide Abstract].
    with Zhicheng Yin, Jin Sun, Ming Li, Jaliya Ekanayake, Haibo Lin, Marc Friedman, Jose A. Blakeley and Clemens A. Szyperski. In Proc. VLDB 2018.
2017
  • Stability of Service under Time-of-Use Pricing [ arXiv pdf | Show/Hide Abstract]
    with Shuchi Chawla, Alexander E. Holroyd, Anna Karlin, James Martin and Balasubramanian Sivan. In Proc. STOC 2017
  • Truth and Regret in Online Scheduling [ arXiv pdf | Show/Hide Abstract]
    with Shuchi Chawla, Janardhan Kulkarni, Rad Niazadeh. In Proc. EC 2017
  • Convex Program Duality, Fisher Markets, and Nash Social Welfare [arXiv pdf | Show/Hide Abstract].
    with Richard Cole, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani and Sadra Yazdanbod. In Proc. EC 2017
  • Optimal Multi-Unit Mechanisms with Private Demands [ arXiv pdf | Show/Hide Abstract]
    with Nima Haghpanah, Christos-Alexandros Psomas. In Proc. EC 2017
  • Online Auctions and Multi-scale Online Learning [ Show/Hide Abstract]
    with Sebastien Bubeck, Zhiyi Huang and Rad Niazadeh. In Proc. EC 2017
  • The optimal mechanism for selling to a budget constrained buyer: the general case [ Show/Hide Abstract]
    with Matt Weinberg. In Proc. EC 2017
2016
  • 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.
2015
  • 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
2014
  • 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
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
  • A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems.
    with Janardhan Kulkarni. In Proc. SPAA 2018.
  • 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.