Market equilibrium under piecewise Leontief concave utilities

Leontief is one of the most widely used and extensively studied function in economic modeling, for both production and preferences. However it lacks the desirable property of diminishing returns. In this paper, we consider piecewise Leontief concave (p-Leontief) utility function which consists of a set of Leontief-type segments with decreasing returns and an upper limit on the utility on each segment, and study complexity of computing equilibria in both Fisher and exchange market models. Leontief is a special case of p-Leontief with exactly one segment with no upper limit. While it is well known that equilibrium computation in Fisher markets with Leontief utilities is polynomial time, in case of p-Leontief, even with two segments, we show that the problem is PPAD-hard. On the other hand for the case when coefficients across segments are scaled versions of each other, we give a polynomial time algorithm. As a corollary, we obtain a non-trivial new class of exchange markets with Leontief utilities where an equilibrium can be computed in a polynomial time, whereas the general problem is known to be PPAD-hard. For p-Leontief exchange markets with pairing economy we show that equilibria are rational and we obtain a simplex-like algorithm to compute one using the classic Lemke–Howson scheme, thereby extending the results of Ye, TCS 2007, and Codenotti, Saberi, Varadarajan and Ye, SODA 2006 for Leontief to p-Leontief utilities.