D. Miller, S. Zucker
What is the complexity of computing equilibria for physically
implementable analog networks (Hopfield 1984, Sejnowski 1981) with
arbitrary connectivity? We show that if the amplifiers are
piecewise-linear, then such networks are instances of a game-theoretic
model known as *polymatrix games*. In contrast with the usual
gradient descent methods for symmetric networks, equilibria for
polymatrix games may be computed by vertex pivoting algorithms similar
to the simplex method for linear programming. Like the simplex method,
these algorithms have characteristic low order polynomial behavior in
virtually all practical cases, though not certain theoretical
ones. While these algorithms cannot be applied to models requiring
evolution from an initial point, they are applicable to ``clamping''
models whose input is expressed purely as a bias. Thus we have an *a
priori* indication that such models are computationally tractable.

Mon Apr 7 12:54:24 EDT 1997