Nonlinear Equilibrium for Resource Allocation Problems (2015)

We consider Nonlinear Equilibrium (NE) for the optimal allocation of limited resources. The NE is a generalization of Walras-Wald equilibrium, which is equivalent to J. Nash equilibrium in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -person concave games. Finding NE is equivalent to solving a variational inequality (VI) with a monotone and smooth operator on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Omega equals double-struck upper R Subscript plus Superscript n Baseline circled-times double-struck upper R Subscript plus Superscript m"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal"> Ω </mml:mi> <mml:mo>=</mml:mo> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>n</mml:mi> </mml:msubsup> <mml:mo> ⊗ </mml:mo> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>m</mml:mi> </mml:msubsup> </mml:mrow> <mml:annotation encoding="application/x-tex">\Omega = \mathbb {R}^n_+ \otimes \mathbb {R}^m_+</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Projection on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Omega"> <mml:semantics> <mml:mi mathvariant="normal"> Ω </mml:mi> <mml:annotation encoding="application/x-tex">\Omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a very simple procedure; therefore, our main focus is two methods for which the projection on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Omega"> <mml:semantics> <mml:mi mathvariant="normal"> Ω </mml:mi> <mml:annotation encoding="application/x-tex">\Omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the main operation. Both pseudo-gradient projection (PGP) and extra pseudo-gradient (EPG) methods require <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis n squared right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(n^2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> operations per step, because in both cases the main operation per step is matrix by vector multiplication. We prove convergence, establish global Q-linear rate and estimated computational complexity for both the PGP and EPG methods under various assumption on the input data. Both methods can be viewed as pricing mechanisms for establishing economic equilibrium. On the other hand, they are primal-dual decomposition methods.