Nonlinear Equilibrium vs. Linear Programming for resource allocation problems.

 For three quarters of a century Linear Programming (LP) was the main tool for solving resource allocation problems (RAP)- one of the main problem in economics.

In 1975 L. V. Kantorovich and T. C. Koopmans shared the Nobel Prize in Economics Nonlinear Equilibrium vs. Linear Programming for resource allocation problems.“for their contributions to the theory of optimum allocation of limited resources."

When LP is used for RAP the prices for goods and the resource availability are given a priori and independent on the production output and prices for the resources. It often leads to solutions, which are not practical, because they contradict to the basic market law of supply and demand.

We consider an alternative to LP approach to RAP, which is based on Nonlinear Equilibrium (NE). The NE is a generalisation of Walras-Wald equilibrium, which is equivalent to J Nash equilibrium in n-person concave game.

NE eliminates the basic drawbacks of LP. Finding NE is equivalent to solving a variation inequality (VI) on the Cartesian product of the primal and dual non negative octants, projection on which is a very simple operation. For solving the VI we consider two methods: projected pseudo-gradient (PPG) and extra pseudo-gradient (EPG), for which projection is the main operation at each step.

We established convergence, proved global Q-linear rate and estimated complexity of both methods under various assumptions on the input data.

Both PPG and EPG can be viewed as pricing mechanisms for establishing economic equilibrium.