Vijay V. Vazirani

College of Computing
Georgia Institute of Technology

Ph.D., University of California, Berkeley, 1983
S.B., Massachusetts Institute of Technology, 1979

My Picture

The "Invisible Hand of the Market": Algorithmic Ratification and the Digital Economy, UW TV.
Distinguished Lecture, University of Wisconsin.

Short course on Primal-Dual Algorithms for Rational Convex Programs, University of Waterloo.
Podcast interview about paper

Research Interests

Algorithmic problems in mathematical economics and game theory, design of efficient exact and approximation algorithms, computational complexity theory.
Supported by NSF Grants CCF-0914732 and CCF-1216019, and a Google Research Grant.


My favourite undergraduate course: CS 1050 Honors ``Understanding and Constructing Proofs'' Firewall Article.


Approximation Algorithms, Springer-Verlag, Berlin, 2001.
Preface, Table of Contents, and Chapter 1.

Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors, Cambridge University Press, Cambridge, 2007.
Non-printable version on the web and DIMAP Workshop (Warwick University) introducing the book.

Selected Recent Papers

Algorithms for Markets and Bargaining

  • Allocation of Divisible Goods under Lexicographic Preferences'', with L. Schulman, FSTTCS (2015).

  • ``Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness'', with J. Garg, R. Mehta and S. Yazdanbod, in arXiv, 2015.

  • ``Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Functions'', with J. Garg and R. Mehta, STOC (2014).

  • ``An Incentive Compatible, Efficient Market for Air Traffic Flow Management, with R. Mehta, in arXiv, 2013.

  • ``On Computability of Equilibria in Markets with Production'', with J. Garg, SODA (2014).

  • ``A Complementary Pivot (Practical) Algorithm for Markets Under Separable, Piecewise-Linear Concave Utilities'', with J. Garg, R. Mehta and M. Sohoni, STOC (2012).

  • ``The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game'', Journal of ACM, vol. 59(2) (2012).

  • ``Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities'', with M. Yannakakis, Journal of ACM, vol. 58(3) (2011).

  • ``Equilibrium Pricing of Semantically Substitutable Digital Goods'', with K. Jain, in arXiv, (2012).

  • ``How Many Tiers? Pricing in the Internet Transit Market'', with V. Valancius, C. Lumezanu, N. Feamster and R. Johari, SIGCOMM (2011).

  • ``Non-Separable, Concave Utilities are Easy -- in a Perfect Price Discrimination Market Model'', SIAM J. Discrete Math, 27(1) (2013).

  • ``Rational Convex Programs and Efficient Algorithms for 2-Player Nash and Nonsymmetric Bargaining Games'', SIAM J. Discrete Math, 26(3) (2012).

  • ``A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for it'', with G. Goal, Math of Operations Research, 36: 762-782 (2011).

  • ``Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets'', with N. Megiddo, WINE (2007).

  • ``Spending Constriant Utilities, with Applications to the Adwords Market'', Math of Operations Research 35(2), 2010.

  • ``New Results on Rationality and Strongly Polynomial Solvability in Eisenberg-Gale Markets with Two Agents'', with D. Chakrabarty and N. Devanur, SIAM J. Discrete Math, 24(3), 2010.

  • ``Eisenberg-Gale Markets: Algorithms and Game-Theoretic Properties'', with K. Jain, Games and Economic Behavior, 70(1), 2010.

  • ``Adwords and Generalized Online Matching'', with A. Mehta, A. Saberi and U. Vazirani, Journal of ACM 54(5), 2007.
    Press release by Georgia Tech and a SIAM News article by Sara Robinson on this work.

  • ``Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Procudtion'', with K. Jain and Y. Ye, SODA (2005).

  • ``Rate Control as a Market Equilibrium'', with F. P. Kelly, unpublished note (2002).

  • ``Market Equilibrium via a Primal-Dual Algorithm for a Convex Program'', with N. Devanur, C. Papadimitriou, and A. Saberi, Journal of ACM, vol. 55(5) (2008).

    Other Recent Papers

    1. ``Settling Some Open Problems on 2-Player Symmetric Nash Equilibria'', with R. Mehta and S. Yazdanbod, SAGT (2015).

    2. ``ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria'', with J. Garg, R. Mehta and S. Yazdanbod, ICALP (2015).

    3. ``A Proof of the MV Matching Algorithm'', submitted, 2014.

    4. ``New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem'', with D. Chakrabarty and N. Devanur, Math Programming, Series A (2009).

    5. ``Solvency Games'', with N. Berger, N. Kapur, and L. Schulman, FSTTCS 2008.

    6. ``Design is as Easy as Optimization'', with D. Chakrabarty and A. Mehta, SIAM Journal on Discrete Math, 24(1) (2010).

    7. ``Diversity in Times of Adversity: Probabilistic Strategies in Microbial Survival Games'', with D. Wolf and A. Arkin, Journal of Theoretical Biology, vol. 234, 2005.
      Reviewed in Faculty of 1000.

    8. ``A Microbial Modified Prisoner's Dilemma Game: How Frequency-Dependent
    9. ``The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness Results'', with N. Devanur, STOC 2004.

      Selection can Lead to Random Phase Variation'', with D. Wolf and A. Arkin, Journal of Theoretical Biology, vol. 234, 2005.

    10. ``On the Capacity of Multiple Unicast Sessions in Unidrected Networks'', with K. Jain, R. Yeung and G. Yuval, ISIT 2005.

    11. ``Improved Simulated Annealing Algoirthm for the Permanent and Combinatorial Counting Problems'', with I. Bezakova, D. Stefankovic and E. Vigoda, SIAM Journal of Computing, 37(5) (2008) 1429 -1454.

    12. ``A stochastic process on the hypercube with applications to peer-to-peer networks'', with M. Adler, E. Halperin, and R. M. Karp, Proc. STOC 2003.

    13. ``Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP'', with K. Jain, M. Mahdian, E. Markakis, and A. Saberi, Journal of ACM, 50(6) (2003), 795-824.

    14. ``A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution'', with L. J. Schulman, Combinatorica 25(4) (2005) 465-486.

    15. ``Applications of Approximation Algorithms to Cooperative Games'', with K. Jain, Proc. STOC 2001.

    16. ``Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation'', with K. Jain, Journal of ACM, Vol. 48 (2001) 274-296.

    17. ``A Graph Theoretic Approach to Software Watermarking'', with R. Venkatesan and S. Sinha, 4th International Information Hiding Workshop, Pittsburgh (2001).

    Other Selected Papers: Click here

    Selected Recent Talks

    Two talks for the algorithmically inclined on
    ``Combinatorial Algorithms for Convex Programs Capturing Market Equilibria and Nash Bargaining Solutions''

    Egervary Research Group on Combinatorial Optimization, Budapest, Hungary, September 2009.

    Bellairs Workshop on Algorithmic Game Theory, Barbados, March 2009.

    1) The Problems
    2) Algorithms

    ``Nash Bargaining via Flexible Budget Markets'' talk ppt
    Youtube, Google Research, September 2008.

    ``New Market Models and Algorithms'' talk ppt
    Webcast from Microsoft Research, May 2006.
    ACO Distinguished Lecture, April 2006.

    ``Markets and the Primal-Dual Paradigm'' talk ppt
    Keynote address, DIMAP Workshop, Warwick University, March 2007.
    MS&E Colloquium (Distinguished lecture), Stanford University, May 2007.
    Plenary talk, WINE, San Diego, December 2007.

    Past and Present Ph.D. Students

      Mark Krentel
      Samir Khuller
      Naveen Garg
      Kamal Jain
      Ion Mandoiu
      Amin Saberi
      Aranyak Mehta
      Nikhil R. Devanur
      Deeparnab Chakrabarty
      Gagan Goel
      Chinmay Karande
      Lei Wang
      Pushkar Tripathi
      Sadra Yazdanbod

    Past and Present Postdocs

      Gagan Goel
      Laszlo Vegh
      Ruta Mehta
      Jugal Garg

    Selected Workshops Co-organized

    College of Computing,
    KACB, Room 2142
    266 Ferst Drive
    Georgia Institute of Technology
    Atlanta, Georgia 30332-0765
    Phone: 404-894-5850
    vazirani AT cc DOT gatech DOT edu