1. Sender-Receiver

In Reference Lewis1969 David Lewis framed the problem in a clean and simple way by introducing sender-receiver games. There are two players, the sender and the receiver. Nature chooses a state at random and the sender observes the state chosen. The sender then sends a signal to the receiver, who cannot observe the state directly but does observe the signal. The receiver then chooses an act, the outcome of which affects them both, with the payoff depending on the state. Both have pure common interest—they get the same payoff—and there is exactly one “correct” act for each state. In the correct act-state combination they both get positive payoff; otherwise, payoff is zero. Lewis discusses only the case in which there are as many acts as there are states, and as many signals as there are states and acts, and this is where we will begin.

Signals are not endowed with any intrinsic meaning. If they are to acquire meaning, the players must somehow find their way to an equilibrium where information is transmitted. When transmission is perfect, so that the act always matches the state and the payoff is optimal, Lewis calls the equilibrium a signaling system. It is a virtue of Lewis's formulation that we do not have to endow the sender and receiver with a preexisting mental language in order to define a signaling system.

If we start with a pair of sender and receiver strategies, and switch the messages around the same way in both, we get the same payoffs. Permutation of messages takes one signaling system equilibrium into another. This fundamental symmetry is what makes Lewis signaling games a model in which the meaning of signals is purely conventional.Footnote ⁵ It also raises in stark form a question that bothered some philosophers from ancient times onward. There seems to be no sufficient reason why one signaling system rather than another should evolve.

2. Information in Signals

Signals carry information.Footnote ⁶ The natural way to measure the information in a signal is to measure the extent that the use of that particular signal changes probabilities.Footnote ⁷ Accordingly, there are two kinds of information in the signals in Lewis sender-receiver games: information about what state the sender has observed and information about what act the receiver will take. The first kind of information measures effectiveness of the sender's use of signals to discriminate states; the second kind measures the effectiveness of the signal in changing the receiver's probabilities of action.Footnote ⁸

Both kinds of information are maximal in a signaling system equilibrium. But this does not characterize a signaling system. Both kinds of information can also be maximal in a state in which the players miscoordinate, and the receiver always does an act that is wrong for the state. In such a state there is plenty of information of both kinds, but we would like to say that no information is transmitted or, better, that misinformation is transmitted.

To deal with this, you might think that we have to build in a semantic concept of information—specifying what the sender intended the signal to mean and what the receiver took it to mean. I want to emphasize again that in Lewis signaling games this is not necessary. Because of the strong common interest present, the mark that information has been successfully transmitted, and that we have a signaling system equilibrium, is maximal payoff to sender and receiver. As Democritus said, “The word is the shadow of the act” (Barnes Reference Barnes1982, 468).

3. Evolution

As a simple explicit model of evolution, we start with the replicator dynamics.Footnote ⁹ It has interpretations both for genetic evolution and for cultural evolution. The population is large, and either differential reproduction or differential imitation lead the population proportion of strategy A, p(A), to change as

where U(A) is the average payoff to strategy A and U is the average payoff in the population.

Evolutionary dynamics could operate on one population of senders and another of receivers, as in some cases of interspecies communication, or it could operate on a single population, in which individuals sometimes find themselves in the role of sender and sometimes in the role of receiver.

Consider the two-population model for the simplest Lewis signaling game—two states, two signals, two acts. And for further simplification, suppose the population has only senders who send different signals for different states and only receivers who perform different acts when they get different signals. There are then only two sender's strategies:

1. S1: State 1 ⇒ Signal 1

   State 2 ⇒ Signal 2

2. S2: State 1 ⇒ Signal 2

   State 2 ⇒ Signal 1

and only two receiver's strategies:

1. R1: Signal 1 ⇒ Act 1

   Signal 2 ⇒ Act 2

2. R2: Signal 1 ⇒ Act 2

   Signal 2 ⇒ Act 1

The pairs $\langle \mathrm{S}\,1,\,\mathrm{R}\,1\rangle $ and $\langle \mathrm{S}\,2,\:\mathrm{R}\,2\rangle $ are the signaling system equilibria.

The population dynamics lives on a square, with p(S2) on the y axis and p(R2) on the x axis, as shown in figure 1. There are five dynamic equilibria—the four corners and one in the center of the square—but three of them are dynamically unstable. The two signaling systems are the only stable equilibria, and evolution carries almost every state of the population to either one signaling system or another.

Figure 1.

Replicator dynamics, two populations.

Consider a one-population model in which the agent's contingency plans, if sender … and if receiver … , correspond to the four corners of the model we just considered. The dynamics lives on a tetrahedron, as shown in figure 2.

Figure 2.

Replicator dynamics, one population.

The vertices are dynamic equilibria, and in addition there is a line of equilibria running through the center of the tetrahedron. But again, all the equilibria are unstable except for the signaling systems. All states to one side of a plane cutting through the tetrahedron are carried to one signaling system; all to the other side to the other signaling system. Almost every possible state of the population is carried to a signaling system.

We see here how a symmetric model can be expected to yield an asymmetric outcome. In our two examples, the principle of sufficient reason is defeated by spontaneous symmetry breaking in the evolutionary dynamics (Skyrms Reference Skyrms1998). The population moves to a signaling system as if—one might say—guided by an unseen hand.

4. Learning Strategies

As a simple explicit model of unsophisticated learning, we start with reinforcement according to Richard Herrnstein's matching law—the probability of choosing an action is proportional to its accumulated rewards.Footnote ¹⁰ We start with some initial weights, perhaps equal, assigned to each action. An act is chosen with probability proportional to its weight. The payoff gained is added to the weight for the act that was chosen, and the process repeats. As the weights build up, the process slows down in accordance with what psychologists call the law of practice.

Consider repeated interactions between two individuals, one sender and one receiver, who learn strategies by this kind of reinforcement. This set-up resembles the two-population evolutionary model, except that process is not deterministic, but chancy.

As an example, let us focus on the two-state, two-signal, two-act signaling game of the last section in the special case in which the sender has only strategies S1 and S2, and the receiver has only strategies R1 and R2.Footnote ¹¹ You can think of this as a model of the situation in which sender and receiver both want the information to be transmitted but don’t know each other's strategies. We can prove that reinforcement learning converges to a signaling system with probability one. Computer simulations show that learning is reasonably fast.

5. Learning Actions

We helped the emergence of signaling in the foregoing model by letting reinforcement work on complete strategies in the signaling game—on functions from input to output. Essentially, the modeler has done some of the work for the learners. I take this as contrary to the spirit of Democritus, according to which the learners should not have to conceive of the problem strategically. Let us reconceptualize the problem by reinforcement work on single actions and see if we still get the same result.

To implement this for the simplest Lewis signaling game, the sender has separate reinforcements for each state. You can think of it as an urn for state 1, with red balls for signal 1 and black balls for signal 2; and another such urn for state 2. The receiver also has two urns, one for each signal received, and each containing balls for the two acts. Reinforcement for a successful act is like adding a ball of the color drawn to the sender and receiver urn just sampled. The individuals are being reinforced for “what to do on this sort of occasion.” We then ask what happens when these occasions fit together to form a signaling game. It has recently been proved in this case as well that learning converges to a signaling system with probability one (Argiento et al. Reference Argiento, Pemantle, Skyrms and Volkov2008).

6. States, Acts, and Signals

In the simplest Lewis signaling games, the number of states, acts, and signals are assumed to be the same. What if there is a mismatch? There may be extra signals, or too few signals, or not enough acts. All of these possibilities raise questions that are interesting both philosophically and mathematically.

Suppose there are too many signals. Do synonyms persist, or do some signals fall out of use until only the number required to identify the states remain in use? Suppose there are too few signals. Then there is, of necessity, an information bottleneck. Does efficient signaling evolve; do the players learn to do as well as possible? Suppose there are lots of states, but not many acts. How do the acts affect how the signaling system partitions the states?

If we have two states, two acts, and three signals, we could imagine that the third signal gets in the way of efficient signaling, or that one signal falls out of use and one ends up with essentially a two-signal system, or that one signal comes to stand for one state and the other two persist as synonyms for the other state. Simulations of the learning process of the last section always produce efficient signaling, often with the persistence of synonyms. Learning is about as fast as in the case in which there are only two signals.

If we have three states, three acts, and only two signals, there is an information bottleneck. The best that the players could do is to get it right two-thirds of the time. This could be managed in various ways. The sender might use signals deterministically to partition the states—for example, send signal 1 in state 1 and signal 2 otherwise. An optimal receiver's strategy in reply would be to do act 1 when receiving signal 1, and to randomize between acts 2 and 3 with any probability. This identifies a line of equilibria. Alternatively, the receiver could be deterministic—for example, doing act 1 for signal 1 and act 2 for signal 2. If so, an optimal sender's strategy to pair with this would be always sending signal 1 in state 1 and signal 2 in state 2, but randomizing in state 3. This identifies another line of efficient equilibria.Footnote ¹² There are, of course, also lots of inefficient equilibria. Simulations always deliver efficient equilibria. They are always of the first kind, not the second. That is to say the signaling system always partitions the states. Learning is still fast.

If we have three states, but only two signals and two acts, we can have act 1 right for state 1, and act 2 right for state 3, and then vary the payoffs for state 2:

Payoffs	State 1	State 2	State 3
Act 1	1	1 − e	0
Act 2	0	e	1

If $e> .5$ it is best to have one signal (which elicits act 1) sent in both state 1 and state 2; and the other signal (which elicits act 2) sent in state 3. If $e> .5$ an efficient equilibrium lumps states 2 and 3 together. The optimal payoff possible depends on e: 2/3 for $e=.5$ and 1 for $e=0$ or $e=1$. For the whole range of values, optimal signaling emerges. Learning is just as fast as in previous cases.

7. Signaling Networks

Signaling is not restricted to the simple one-sender, one-receiver case discussed so far. Alarm calls usually involve one sender and many receivers, perhaps with some of the receivers being eavesdroppers from other species. Quorum signaling in bacteria has many individuals playing the role of both sender and receiver. The brain continually receives and dispatches multiple signals, as do many of its constituents. Most natural signaling occurs in networks. A signaling network can be thought of as a directed graph, with an edge directed from node A to node B signifying that A sends signals to B. All our examples so far have been instantiations of the simplest possible case; one sender sends signals to one receiver.

There are other simple topologies that are of interest. One that I discussed elsewhere (Skyrms Reference Skyrms, Kohler and Gumerman2000, Reference Skyrms2004) involved multiple senders and one receiver. I imagined two senders who observed different partitions of the possible states.

In the context of alarm calls, if one sender observes that a snake or leopard is present, and another observes that there is no snake, a receiving monkey might be well advised to take the action appropriate to evade a leopard. Multiple senders who transmit different information leave the receiver with a problem of logical inference. It is not simply the problem of drawing a correct inference but, rather, the problem of drawing the correct inference relevant to his decision problem. For instance, suppose sender 1 observes the truth value of p and then sends signal A or signal B, and sender 2 observes the truth value of q and sends C or D. Maximum specificity is required where the receiver has four acts, one right for each combination of truth values. But a different decision problem might require the receiver to compute the truth value (p exclusive-or q) and of one act if true and another if false.

Senders may observe different aspects of nature by chance, but they may also be able to choose what they observe. Nature may present receivers with different decision problems. Thus, a receiver might be in a situation in which he would like to ask a sender to make the right observation. This calls for a dialogue, where information flows in both directions.

Nature flips a coin and presents player 2 with one or another decision problem. Player 2 sends one of two signals to player 1. Player 1 selects one of two partitions of the state of nature to observe. Nature flips a coin and presents player 1 with the true state. Player 1 sends one of two signals to player 2. Player 2 chooses one of two acts. Here a question and answer signaling system can guarantee that player 2 always does the right thing.

A sender may distribute information to several receivers.

One instance is the case of eavesdropping, where a third individual listens in to a two-person sender-receiver game, with the act of the third person having payoff consequences for himself, but not for the other two.Footnote ¹³ In a somewhat more demanding setup, the sender sends separate signals to multiple receivers who then have to perform complementary acts for everyone to get paid. For instance, each receiver must choose one of two acts, and the sender observes one of four states of nature and sends one of two signals to each receiver. Each combination of acts pays off in exactly one state.

Signalers may form chains, where information is passed along.

In one scenario, the first individual observes the state and signals the state, and the second observes the signal and signals the third, which must perform the right act to ensure a common payoff. There is no requirement that the second individual sends the same signal that she receives. She might function as a translator from one signaling system to another.

For all these networks, computer simulations of reinforcement learning show spontaneous emergence of signaling systems—although a full mathematical analysis remains to be done. It is remarkable that such an unsophisticated form of learning can arrive at optimal solutions to these various problems.

These networks are the simplest examples of large classes on phenomena of general interest. They also can be thought of as modules, which appear as constituents of more complex and interesting networks that process and transmit information. It is possible for modules to be learned in simple signaling interactions and then assembled into complex networks by either reinforcement or some more sophisticated form of learning. The analogous process operates in evolution.

8. Conclusion

How do these results generalize? This is not so much a single question as an invitation to explore an emerging field. Even the simplest extensions of the models I have shown here are full of surprising and interesting phenomena.Footnote ¹⁴ The dynamics could be varied. On the evolutionary side, we can move from the large population, deterministic model of the replicator dynamics to a small population stochastic model. The mathematical structure of one natural stochastic model of differential reproduction is remarkably similar to our model of reinforcement learning (Schreiber Reference Shreiber2001; Benaim, Schreiber, and Tarres Reference Benaim, Shreiber and Tarres2004). On the learning side, we could consider more sophisticated types of learning. One might expect more sophisticated learners to learn to signal more easily, but the matter needs to be investigated.

We started with a fundamental question. Suppose we start without preexisting meaning. Is it possible that, under favorable conditions, unsophisticated learning dynamics can spontaneously generate meaningful signaling? The answer is affirmative. The parallel question for evolution turns out to be not so different and is answered in the same way. The adaptive dynamics achieves meaning by breaking symmetry. Democritus was right. It remains to explore all the ways in which he was right.