A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices.(English)Zbl 0616.90084
A new simplicial variable dimension restart algorithm is introduced to solve the nonlinear complementarity problem on the product space S of unit simplices. The triangulation which underlies the algorithm differs from the triangulations of S used thus far. Moreover, the number of rays along which the algorithm can leave the arbitrary chosen starting point is much larger. More precisely, there is a ray leading from the starting point to each vertex of S. In case S is the product of n one-dimensional simplices the algorithm is similar to the octahedral algorithm on \(R^ n\) having \(2^ n\) rays. Also, the accuracy of an approximate solution in the terminal simplex of the algorithm is in general better than for the other algorithms on S. 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.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
vector labelling;simplicial variable dimension restart algorithm;nonlinear complementarity problem;triangulation;approximate solution;computation of equilibria in noncooperative games;exchange economies;trade modelsCite
References:
| [1] | G. van der Laan, ”The computation of general equilibrium in economies with a block diagonal pattern”,Econometrica 53 (1985) 659–666. ·Zbl 0569.90007 ·doi:10.2307/1911660 |
| [2] | 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. ·Zbl 0411.90061 ·doi:10.1007/BF01588226 |
| [3] | 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. ·Zbl 0433.90089 ·doi:10.1007/BF01588323 |
| [4] | 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. ·Zbl 0441.90112 ·doi:10.1007/BF01589331 |
| [5] | 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. ·Zbl 0497.90063 ·doi:10.1287/moor.7.1.1 |
| [6] | 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. ·Zbl 0633.90082 |
| [7] | 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. ·Zbl 0638.90096 |
| [8] | A. Mansur and J. Whalley, ”A decomposition algorithm for general equilibrium computation with application to international trade models,”Econometrica 50 (1982) 1547–1557. ·Zbl 0493.90014 ·doi:10.2307/1913395 |
| [9] | H. Scarf, ”The approximation of fixed points of a continuous mapping,”SIAM Journal of Applied Mathematics 15 (1967) 1328–1343. ·Zbl 0153.49401 ·doi:10.1137/0115116 |
| [10] | A.J.J. Talman, ”Variable dimension fixed point algorithms and triangulations,” Mathematical Centre Tracts 128, Mathematisch Centrum, Amsterdam, The Netherlands, 1980. ·Zbl 0464.90047 |
| [11] | M.J. Todd, ”Improving the convergence of fixed point algorithms,” Mathematical Programming Studies 7 (1978) 151–169. ·Zbl 0399.65034 |
| [12] | 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. ·Zbl 0395.90083 |
| [13] | A.H. Wright, ”The octahedral algorithm, a new simplicial fixed point algorithm,”Mathematical Programming 21 (1981) 47–69. ·Zbl 0475.65029 ·doi:10.1007/BF01584229 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
