Vijay Vazirani has spent a considerable amount of time in the last few years on developing combinatorial algorithms for problems (mostly involving market equilibria) that can be solved by general convex programming. In this guest post Vijay talks about the motivation for this:
Since convex programs can be solved efficiently using “continuous” methods, such as ellipsoid or interior point methods, why bother designing extremely ellaborate and difficult combinatorial algorithms for them? Let me propose the following thought experiment (it is not a difficult one!) to bring home the point. Think of a world in which these continuous methods were developed in the 1920’s and ever since, problems such as network flow and matching, which can be cast as linear programs, were routinely solved using such methods. Then in 1956, Ford and Fulkerson propose their beautiful combinatorial algorithm for max-flow and it is immediately trashed, since it is “needlessly complicated and difficult”. Edmonds’ matching algorithm, which is proposed in 1965, meets a similar fate. As a consequence, in this world, combinatorial optimization is a stillborn field. How much of a tragedy would that be? After all, matchings and max-flows could still be computed efficiently …
Observe that the continuous methods solve the instance at hand, without giving any insight into the entire problem from which the instance arose. In fact, such methods do not even need to be told the problem from which the instance arose — all that is needed is the specific linear or convex program for the given instance. So, in this world, theoreticians (if they can be called that) would not have the deep insights we have into the structure of numerous fundamental combinatorial problems. And you can gauge what kind of a “theory” of algorithms this world would have!
I believe that if our research community does not pursue the design of combinatorial algorithms for convex programs, our world would also lose out on a beautiful, deep theory. My lone work on this topic, some joint with my students, is too insignificant an effort in comparison with the ideas, structures and methods that still need to be unearthed. My inability to convince people so far, on what had seemed to me an obvious direction worth pursuing, is the reason for this post.
The convex programs I have studied over the last 8 years arose in AGT, in the context of market equilibria and Nash bargaining games. The theory so far has started forming around a remarkable convex program given by Eisenberg and Gale in 1959. In order to solve these nonlinear programs combinatorially, the classical primal-dual algorithm design paradigm had to be extended from its previous setting of LP-duality theory to the more general setting of convex programs and KKT conditions. The algorithms are non-trivial and require substantial structural insights. In turn, these structural insights provide a starting point for tackling more general problems. To get an idea of how rich the theory is already, consider the following episode. A few months ago, Gagan Goel and I started designing a combinatorial algorithm for a certain Nash bargaining game under peicewise-linear, concave utility functions; the linear case had already been solved. Out of the structural insights gained, we managed to define a new, natural market that models perfect price discrimination and in which buyers have peicewise-linear, concave utility functions (the usual Fisher and Arrow-Debreu markets were recently shown to be PPAD-complete under these utility functions). The equilibrium of our market is captured by a generalization of the Eisenberg-Gale program and is polynomial time computable — even combinatorially. In addition, the convex program yields very simple proofs of both welfare theorems for this market!
It is important to point out immediately that my work is limited to a very thin sliver of convex programs — depite their nonlinearity, these programs admit rational solutions. How about attacking more general classes of convex programs combinatorially, perhaps via approximation algorithms, since they won’t admit rational solutions? Considering how extensive the theory is already, I believe it cannot exist in islolation and is indicative of the tip of an iceberg. We need a lot more smart people to ponder on these issues to find the rest of the iceberg!