Market equilibrium computation
Market equilibrium computation has been studied under various assumptions regarding the agents' utility functions.
Utilities that are piecewise-linear and concave are often called PLC; if they are also separable, then they are called SPLC.
There is an algorithm that solves this problem in weakly polynomial time.