betaFeedback

WorksComputer Science

Neural networks and games

Abstract

Hopfield neural networks and noncooperative games provide seemingly different approaches to understanding how collective outcomes emerge from local interactions. In a neural network, individual units adjust their states according to local signals; in a game, players choose actions to maximise individual payoffs. I establish an exact equivalence between symmetric binary Hopfield networks and binary-action games that admit a quadratic potential. The equivalence identifies stable network configurations with pure-strategy Nash equilibria, and asynchronous neural updating with best-response dynamics. More broadly, the storage and retrieval of memories in neural networks correspond, respectively, to the design and selection of equilibria in games.

Introduction

Hopfield’s [1] foundational neural-network model shows how simple, locally interacting units can collectively store and retrieve information. Neurons take one of two states and update in response to their neighbours. These updates reduce a global energy function, leading to stable configurations that can serve as stored memories.

There is a natural parallel in noncooperative game theory, where players adjust their actions in response to one another. In potential games [3], these adjustments can be captured by a single function that increases whenever a player makes a profitable deviation. In finite games, any sequence of such improvements eventually lead to a Nash equilibrium [3 Lemma 2.3].

In this note I show that, despite their different origins and terminology, these two approaches to decentralised interaction are mathematically equivalent. Specifically, Theorem 1 confirms that symmetric binary Hopfield networks are equivalent to binary-action games whose incentives admit a quadratic potential.1 In particular, the negative of the Hopfield energy function is the game-theoretic potential, stable network configurations are Nash equilibria, and asynchronous neuronal updating corresponds to best-response dynamics. More broadly, the storage and retrieval of memories in neural networks correspond, respectively, to the design of equilibria and their selection using dynamics. My hope is that methods and questions developed in either literature may prove useful in the other.

Neural nets as games and games as neural nets

Consider a finite set V={1,…,n}V = \{1, \ldots, n\} of interacting units. Each unit i∈Vi \in V is in one of two states, xi∈{−1,+1}x_i \in\{-1, +1\}, and, as is standard, x−i\mathbf{x}_{-i} denotes the states of all units other than ii. The units are connected by an undirected graph G=(V,E)G = (V, E), where an edge ij∈Eij \in E indicates that units ii and jj interact and Ni={j:ij∈E}N_i = \{j : ij \in E\} denotes the neighbours of ii.

Now consider two interpretations of this environment. In the first, the units are neurons whose states evolve in response to their neighbours. In the second, they are players whose actions depend on the actions of those with whom they interact. In the neural-network interpretation, behaviour is governed by an energy function defined over network configurations; in the game-theoretic variant, each player has a utility function that depends on her own action and those of her neighbours.

The connection between the two models can be seen clearly by presenting the ingredients in parallel. The formal equivalence is established in Theorem 1 that follows.

Neural networks

Neuron i∈Vi \in V has state xi∈{−1,+1}x_i \in\{-1,+1\}.

A pattern is a configuration x=(xi)i∈V\mathbf{x}=(x_i)_{i\in V}.

An edge ij∈Eij \in E represents a synaptic connection, with symmetric weight Jij=JjiJ_{ij}=J_{ji}. Set Jij=0J_{ij}=0 off EE and Jii=0J_{ii}=0.

The local field of neuron ii is

ℓi(x−i)=hi+∑j∈NiJijxj.\ell_i(\mathbf{x}_{-i})=h_i+\sum_{j\in N_i}J_{ij}x_j.

The neuron adopts the sign of its local field, adjusting its state accordingly; when the field is zero, it retains its state.

The network has energy

H(x)=−∑ij∈EJijxixj−∑ihixi.H(\mathbf{x})=-\sum_{ij\in E}J_{ij}x_ix_j-\sum_i h_ix_i.

A unilateral change of state gives

ΔiH=−(xi′−xi)ℓi(x−i).\Delta_iH=-(x_i'-x_i)\ell_i(\mathbf{x}_{-i}).

Every strict asynchronous update strictly lowers energy.

A configuration is stable if no neuron would change when updated.

Games

Player i∈Vi \in V chooses action xi∈{−1,+1}x_i \in\{-1,+1\}.

A pure strategy profile is x=(xi)i∈V\mathbf{x}=(x_i)_{i\in V}.

An edge ij∈Eij \in E represents a bilateral game, with symmetric interaction coefficient Jij=JjiJ_{ij}=J_{ji}. Set Jij=0J_{ij}=0 off EE and Jii=0J_{ii}=0.

Player ii receives additive bilateral payoffs:

ui(x)=hixi+∑j∈NiJijxixj.u_i(\mathbf{x})=h_ix_i+\sum_{j\in N_i}J_{ij}x_ix_j.

The player chooses a best response to her neighbours’ actions; when indifferent, she retains her action.

The game has exact potential

Φ(x)=∑ij∈EJijxixj+∑ihixi.\Phi(\mathbf{x})=\sum_{ij\in E}J_{ij}x_ix_j+\sum_i h_ix_i.

A unilateral change of action gives

Δiui=ΔiΦ=(xi′−xi)ℓi(x−i).\Delta_i u_i=\Delta_i\Phi=(x_i'-x_i)\ell_i(\mathbf{x}_{-i}).

Every strict best-response strictly raises potential.

A profile is a Nash equilibrium if no player has a profitable unilateral deviation.

A player’s payoff depends on her own action, whereas, interestingly, a neuron’s local field is independent of its own state. The two are related by ui(x)=xiℓi(x−i)u_i(\mathbf{x})=x_i\ell_i(\mathbf{x}_{-i}).

Theorem 1 (Neural-network–game equivalence). The following two systems are mathematically equivalent:

(i) Symmetric binary Hopfield networks with Jij=JjiJ_{ij}=J_{ji}, Jii=0J_{ii}=0, biases hih_i, and energy

H(x)=−∑i<jJijxixj−∑ihixi.H(\mathbf{x})=-\sum_{i<j}J_{ij}x_ix_j-\sum_i h_ix_i.

(ii) Binary-action exact-potential games admitting a quadratic potential2

Φ(x)=∑i<jJijxixj+∑ihixi.\Phi(\mathbf{x})=\sum_{i<j}J_{ij}x_ix_j+\sum_i h_ix_i.

Proof. For any unilateral change from xix_i to xi′x_i',

Φ(xi′,x−i)−Φ(xi,x−i)=(xi′−xi)(hi+∑j≠iJijxj)=−ΔiH.\Phi(x_i',x_{-i})-\Phi(x_i,x_{-i})=(x_i'-x_i)\left(h_i+\sum_{j\ne i}J_{ij}x_j\right)=-\Delta_i H.

The middle expression is also the change in player ii’s payoff in the corresponding game. Thus, the Hopfield network and the game have identical unilateral incentives. Consequently, best responses coincide with local-field updates, and it follows that stable configurations coincide with Nash equilibria.

To illustrate the equivalence, consider the threshold model of Neary and Newton [6]. Along every edge ij∈Eij\in E, neighbours play the following two-player game, where γi,γj∈(0,1)\gamma_i,\gamma_j\in(0,1).

Player jj: +1+1Player jj: −1-1
Player ii: +1+11−γi,1−γj1-\gamma_i, 1-\gamma_j0,00,0
Player ii: −1-10,00,0γi,γj\gamma_i,\gamma_j

Table 1.

Each player must use the same action with each neighbour and receives the sum of her bilateral payoffs. Writing did_i for player ii’s degree, the payoff difference is

ui(+1,x−i)−ui(−1,x−i)=12[∑j∈Nixj+di(1−2γi)].u_i(+1,x_{-i})-u_i(-1,x_{-i})=\frac{1}{2}\left[\sum_{j\in N_i}x_j+d_i(1-2\gamma_i)\right].

Comparing this with the payoff difference implied by the corresponding Hopfield network,

2(hi+∑j∈NiJijxj)=12[∑j∈Nixj+di(1−2γi)],2\left(h_i+\sum_{j\in N_i}J_{ij}x_j\right)=\frac{1}{2}\left[\sum_{j\in N_i}x_j+d_i(1-2\gamma_i)\right],

we get that Jij=1/4J_{ij}=1/4 for every edge ijij and hi=di(1−2γi)/4h_i=d_i(1-2\gamma_i)/4 for every vertex ii.

Associative memory and mechanism design

One of the principal applications of Hopfield networks is associative memory: the ability to store patterns of neuronal states and subsequently retrieve them from incomplete or corrupted inputs. This raises three related questions: how to design a network that stores prescribed memories, how to account for unintended stable configurations, and how the network’s dynamics determine which memory is retrieved. To a game theorist, the equivalence established in § 2 naturally brings to mind mechanism design, unintended equilibria, and equilibrium selection, respectively.

Storing memories is a design problem

Given a prescribed collection of patterns, the network designer seeks to choose the weights and biases so that each pattern is stable. By Theorem 1, this is equivalent to designing a game by choosing its interaction coefficients and individual payoff parameters so that the corresponding pure strategy profiles are Nash equilibria. Memory storage is therefore simply, in game-theoretic jargon, a mechanism design problem.

Formally, let M⊆{−1,+1}n\mathcal{M} \subseteq\{-1,+1\}^{n} denote the collection of prescribed memories the designer wishes to store. Writing J=(Jij)J=(J_{ij}) and h=(hi)h=(h_i) for a network’s weight matrix and bias vector, the designer’s problem is

find J,hsubject to xi(∑j≠iJijxj+hi)≥0,for all i∈V, x∈M,Jij=Jji,Jii=0.\begin{aligned} &\text{find } J,h\\ &\text{subject to } x_i\left(\sum_{j\ne i}J_{ij}x_j+h_i\right)\ge0,\quad\text{for all }i\in V,\ x\in\mathcal{M},\\ &J_{ij}=J_{ji},\qquad J_{ii}=0. \end{aligned}

Equivalently, let NE⁡(J,h)\operatorname{NE}(J,h) denote the set of pure Nash equilibria of the corresponding game. The designer seeks JJ and hh such that

M⊆NE⁡(J,h).\mathcal{M}\subseteq\operatorname{NE}(J,h).

There is, however, an unusual feature of this mechanism design problem worth highlighting. Maskin and Sjöström [2] is a survey on implementation theory that opens as follows: “The implementation problem is the problem of designing a mechanism (game form) such that the equilibrium outcomes satisfy a criterion of social optimality embodied in a social choice rule.” In Hopfield networks the prescribed outcomes are simply the patterns the designer wishes to store. But, in contrast, there is no requirement that these outcomes be socially optimal, or even that their welfare be worthy of consideration. All that is demanded is equilibrium.

As an example, suppose a designer wishes to store the two patterns x+=(+1,+1,+1,+1)\mathbf{x}^{+}=(+1,+1,+1,+1) and x−=(−1,−1,−1,−1)\mathbf{x}^{-}=(-1,-1,-1,-1). It is easy to see that many choices of weights and biases make both prescribed patterns stable.3 As one possible solution, suppose the designer chooses weights and biases corresponding to the four-player threshold game in Figure 1, with γ1=γ2=3/4\gamma_1=\gamma_2=3/4 and γ3=γ4=1/4\gamma_3=\gamma_4=1/4. Players 1 and 2 are coloured red, while players 3 and 4 are coloured blue.4 Both prescribed patterns, x+x^{+} and x−x^{-}, are strict Nash equilibria of this game and hence stable configurations of the Hopfield network.

Memory storage on a four-player path

Figure 1. Memory storage on a four-player path. Red vertices have threshold 3/43/4, while blue vertices have threshold 1/41/4. Panel (a) shows the network, with player indices above the vertices. Panels (b) and (c) show the two prescribed memories, while panel (d) shows an unintended stable configuration. The signs inside the vertices indicate each neuron’s state.

The example illustrates the distinction between choosing a game and choosing an equilibrium. The designer chooses weights and biases which build a game, which in turn determine the equilibrium set. The potential structure guarantees convergence to an equilibrium (with probability one) under asynchronous best-response dynamics. But two issues remain. First, satisfying the designer’s constraints does not rule out additional equilibria: the inclusion M⊆NE⁡(J,h)\mathcal{M} \subseteq\operatorname{NE}(\mathbf{J},\mathbf{h}) may be strict. Second, whether or not the inclusion is strict, when multiple equilibria exist, the equilibrium reached may depend on the initial configuration and the updating sequence.

Both issues arise in the example. The resulting game admits a third equilibrium, x∗=(−1,−1,+1,+1)x^{*}=(-1,-1,+1,+1), which was not among the prescribed memories. Moreover, x∗x^{*} is the unique potential maximiser. Potential maximisation is a standard equilibrium-selection criterion and yet here it selects an outcome the designer did not intend. I now turn to such unintended stable configurations, known as spurious memories in the neural nets literature.

Spurious memories are unintended equilibria

The problem with spurious memories is not simply that they exist, but that they can interfere with retrieval. In the four-player example, the designer only wanted to store two prescribed memories, yet the resulting game admits three Nash equilibria. This is why spurious memories can be problematic: when presented with an incomplete or corrupted version of a prescribed memory, the network may instead retrieve the spurious memory.

This suggests a stronger version of the memory-storage problem is needed. That is, rather than merely requiring that every prescribed pattern be stable, the designer may wish to ensure that these are the only stable configurations. The mechanism design problem then becomes to construct a game wherein M=NE⁡(J,h)\mathcal{M} = \operatorname{NE}(\mathbf{J},\mathbf{h}).

Retrieving memories and equilibrium selection

Once a network has been designed, the problem of memory retrieval can be interpreted as a kind of targeted equilibrium selection. “Equilibrium” because, by definition, any stored memory is a stable configuration, and “targeted selection” because the objective is to recover a particular memory identified by the input supplied to the network.

The way in which this differs from the quintessential equilibrium-selection problem in game theory is twofold. First, the target may change from one moment (“retrieval episode”) to the next, even though the underlying game remains fixed. Second, and more interestingly in my view, successful retrieval need not involve exact convergence to the targeted equilibrium: recovering a close approximation, with high probability, is often deemed enough.5

Suppose a network has been designed to store images of a cat, a dog, and a horse. (See Figure 3 in the Appendix.) When presented with a corrupted image of a cat, we want the network to retrieve the cat; when subsequently presented with a corrupted image of a dog, we want it to retrieve the dog; etc. Each retrieval begins with a new externally supplied input, rather than the configuration reached after the previous retrieval. The justification for why state nearby the target is deemed “good enough” follows fairly naturally: since the memories are images represented by pixels, recovering an image with a small number of incorrect pixels may be perfectly adequate for recognition.

Cat, dog, and horse images, with a noisy input and retrieved cat

Figure 3. Illustrative stored memories and retrieval from a corrupted input. The lower row shows a noisy cat pattern and the intended recovered memory.

Let’s return to the four-player example. Suppose the designer wishes to retrieve the prescribed memory x−=(−1,−1,−1,−1)\mathbf{x}^{-} = (-1,-1,-1,-1), and suppose further that the initial configuration is y=(−1,−1,−1,+1)\mathbf{y} = (-1,-1,-1,+1) which differs in the third coordinate. Under asynchronous best-response dynamics, retrieval is not guaranteed. If player 4 revises before player 3, the dynamics converge to x−\mathbf{x}^{-} as intended. But if player 3 revises first then the system converges to the spurious memory x∗=(−1,−1,+1,+1)\mathbf{x}^{*} = (-1,-1,+1,+1). Each outcome occurs with probability 1/21/2.

More generally, for a prescribed memory xμ\mathbf{x}^{\mu} and an initial configuration y\mathbf{y}, define

qμ(y)=P(X∞=xμ∣X0=y),q_{\mu}(\mathbf{y}) = \mathbb{P}\left(X_{\infty} = \mathbf{x}^{\mu} \mid X_{0} = \mathbf{y}\right),

where Xt\mathbf{X}_{t} follows random asynchronous best-response dynamics. This is the probability of successfully retrieving the targeted memory from y\mathbf{y}.

Targeted equilibrium selection in the four-player example

Figure 2. Targeted equilibrium selection in the four-player example. The initial configuration is at Hamming distance one from the target memory x−x^{-}. Under uniform random asynchronous best-response dynamics, the target memory is retrieved with probability 1/2, while the spurious memory x∗x^{*} is selected with probability 1/2.

The example illustrates that Hamming distance and retrieval probability capture different aspects of the problem.6 Hamming distance measures the extent of corruption of the initial configuration, whereas qμ(y)q_{\mu}(y) measures the probability that the dynamics recover the intended memory. In the example, a configuration at Hamming distance one from the target only retrieved it with probability only 1/2. Indeed, it is easy to construct examples for which the initial configuration is at Hamming distance one from a strict equilibrium, yet the probability of retrieving that equilibrium is arbitrarily close to zero.

So What?

What do we learn from all this? The mathematical equivalence established in Theorem 1 is straightforward, and so it is not unreasonable to ask what is gained by making it explicit. One immediate consequence is that we now have a common mathematical language connecting two previously distinct literatures, allowing results from one to be translated directed into the other. But translating a known result from one language into another does not make it new, nor does it necessarily make it interesting. The potential value of the connection may, however, extend beyond such translations.

One interesting possibility arises from the fact that the two literatures have developed largely independently, motivated by different questions. Game theorists care about incentives, the rules of interaction, and equilibrium, while researchers studying associative memory are concerned with storage, retrieval, and the behaviour of neural networks. Yet, as we have seen, the two literatures study essentially the same mathematical objects, albeit from different perspectives. The potential benefit is therefore not simply that existing answers can be translated, but that new lines of enquiry may emerge from bringing the two perspectives together. Indeed, the most interesting consequences of the connection may be ones that are difficult to anticipate from within either literature alone.

Cat, dog, and horse images

References

  1. [1]John J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 79(8):2554–2558, 1982.
  2. [2]Eric Maskin and Tomas Sjöström. Implementation theory. In Kenneth J. Arrow, Amartya K. Sen, and Kotaro Suzumura, editors, Handbook of Social Choice and Welfare, volume 1, pages 237–288. Elsevier, 2002.
  3. [3]Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124–143, 1996.
  4. [4]Philip R. Neary. Multiple-Group Games. PhD thesis, University of California, San Diego, 2011.
  5. [5]Philip R. Neary. Competing conventions. Games and Economic Behavior, 76(1):301–328, 2012.DOI
  6. [6]Philip R. Neary and Jonathan Newton. Heterogeneity in preferences and behavior in threshold models. Journal of Mechanism and Institution Design, 2:141–159, 2017.DOI

Paper details

vlnc:W_7nbr9qsg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents