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 teaching 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: ndevanur[AT]gmail[DOT]com
Algorithmic Game Theory Arrange by Default
    Computation of Equilibria
      Centralized Algorithms
      • Fisher Markets and Convex Programs [pdf| Show/Hide Abstract]
        Working Paper
      • Market Equilibrium with Transaction Costs [pdf| Show/Hide Abstract]
        with Sourav Chakraborty and Chinmay Karande. In Proc. WINE 2010
      • Market Equilibria in Polynomial time for fixed number of goods or agents [pdf | Show/Hide Abstract]
        with Ravi Kannan. In Proc. FOCS 2008.
      • The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness results [pdf | Show/Hide Abstract]
        with Vijay V. Vazirani. In Proc. STOC 2004.
      • 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.
      • 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
      • An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case [pdf | Show/Hide Abstract]
        with Vijay Vazirani. In Proc. FSTTCS 2003.
      Market Dynamics
      • New Convex Programs and Distributed Algorithms for Fisher Markets with Linear and Spending Constraint Utilities [pdf| Show/Hide Abstract]
        with Benjamin Birnbaum and Lin Xiao. Working paper
      • Local Dynamics in Bargaining Networks via Random-Turn Games [pdf| Show/Hide Abstract]
        with Elisa Celis and Yuval Peres. In Proc. WINE 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
    Mechanism Design
    • The Price of Truthfulness for Pay-Per-Click Auctions [pdf | Show/Hide Abstract]
      with Sham Kakade. 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.
    • An Online Multi-unit Auction with Improved Competitive Ratio [pdf | Show/Hide Abstract]
      with Sourav Chakraborty. In Proc. WINE 2009.
    • 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
    Bargaining Networks
    • Local Dynamics in Bargaining Networks via Random-Turn Games [pdf| Show/Hide Abstract]
      with Elisa Celis and Yuval Peres. In Proc. WINE 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
    Miscellaneous
    • 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
    • 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
    • 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
Algorithms
  • 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
  • The Adwords Problem: Online Keyword Matching with Budgeted Bidders under Random Permutations [pdf | Show/Hide Abstract]
    with Tom Hayes. In Proc. ACM EC 2009.
  • 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. )
  • 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.
  • 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 complexity of Hilbert's 17th problem [pdf | Show/Hide Abstract]
    with Richard J. Lipton and Nisheeth Vishnoi. In Proc. FSTTCS 2004.