Abstract
A new simplicial variable dimension restart algorithm is introduced to solve the nonlinear complementarity problem on the product spaceS of unit simplices. The triangulation which underlies the algorithm differs from the triangulations ofS used thus far. Moreover, the number of rays along which the algorithm can leave the arbitrarily chosen starting point is much larger. More precisely, there is a ray leading from the starting point to each vertex ofS. In caseS is the product ofn one-dimensional unit simplices the alogrithm is similar to the octahedral algorithm onR n having 2n rays. Also, the accuracy of an approximate solution in the terminal simplex of the algorithm is in general better than for the other algorithms onS. Computational results will show that the number of iterations for the new algorithm is much less. The examples concern the computation of equilibria in noncooperative games, exchange economies and trade models.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. van der Laan, “The computation of general equilibrium in economies with a block diagonal pattern”,Econometrica 53 (1985) 659–666.
G. van der Laan and A.J.J. Talman, “A restart algorithm for computing fixed points without an extra dimension,”Mathematical Programming 17 (1979) 74–84.
G. van der Laan and A.J.J. Talman, “An improvement of fixed point algorithms by using a good triangulation,”Mathematical Programming 18 (1980) 274–285.
G. van der Laan and A.J.J. Talman, “A class of simplicial restart fixed point algorithms without an extra dimension,”Mathematical Programming 20 (1981) 33–48.
G. van der Laan and A.J.J. Talman, “On the computation of fixed points in the product space of unit simplices and an application to noncooperativeN-person games,”Mathematics of Operations Research 7 (1982) 1–13.
G. van der Laan and A.J.J. Talman, “Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds,” Research Memorandum 137, Department of Economics, Tilburg University, Tilburg, The Netherlands (December 1983), to appear inMathematical Programming.
G. van der Laan, A.J.J. Talman and L. Van der Heyden, “Variable dimensions algorithms for unproper labellings,” Research Memorandum 147, Department of Economics, Tilburg University, Tilburg, The Netherlands (April 1984), to appear inMathematics of Operations Research.
A. Mansur and J. Whalley, “A decomposition algorithm for general equilibrium computation with application to international trade models,”Econometrica 50 (1982) 1547–1557.
H. Scarf, “The approximation of fixed points of a continuous mapping,”SIAM Journal of Applied Mathematics 15 (1967) 1328–1343.
A.J.J. Talman, “Variable dimension fixed point algorithms and triangulations,” Mathematical Centre Tracts 128, Mathematisch Centrum, Amsterdam, The Netherlands, 1980.
M.J. Todd, “Improving the convergence of fixed point algorithms,” Mathematical Programming Studies 7 (1978) 151–169.
H. Tuy, Ng. van Thoai and Le d. Muu, “A modification of Scarf's algorithm allowing restarting,”Mathematische Operationsforschung und Statistik Series Optimization 9 (1978) 357–372.
A.H. Wright, “The octahedral algorithm, a new simplicial fixed point algorithm,”Mathematical Programming 21 (1981) 47–69.
Author information
Authors and Affiliations
Additional information
This author is financially supported by the Netherlands Organisation for the Advancement of Pure Research (ZWO), Grant 46-98.
This research is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply” which has been approved by the Netherlands ministry of education and sciences.
Rights and permissions
About this article
Cite this article
Doup, T.M., Talman, A.J.J. A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices. Mathematical Programming 37, 319–355 (1987). https://doi.org/10.1007/BF02591741
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591741