IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v192y2009i2p374-381.html
   My bibliography  Save this article

A discrete multivariate mean value theorem with applications

Author

Listed:
  • Talman, Dolf
  • Yang, Zaifu

Abstract

We establish a discrete multivariate mean value theorem for the class of positive maximum component sign preserving functions. A constructive and combinatorial proof is given based upon a simplicial algorithm and vector labeling. Moreover, we apply this theorem to a discrete nonlinear complementarity problem and an economic equilibrium problem with indivisibilities and show the existence of solutions in both problems under certain mild conditions.

Suggested Citation

  • Talman, Dolf & Yang, Zaifu, 2009. "A discrete multivariate mean value theorem with applications," European Journal of Operational Research, Elsevier, vol. 192(2), pages 374-381, January.
    • Handle: RePEc:eee:ejores:v:192:y:2009:i:2:p:374-381
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00995-2
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2005. "Computing Integral Solutions of Complementarity Problems," Other publications TiSEM b8e0c74e-2219-4ab0-99a2-0, Tilburg University, School of Economics and Management.
    2. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2007. "A vector labeling method for solving discrete zero point and complementarity problems," Other publications TiSEM 070869d0-4e42-4d34-85f9-b, Tilburg University, School of Economics and Management.
    3. Kaneko, Mamoru & Yamamoto, Yoshitsugu, 1986. "The existence and computation of competitive equilibria in markets with an indivisible commodity," Journal of Economic Theory, Elsevier, vol. 38(1), pages 118-136, February.
    4. P. J. J. Herings & G. A. Koshevoy & A. J. J. Talman & Z. Yang, 2004. "General Existence Theorem of Zero Points," Journal of Optimization Theory and Applications, Springer, vol. 120(2), pages 375-394, February.
    5. Bevia, Carmen & Quinzii, Martine & Silva, Jose A., 1999. "Buying several indivisible goods," Mathematical Social Sciences, Elsevier, vol. 37(1), pages 1-23, January.
    6. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2005. "Solving Discrete Zero Point Problems with Vector Labeling," Other publications TiSEM 9bd940ee-3fe6-4201-aede-7, Tilburg University, School of Economics and Management.
    7. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(3), pages 427-432, June.
    8. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(4), pages 629-637, August.
    9. Iimura, Takuya, 2003. "A discrete fixed point theorem and its applications," Journal of Mathematical Economics, Elsevier, vol. 39(7), pages 725-742, September.
    10. van der Laan, Gerard & Talman, Dolf & Yang, Zaifu, 2002. "Existence and Welfare Properties of Equilibrium in an Exchange Economy with Multiple Divisible and Indivisible Commodities and Linear Production Technologies," Journal of Economic Theory, Elsevier, vol. 103(2), pages 411-428, April.
    11. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(5), pages 777-788, October.
    12. Iimura, Takuya & Murota, Kazuo & Tamura, Akihisa, 2005. "Discrete fixed point theorem reconsidered," Journal of Mathematical Economics, Elsevier, vol. 41(8), pages 1030-1036, December.
    13. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2002. "Existence and welfare properties of equilibrium in an exchange economy with multiple divisible and indivisible commodities and linear production," Other publications TiSEM 5a5610bf-4f85-4a25-963c-c, Tilburg University, School of Economics and Management.
    14. ,, 1999. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 15(1), pages 151-160, February.
    15. G. van der Laan, 1981. "Simplicial fixed point algorithms," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 35(1), pages 58-58, March.
    16. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
    17. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    18. Ning Sun & Zaifu Yang, 2006. "Equilibria and Indivisibilities: Gross Substitutes and Complements," Econometrica, Econometric Society, vol. 74(5), pages 1385-1402, September.
    19. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    20. Peter M. Reiser, 1981. "A Modified Integer Labeling for Complementarity Algorithms," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 129-139, February.
    21. Yang, Zaifu, 2000. "Equilibrium in an exchange economy with multiple indivisible commodities and money," Journal of Mathematical Economics, Elsevier, vol. 33(3), pages 353-365, April.
    22. Talman, A.J.J. & van der Laan, G., 1979. "A restart algorithm for computing fixed points without an extra dimension," Other publications TiSEM 1f2102f8-e6da-4e9c-a2ed-9, Tilburg University, School of Economics and Management.
    23. R. Saigal, 1983. "A Homotopy for Solving Large, Sparse and Structured Fixed Point Problems," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 557-578, November.
    24. M. Seetharama Gowda & Jong-Shi Pang, 1992. "On Solution Stability of the Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 77-83, February.
    25. Robert M. Freund, 1984. "Variable Dimension Complexes Part II: A Unified Approach to Some Combinatorial Lemmas in Topology," Mathematics of Operations Research, INFORMS, vol. 9(4), pages 498-509, November.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. van der Laan, Gerard & Talman, Dolf & Yang, Zaifu, 2011. "Solving discrete systems of nonlinear equations," European Journal of Operational Research, Elsevier, vol. 214(3), pages 493-500, November.
    2. G. Laan & A. J. J. Talman & Z. Yang, 2010. "Combinatorial Integer Labeling Theorems on Finite Sets with Applications," Journal of Optimization Theory and Applications, Springer, vol. 144(2), pages 391-407, February.
    3. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2007. "Combinatorial Integer Labeling Thorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations," Other publications TiSEM 264c28a5-10b6-44e1-9694-4, Tilburg University, School of Economics and Management.
    2. van der Laan, Gerard & Talman, Dolf & Yang, Zaifu, 2011. "Solving discrete systems of nonlinear equations," European Journal of Operational Research, Elsevier, vol. 214(3), pages 493-500, November.
    3. G. Laan & A. J. J. Talman & Z. Yang, 2010. "Combinatorial Integer Labeling Theorems on Finite Sets with Applications," Journal of Optimization Theory and Applications, Springer, vol. 144(2), pages 391-407, February.
    4. Zaifu Yang, 2008. "On the Solutions of Discrete Nonlinear Complementarity and Related Problems," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 976-990, November.
    5. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2005. "Solving Discrete Zero Point Problems with Vector Labeling," Discussion Paper 2005-122, Tilburg University, Center for Economic Research.
    6. Gerard van der Laan & Dolf Talman & Zaifu Yang, 2004. "Solving Discrete Zero Point Problems," Tinbergen Institute Discussion Papers 04-112/1, Tinbergen Institute.
    7. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2007. "A vector labeling method for solving discrete zero point and complementarity problems," Other publications TiSEM 070869d0-4e42-4d34-85f9-b, Tilburg University, School of Economics and Management.
    8. Elizabeth Baldwin & Omer Edhan & Ravi Jagadeesan & Paul Klemperer & Alexander Teytelboym, 2020. "The Equilibrium Existence Duality: Equilibrium with Indivisibilities & Income Effects," Papers 2006.16939, arXiv.org.
    9. Koshevoy, G.A. & Talman, A.J.J., 2006. "Competitive Equilibria in Economies with Multiple Divisible and Indivisible Commodities and No Money," Other publications TiSEM 130306fe-6e3c-499c-b776-c, Tilburg University, School of Economics and Management.
    10. Koshevoy, Gleb A. & Talman, Dolf, 2006. "Competitive equilibria in economies with multiple indivisible and multiple divisible commodities," Journal of Mathematical Economics, Elsevier, vol. 42(2), pages 216-226, April.
    11. Satoru Fujishige & Zaifu Yang, 2002. "Existence of an Equilibrium in a General Competitive Exchange Economy with Indivisible Goods and Money," Annals of Economics and Finance, Society for AEF, vol. 3(1), pages 135-147, May.
    12. Ning Sun & Zaifu Yang, 2009. "Strategy Proof And Privacy Preserving Fair Allocation Mechanism," The Japanese Economic Review, Japanese Economic Association, vol. 60(2), pages 143-151, June.
    13. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.
    14. Satoru Fujishige & Zaifu Yang, 2020. "A Universal Dynamic Auction for Unimodular Demand Types: An Efficient Auction Design for Various Kinds of Indivisible Commodities," Discussion Papers 20/08, Department of Economics, University of York.
    15. Yang, Zaifu, 2003. "A competitive market model for indivisible commodities," Economics Letters, Elsevier, vol. 78(1), pages 41-47, January.
    16. G. Isac & V. V. Kalashnikov, 2001. "Exceptional Family of Elements, Leray–Schauder Alternative, Pseudomonotone Operators and Complementarity," Journal of Optimization Theory and Applications, Springer, vol. 109(1), pages 69-83, April.
    17. Krzysztof S. Targiel & Maciej Nowak & Tadeusz Trzaskalik, 2018. "Scheduling non-critical activities using multicriteria approach," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(3), pages 585-598, September.
    18. Okitonyumbe Y.F., Joseph & Ulungu, Berthold E.-L., 2013. "Nouvelle caractérisation des solutions efficaces des problèmes d’optimisation combinatoire multi-objectif [New characterization of efficient solution in multi-objective combinatorial optimization]," MPRA Paper 66123, University Library of Munich, Germany.
    19. Amit Kumar & Anila Gupta, 2013. "Mehar’s methods for fuzzy assignment problems with restrictions," Fuzzy Information and Engineering, Springer, vol. 5(1), pages 27-44, March.
    20. Monica Motta & Caterina Sartori, 2020. "Normality and Nondegeneracy of the Maximum Principle in Optimal Impulsive Control Under State Constraints," Journal of Optimization Theory and Applications, Springer, vol. 185(1), pages 44-71, April.

    More about this item

    Keywords

    Discrete set Mean value theorem Fixed point Algorithm Equilibrium Complementarity;

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C62 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium
    • C68 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computable General Equilibrium Models
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C58 - Mathematical and Quantitative Methods - - Econometric Modeling - - - Financial Econometrics

    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:eee:ejores:v:192:y:2009:i:2:p:374-381. See general information about how to correct material in RePEc.

    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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.