Thursday, December 06, 2012

Where is the youth of TCS/Market Eq/Guest Post by Vijay

(Guest post by Vijay Vazirani.)

On
Theory Day on Nov 30, 2012
Vijay Vazirani gave a talk:
New (Practical) Complementary Pivot Algorithms for Market Equilibrium.
He was inspired by the reaction to the talk to write a guest blog
which I present here!

Where is the Youth of TCS?

by Vijay Vazirani

I have always been impressed by the researchers of our community, especially the young researchers -- highly competent, motivated, creative, open-minded ... and yet cool! So it has been disconcerting to note that over the last couple of years, each time I have met Mihalis Yannakakis, I have lamented over the lack of progress on some fundamental problems, and each time the same thought has crossed my mind, ``Where is the youth of TCS? Will us old folks have to keep doing all the work?''

Is the problem lack of information? I decided to test this hypothesis during my talk at NYTD. To my dismay, I found out that there is a lot of confusion out there! By a show of hands, about 90% of the audience said they believed that Nash Equilibrium is PPAD-complete and 3% believed that it is FIXP-complete! I would be doing a disservice to the community by not setting things right, hence this blog post.

First a quick primer on PPAD and FIXP, and then the questions. Ever since Nimrod Megiddo, 1988, observed that proving Nash Equilibrium NP-complete is tantamount to proving NP = co-NP, we have known that the intractability of equilibrium problems will not be established via the usual complexity classes. Two brilliant pieces of work gave the complexity classes of PPAD (Papadimitriou, 1990) and FIXP (Etessami and Yannakakis, 2007), and they have sufficed so far. A problem in PPAD must have rational solutions and this class fully characterizes the complexity of 2-Nash, which has rational equilibria if both payoff matrices have rational entries. On the other hand, 3-Nash, which may have only irrational equilibria, is PPAD-hard; however, its epsilon-relaxation is PPAD-complete. That leaves the question, ``Exactly how hard is 3-Nash?''

Now it turns out that 3-Nash always has an equilibrium consisting of algebraic numbers. So one may wonder if there is an algebraic extension of PPAD that captures the complexity of 3-Nash, perhaps in the style of Adler and Beling, 1994, who considered an extension of linear programs in which parameters could be set to algebraic numbers rather than simply rationals. The class FIXP accomplishes precisely this: it captures the complexity of finding a fixed point of a function that uses the standard algebraic operations and max. Furthermore, Etessami and Yannakakis prove that 3-Nash is FIXP-complete. The classes PPAD and FIXP appear to be quite disparate: whereas the first is contained in NP INTERSECT co-NP, the second lies somewhere between P and PSPACE (and closer to the harder end of PSPACE, according to Yannakakis).

Now the questions (I am sure there are more):

  1. Computing an equilibrium for an Arrow-Debreu market under separable, piecewise-linear concave utilities is PPAD-complete (there is always a rational equilibrium). On the other hand, if the utility functions are non-separable, equilibrium consists of algebraic numbers. Is this problem FIXP-complete? What about the special case of Leontief utilities? If the answer to the latter question is ``yes,'' we will have an interesting demarcation with Fisher markets under Lenotief utilities, since they admit a convex program.
  2. An Arrow-Debreu market with CES utilities has algebraic equilibrium if the exponents in the CES utility functions are rational. Is computing its equilibrium FIXP-complete? Again, its epsilon-relaxation is PPAD-complete.
  3. A linear Fisher or Arrow-Debreu market with piecewise-linear concave production has rational equilibria if each firm uses only one raw good in its production, and computing it is PPAD-complete. If firms use two or more raw goods, equilibria are algebraic numbers. Is this problem FIXP-complete?

23 comments:

  1. When I attend STOC/FOCS/SODA, I often ask "Where are the old folks in TCS?" I guess they are too busy "doing all the work" to present papers in which they do all the work.

    ReplyDelete
  2. They're working on their own insanely hard open problems, on which you old folks are not making any progress either.

    ReplyDelete
  3. Vijay: Look at the perverse incentive system we ("the old folks") have created. Aleksander Madry didn't get a position at a top 5 U.S. institution. In a hyper competitive job market, the young folks want jobs. Apparently it's easier to chase fads than work on hard problems.

    ReplyDelete
  4. There are a number of brilliant people comparable to or better than Aleksander Madry that are not at a top 5 US institution. There are simply not enough jobs in 5 places. Young and old people should follow their interests and strengths, and good thing will happen in time. It is fine for Vijay to passionately advocate for his area/problems but there is no reason to believe that they are more central/important than many others that people are working on.

    ReplyDelete
  5. My impression is the converse: I am more often impressed by the amazing ways in which the youth of TCS continually DO solve those hard problems that have been around a long time - beating Christofides for TSP, finding a lower bound for ACC^0, improving the exponent for matrix multiplication, proving Yannakakis' extended LP formulation conjecture for TSP - to name just a few recent examples.

    ReplyDelete
  6. Anon at 3:07pm: I am not suggesting that these problems are more important than others or that people should drop what they are doing and work on these problems. I am simply lamenting on the massive confusion that is out there due to which most people are not aware of an important new complexity class and its associated open problems. This is not good for the health of our field and you can see the adverse effects it has had already. I am simply trying to do my bit to correct this.

    Anon at 1:11pm: I agree that overemphasis on fads and flimsy results that will not stand the test of time is not the way to build a solid field. Clearly there have to be forays into new directions and ideas, but it is not good to lose sight of depth and quality.

    ReplyDelete
  7. Which recent theory slot at a top 5 university do you think Madry should have gotten?

    ReplyDelete
  8. As a youth across the hall in mathematical logic, the reason TCS turns me off is because there's the appearance that there's nothing really new or exciting, ever.

    As a mathematician, I'm interested in being multidisciplinary-- publishing papers in physics and biology and, well, everywhere. TCS seems to be 100% isolated in that sense. Yes, there are TCS papers published in other fields, but it seems every last one of them is a variation on "(insert something here) is NP-hard".

    You really, really, REALLY need to lose all the acronyms. If you can't think up a good name without resorting to acronyms, that's a sign the object is unworthy of study in the first place.

    You need to stop over-glorifying petty results-- you're the boy who cried wolf, especially here in the blogosphere. How about this. Before you start talking about groundbreaking-this and gamechanging-that, wait til the paper is accepted in a prestigious *NON-TCS* journal. Model yourselves more after Press and Dyson, 2012, "Iterated Prisoner’s Dilemma contains strategies that
    dominate any evolutionary opponent", PNAS. I suppose you laugh at this paper because it doesn't have 30-page proofs stuffed full of excruciatingly painful estimations. And yet, it does what a scientist is supposed to do: adds some real insight into how the universe works. TCS hasn't added any such insight in a very, very, very long time.

    ReplyDelete
  9. +1 Paul Beame

    Adding: PRIMES \in P solved by two undergraduates (okay, plus one "older" guy)

    Amit C

    ReplyDelete
  10. Never seen this before.
    How did it happen?

    ReplyDelete
  11. This is some perverse reasoning (not limited to TCS, by the way) by which a position at a top-5 US university is a "success" while a position at any lower-ranked university (or a top-ranked university in Europe) is a "failure".

    ReplyDelete
  12. Comments section has reached dangerous levels of debate fragmentation and social toxicity. Please gather your belongings, thank Prof. Vazirani for the nice open problems, and leave.

    ReplyDelete
  13. Paul, when is Christofides beaten for TSP? Is it for a special metric or a general metric? There were special metrics for which TSP was already broken, e.g., euclidean matrix. Some recent results broke it for graphical metric, but that is just one other metric.

    Just asking in case I missed some result.

    ReplyDelete
  14. To hosts of this blog: don't you think that anonymous commenting should be banned here? The amount of venom and bitterness is sometimes astounding.

    ReplyDelete
  15. I really don't understand why Vijay is "dismayed" at there being a "lot of confusion". 90 percent said that Nash Equilibrium is PPAD-complete, and as Vijay explains in his post, there are several natural, practical problems in Nash Equilibria that are PPAD-complete, such as an epsilon-relaxation of 3-player Nash. So, unless in his question to the audience Vijay specifically said "How hard is 3-player Nash, not the epsilon relaxation of 3-Nash, but 3-Nash itself?", then I'd say that those 90 percent gave a completely reasonable answer.

    ReplyDelete
  16. Question to Anon at 5:03pm: Is Euclidean TSP NP-complete?

    ReplyDelete
    Replies
    1. Hi Vijay,

      (I'm not anon from 5:03pm.)

      I think Euclidean TSP is NP-complete due to Luca Trevisan's paper "when hamming meets Euclid". But I admit that I am not 100% sure despite being an algorithms person who actually could explain the details of most of the recent progress on graphic TSP results.

      Delete
    2. Not even known to be in NP, due to precision needed for the sum of square roots problem: http://cs.smith.edu/~orourke/TOPP/P33.html. A tricky question!

      Delete
  17. Euclidean TSP is not known to NP-complete, but it's known to be NP-hard. And it's been known a long time before Trevisan's paper. And as Anon 7:42am said, we don't know if the problem is NP-complete because of the tricky problem of dealing with the sum of square roots.
    However, Vijay's question is not tricky. It's a very basic question which should be taught in complexity classes, and PhD students in theory should be familiar with it. And I think this is what Vijay is pointing out. That too many of us don't know some very basic facts from complexity theory, like whether Euclidean TSP is NP-complete, or whether Nash is PPAD-complete.

    ReplyDelete
  18. Vijay, it is possible that much of the confusion rests with others in the Market Eq community, who use different definitions of {\sc Nash} than you do. For example, in both their 2006 STOC paper and a 2009 CACM article, Daskalakis, Goldberg, and Papadimitriou make claims such as the following:

    "We show that finding a Nash equilibrium is complete for a class of problems called PPAD"

    "Indeed, in this paper we describe a proof that {\sc Nash} is PPAD-complete"

    "In this paper we show that {\sc Nash} is PPAD-complete, thus answering the open questions discussed above."

    http://people.csail.mit.edu/costis/journal_ver10.pdf
    http://people.csail.mit.edu/costis/simplified.pdf

    You might also get similar mixed results if you asked the audience whether SDP (semidefinite programming) is in P.

    ReplyDelete
  19. Vijay's post doesn't make the issue quite as clear as it could be. There are two different versions of approximation in our usual bit model of computation. The problem NASH as defined by Papadimitriou, which we now know to be PPAD-complete, asks for a point that is an epsilon-approximate equilibrium. However, though a point is close to being in equilibrium, it does not mean that there is a true equilibrium nearby. The problem considered by Etesammi and Yannakakis is to ask for a point that is within epsilon of a true equilibrium.

    ReplyDelete
  20. 2-NASH is PPAD-complete. "Setting the complexity of computing a Nash Equilibrium" by Chen and Deng.

    ReplyDelete