Non-separable utilities are as easy as separable ones -- if they are Leontief-free

Thursday, March 21, 2013 - 2:00pm to 3:00pm
Vijay Vazirani
Georgie Tech

Conventional wisdom has it that computing an equilibrium for a market under non-separable utilities is difficult -- even if restricted to the piecewise-linear, concave (PLC) case, for which irrationality sets in and no fast algorithms are known. In contrast, recent results have shown that markets under separable PLC utilities have rational equilibria and admit practical algorithms.

Using the powerful machinery of LCP formulations and complementary pivot algorithms, we show that a subclass of non-separable PLC, which we call Leontief-free PLC, is just as easy as separable PLC. Furthermore, adding even one Leontief-type constraint renders it difficult.

The same applies for production, where by separable PLC production we mean using one raw good to produce one finished good in a piecewise-linear, concave manner.

Based on joint work with Jugal Garg and Ruta Mehta.