A variable-dimension homotopy on networks for computing linear spatial equilibria (Q1077331)

The paper presents a new method of solution for an old problem, that of finding a one-commodity spatial equilibrium for a network characterized by linear excess demand functions at each node and constant unit shipping costs from node to node. The spatial equilibrium conditions are formulated as a linear complementarity problem. The underlying idea of the algorithm uses the fact that an equilibrium for K-1 nodes is an equilibrium for K nodes when the excess demand at node K is shifted in an appropriate way; this pseudo-equilibrium is then continuously deformed to a true equilibrium, using a homotopy. The algorithm is implemented using complementary pivoting on the underlying network. An advantage of the new method is that it performs its work in variable dimensions, and can exploit the problem structure: if the nodes are ordered according to dominant market structure, most of the work will be performed in lower dimensions, since a near-equilibrium will be found in a network with only a few nodes with large market shares. The authors present evidence that this can entail substantial savings in computational cost.