IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v17y1971i9p612-634.html
   My bibliography  Save this article

The Linear Complementarity Problem

Author

Listed:
  • B. Curtis Eaves

    (University of California, Berkeley)

Abstract

This study centers on the task of efficiently finding a solution of the linear complementarity problem: Ix - My = q, x \ge 0, y \ge 0, x \perp y. The main results are: (1) It is shown that Lemke's algorithm will solve (or show no solution exists) the problem for M \in L where L is a class of matrices, which properly includes (i) certain copositive matrices, (ii) certain matrices with nonnegative principal minors, (iii) matrices for bimatrix games. (2) If M \in L, if the system Ix - My = q, x \ge 0, y \ge 0 is feasible and nondegenerate, then the corresponding linear complementarity problem has an odd number of solutions. If M \in L and q > 0 then the solution is unique. (3) If for some M and every q \ge 0 the problem has a unique solution then M \in L and the problem has a solution for every q. (4) If M has nonnegative principal minors and if the linear complementarity with M and q has a nondegenerate complementary solution then the solution is unique. (5) If y T My + y T q is bounded below on y \ge 0 then the linear complementarity problem with M and q has a solution and Lemke's algorithm can be used to find such a solution. If, in addition, the problem is nondegenerate, then it has an odd number of solutions. (6) A procedure based on Lemke's algorithm is developed which either computes stationary points for general quadratic programs or else shows that the program has no optimum. (7) If a quadratic program has an optimum and satisfies a nondegeneracy condition then there are an odd number of stationary points.

Suggested Citation

  • B. Curtis Eaves, 1971. "The Linear Complementarity Problem," Management Science, INFORMS, vol. 17(9), pages 612-634, May.
  • Handle: RePEc:inm:ormnsc:v:17:y:1971:i:9:p:612-634
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.17.9.612
    Download Restriction: no

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Van Soest, Arthur & Kooreman, Peter, 1990. "Coherency of the indirect translog demand system with binding nonnegativity constraints," Journal of Econometrics, Elsevier, vol. 44(3), pages 391-400, June.
    2. Bernhard Stengel, 2010. "Computation of Nash equilibria in finite games: introduction to the symposium," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 1-7, January.
    3. Quint, Thomas & Shubik, Martin, 2002. "A bound on the number of Nash equilibria in a coordination game," Economics Letters, Elsevier, vol. 77(3), pages 323-327, November.
    4. Gailly, B. & Installe, M. & Smeers, Y., 2001. "A new resolution method for the parametric linear complementarity problem," European Journal of Operational Research, Elsevier, vol. 128(3), pages 639-646, February.
    5. Govindan, Srihari & Wilson, Robert, 2003. "A global Newton method to compute Nash equilibria," Journal of Economic Theory, Elsevier, vol. 110(1), pages 65-86, May.
    6. repec:spr:joptap:v:169:y:2016:i:3:d:10.1007_s10957-015-0800-2 is not listed on IDEAS
    7. Shu-Cherng Fang & Elmor L. Peterson, 1979. "A Unification and Generalization of the Eaves and Kojima Fixed Point Representations of the Complementarity Problem," Discussion Papers 365, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    8. Anne Balthasar, 2010. "Equilibrium tracing in strategic-form games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 39-54, January.
    9. Herings, P. Jean-Jacques & van den Elzen, Antoon, 2002. "Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games," Games and Economic Behavior, Elsevier, vol. 38(1), pages 89-117, January.
    10. Christian Bidard & Guido Erreygers, 1998. "The number and type of long-term equilibria," Journal of Economics, Springer, vol. 67(2), pages 181-205, June.
    11. repec:spr:joptap:v:170:y:2016:i:1:d:10.1007_s10957-016-0907-0 is not listed on IDEAS
    12. Srihari Govindan & Robert Wilson, 2010. "A decomposition algorithm for N-player games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 97-117, January.
    13. Thomas Quint & Martin Shubik, 1994. "On the Number of Nash Equilibria in a Bimatrix Game," Cowles Foundation Discussion Papers 1089, Cowles Foundation for Research in Economics, Yale University.
    14. Richard Cottle, 2010. "A field guide to the matrix classes found in the literature of the linear complementarity problem," Journal of Global Optimization, Springer, vol. 46(4), pages 571-580, April.
    15. van Soest, A.H.O., 1990. "Essays on micro-econometric models of consumer demand and the labour market," Other publications TiSEM be045d62-a73d-4d7c-a591-f, Tilburg University, School of Economics and Management.
    16. Shihsien, Liu & Fricker, Jon D., 1996. "Estimation of a trip table and the [Theta] parameter in a stochastic network," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(4), pages 287-305, July.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:17:y:1971:i:9:p:612-634. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.