A Refinement Procedure for Computing Fixed Points Using Scarf's Primitive Sets

A fixed point of a function is a point that coincides with its image when applying the function. Fixed point computations originated with Scarf (Scarf, H. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math.15 1328–1343.) who presented a finite combinatorial method for finding an approximate fixed point. The method is a systematic search through a sequence of combinatorial objects called primitive sets and provides a constructive proof for a theorem whose domain of applicability goes beyond fixed point computations.

In this paper we present a refinement method for proving Scarf's theorem. A refinement method solves the main problem, as formulated in Scarf's theorem, by solving a succession of subproblems. A solution for a subproblem is an approximate solution for the main problem. It is also the starting point for solving a more refined subproblem whose solution we expect to have greater accuracy than the approximate solution we started with. Subproblems are solved continuously until a solution of sufficient accuracy has been found.

An interesting feature of the refinement method is its possibly nonmonotonic behavior. The method sometimes regresses to a subproblem solved earlier. Several regressions may follow each other, but eventually the method returns to a forward mode. Index theoretic arguments enable us to characterize the points where the procedure behaves nonmonotonically.

Finally, we relate our approach to that of Tuy (Tuy, H. 1979. Pivotal methods for computing equilibria: Unified approach and new restart algorithm. Math. Programming16 210–227.) and establish that both methods coincide. We also show how Scarfs original method can be considered a special case of the refinement method presented here.