The signaling game is a game-theoretical model that can depict the dynamics enabling the emergence of semantic meaning that establishes as convention among members of a society. The signaling game alone describes a communicative situation, but by applying it as a repeated game and combining it with update dynamics, a path of the evolution of semantic meaning can be simulated. In this work I will i) combine the repeated signaling game with the update dynamics innovative reinforcement learning, and ii) conduct it on a society of agents arranged in scale-free networks. The simulation runs show not only that multiple regional conventions emerge and stabilize, but also reveal the way these regions are arranged and interact with each other.
Semantic meaning of a language's expressions is in the least frequent cases a
result of agreements among a speech community, but rather a product of
regularities in communicative behavior. These regularities form semantic conventions,
which { once emerged { are stable to a speci c degree.1 To formalize this process
of the emergence of semantic meaning, Lewis invented a game-theoretical model,
the signaling game [
As a matter of fact, most studies with signaling games consider only
twoplayers setups, and therefore neglect the fact that an essential feature of a
convention might be its emergence inside a population that contains more than
two members. In the last decade, a number of studies addressed the question of
how conventions of semantic meaning arise in realistic population structures; by
applying repeated signaling games between connected agents placed in network
1 Of course, forces of language change might shift the manifestation of semantic
conventions, in form and in meaning as well, but generally they reveal at least a temporal
stability.
structures: from lattice structures [
In the last two decades a quite large number of studies emerged that
incorporate the analysis of the behavior of agents that communicate via the naming
game in diverse population structures to reach semantic conventions [
Another line of research analyzed the emergence of conventions and norms
by applying a repeated coordination game combined with reinforcement learning
in social network structures [
With this study I want to contribute to the line of research that deals with
the question of how semantic conventions emerge and position themselves in a
society. I use repeated signaling games in combination with an update mechanism
that is called reinforcement learning [
The article is divided in the following way: in Section 2, I will introduce some basic notions of repeated signaling games, innovative reinforcement learning and network theory. In Section 3, I will present the simulation experiments, their results and appropriate analyses of the data. In Section 4, I will give a nal conclusion and discuss open questions. 2
This section will give a coarse technical and theoretical background of the important concepts of this article: the signaling game, innovative reinforcement learning and network theory. 2.1
A signaling game SG = hfS; Rg; T; M; A; P r; U i is a game played between a sender S and a receiver R. T is a set of information states, M is a set of messages and A is a set of interpretation states. Pr(t) 2 (T ) is a probability distribution over T and describes the prior probability that a state t is topic of communication.5 U : T A ! R is a utility function that determines how well interpretation state and information state both correspond to each other.
A play of the game looks as follows: the so-called invisible player, call it destiny or nature, picks one of the states t 2 T and puts it into the sender's mind.6 The sender wants to communicate this state by choosing a message m 2 M that she signals to the receiver. At this point the receiver knows the message that has been signaled, whereas the information state is concealed to him. In face of the given message m the receiver picks an interpretation state a 2 A with the purpose to match as good as possible with information state t; or in other words: to maximize the utility U (t; a). Since utilities are identical to both participants, also the sender has an interest that the receiver decodes successfully. All in all, both interlocutors have an interest to perform an act of perfect information transmission, of perfect communication.
In this study I only consider signaling games that i) have a at probability function, 8t 2 T : P r(t) = jT1 j , and ii) have the same number of information states and interpretation states, thus jT j = jAj. Furthermore, each information state has a corresponding interpretation state, that is marked by the same index, c.f. ti corresponds to ai. Finally, this correspondence is valued by the utility function: if both states correspond to each other, the utility for both players is 5 (X) : X ! R denotes a probability distribution over random variable X. 6 Note that in this kind of game the function P r determines how probable nature picks an information state; i.o.w. the probability of state t being in the sender's mind is always P r(t).
t1 L1: t2 m1 m2 a1 a2 a positive value 2 R; if not, it is zero or a negative value signaling game is called n k-game and de ned as follows: 2 R. This kind of
jT j = jAj = n, jM j = k, 8t 2 T : P r(t) = 1=jT j and U (ti; aj ) = k-game is a signaling game SG with: > 0 if i = j 0 else Note that messages are initially meaningless in this game, since the utility function rewards a correspondence between information state and interpretation state, whereas the chosen message does not a ect the reward. In other words, each message can be used to communicate a corresponding state pair hti; aii. The meaningfulness of a message m is stated if it communicates a particular state; and this meaningfulness can arise from regularities in behavior. Behavior is de ned in terms of strategies. A behavioral sender strategy is a function : T ! (M ), and a behavioral receiver strategy is a function : M ! (A). A behavioral strategy can be interpreted as a single agent's probabilistic choice.
If the game per se does not entail meaningfulness of messages, then what circumstances can tell us that a message is attributed with a meaning? The answer is: this can be indicated by the combination of sender and receiver strategies, called strategy pro le: a message has a meaning between a sender and a receiver, if both participants use pure strategies that constitute a speci c isomorphic strategy pro le.
Note that for a 2 2-game, there are exactly two such strategy pro les, as
depicted in Figure 1. Here in pro le L1 the message m1 has the meaning of state
pair ht1; a1i and message m2 has the meaning of state pair ht2; a2i. For pro le L2
it is exactly the other way around. Lewis called such strategy pro les signaling
systems [
A signaling system shows how semantic meaning can be expressed by
participants' communicative behavior: a message has a meaning, if sender and
receiver communicate according to a signaling system. But it does not explain,
how participants come to a signaling system in the rst place, by expecting that
messages are initially meaningless. To understand the evolutionary paths that
might lead from a meaningless to a meaningful message, it is necessary to explore
the process that leads from participants' arbitrary communicative behavior to a
behavior that constitutes a signaling system. Such a process can be simulated by
repeated signaling games, where the participants' behavior is guided by update
dynamics. One popular dynamics is called reinforcement learning [
Reinforcement learning can be delineated by an urn model, known as Polya urns
[
The behavioral strategy of sender and receiver as well can be described in terms of response rules that describe a participant's situation before making the next move. To be concrete, let's designate i) the number of balls of type m in sender urn ft with m(ft), and the overall number of balls in sender urn ft with jftj; and ii) the number of balls of type a in receiver urn fm with a(fm), and the overall number of balls in receiver urn fm with jfmj. The resulting sender response rule and receiver response rule is given in equations 1 and 2. (mjt) = m(ft) jftj (1) (ajm) = a(fm) jfmj (2) The actual learning dynamics is realized by changing the urn content dependent on the communicative success: if communication via t, m and a is successful, the number of balls of type m in urn ft and the number of balls of type a in urn fm each is increased by the positive utility value 2 R. In this way successful communicative behavior is more probable to reappear in subsequent rounds, successful behavior is reinforced.
This mechanism can be intensi ed by lateral inhibition: if communication
via t, m and a is successful, not only will the number of ball type m in urn ft
be increased, but also will the number of all other ball types m0 2 M n fmg be
decreased by 2 R. Similarly, for the receiver. Franke and Jager [
Furthermore, negative reinforcement can be used to punish unsuccessful behavior. It changes urn contents in the following way: if communication via t, m and a is unsuccessful, the number of balls of type m in the sender urn ft, and the number of balls of type a in the receiver urn fm each will be decreased by negative utility value 2 R. In this way unsuccessful communicative behavior is less probable to reappear in subsequent rounds.
Note that reinforcement learning might have the property to slow down the
learning e ect: if the total number of balls in an urn increases over time, but the
rewarding value is a xed value, then the learning e ect mitigates. A way to
prevent learning from slowing down is to keep the overall number of balls jfj on
a xed value 2 R by scaling the urn content appropriately after each round
of play. Such a setup is a variant of so-called Bush-Mosteller reinforcement [
All in all, a reinforcement learning setup for a signaling game can be captured by RL = h ; ; ; ; i, where is the reward value, the punishment value, the lateral inhibition value and determines the constant urn size. Additionally, is a function that de nes the initial urn settings. This standard account can be re ned to an account that includes a mechanism for the invention of new messages, and is correspondingly called innovative reinforcement learning. 2.3
The basic idea of innovative reinforcement learning stems from Skyrms [
The second study [
To ensure that a network structure resembles a realistic interaction structure of
human populations, it should have small-world properties: i) a short
characteristic path length, and ii) a high clustering coe cient [
This is no surprise, since the less messages are given, the less signaling systems are
possible: for an n k-game there are k!=(k n)! possible signaling systems.
8 For the de nition of these network properties I refer to Jackson's Social and
Economic Networks [
In the analysis of the simulation experiments I perused particular network properties, which I divide in local properties that describe characteristics of a node, and global properties that describe characteristics of a connected subnetwork. There were two local network properties I was interested in: degree centrality that is determined by the number of a node's connections; and individual clustering that is determined by the number of connections among a node's neighborhood.9 Furthermore, there are two global network properties: transitivity that can be interpreted as a measure of global clustering; and the clustering coe cient that is the average value of individual clustering among all nodes of a sub-network, and can be seen as a measure of local clustering.8 3
My experiment contained 10 simulation runs, each is arranged as follows: agents
are placed in a social network structure; per simulation step they communicate
by playing a signaling game with each of their connected neighbors and update
their behavior by reinforcement learning. The concrete settings are as follows:
{ network structure: a scale-free network with 500 agents (Holme-Kim
algorithm [
A basic result of all simulation runs was as follows: a number of di erent
convention regions emerged. This result was already observed in previous studies
with similar settings [
Another result of the simulation runs was the following: the global communicative success10 also oscillates around a speci c value between :75 and :95, depending on the simulation run. Apparently, despite the high number of multiple conventions, communication works quite well in this society. The reasons are i) that all members of their own convention region communicate perfectly successfully with each other, and ii) that neighboring regions often have similar conventions that guarantee at least partial success at the borders. To get an impression of such a diverse society, Figure 3a shows a resulting scale-free network with around 20 di erent convention regions, indicated by di erent colors.
It turned out that the conventions regions that evolved inside a network after 100,000 simulation steps di erentiate highly in their size.11 In each simulation run maximally one really large region emerged, and always a couple of medium size regions, and a high number of small regions. Figure 3b depicts the number of emerged convention regions for speci c intervals of sizes, over all 10 simulation runs. As observable, the number of convention regions decreases with their size; c.f. while there evolved more that 50 convention regions with a size smaller than 50, there evolved only two convention regions with a size larger than 250.
A further, quite surprising result is the fact that there is a negative correlation between the size of a region and the degree centrality of its agents. This is clearly observable in Figure 4a, where each data point represents an agent's region size (x-axis) and her degree centrality (y-axis). This analysis reveals a negative Pearson correlation of -.405. Furthermore, by conducting the same analysis and considering only each region's agent with maximal degree centrality (as depicted in Figure 4b) the negative correlation is even stronger, namely -.634. 10 The global communicative success is simply the utility value averaged over all conducted interactions at one simulation step,. 11 A size of a region is determined by its number of members. (a) exemplary scale-free network (b) histogram of region sizes Fig. 3: Scale-free network with 500 nodes and around 20 convention regions (Figure 3a) and the number of convention regions for di erent intervals of size over all 10 simulation runs (Figure 3b).
This result says that agents with a high degree centrality are members of a small convention region, while large regions contain rather agents with a low degree centrality. This is a surprising result, since intuitively one would expect an outcome that is exactly the other way around; one would expect agents with a lot of neighbors of the same convention rather in a large convention region, and vice versa. One possible explanation is that agents with a high degree centrality tend to be more innovative and frequently create their own small society. A more detailed analysis that might explain this phenomenon is under study and will be part of a subsequent study. 3.2
Another issue of examination was the way convention regions change over time. As a basic result it turns out that most of the time regions have a rather xed size that oscillates with a small deviation. But from time to time a process happens that I will call spatial acquisition: a convention region acquires a part of a neighboring region. Furthermore, all simulation runs reveal that spatial acquisition only happens between regions whose conventions have a high similarity and di er only in one used message. This result gives rise to the more general assumption that a particular degree of similarity between conventions is a necessary condition for realizing spatial acquisition at all. Further formal analyses are beyond the scope of this study and are left to future research.
In a more detailed analysis I wanted to gure out if particular global network properties of neighboring regions are supportive for the emergence of spatial acquisition among them. For that purpose I extracted all events that indicated a spatial acquisition between two convention regions and measured the transitivity (a) all agents (b) agents with max. DC Fig. 4: Data plot of agent's degree centrality (y-axis) in comparison to their region's size (x-axis). Figure 4a depicts all agent's data points, Figure 4b only data points of agents with maximal degree centrality in their region. value and clustering coe cient12of the occupying force and the retreating force13 just before the spatial acquisition event started. Furthermore, I also computed the transitivity value and clustering coe cient of the occupied territory right after the spatial acquisition event.
It turned out that there doesn't seem to be any systematic di erence between the clustering coe cient of occupying and retreating force, whereas the transitivity values reveal a systematic distribution: the occupying force has always a lower value than the retreating force and the occupied territory (Figure 5a and 5b shoe the results of 5 exemplary spatial acquisition events). This is an indicator for the fact that areas of high transitivity are easier to occupy. In conclusion, while it is generally assumed that i) a high degree of local clustering - the clustering coe cient - is an indicator for stability and supports conventions to maintain, the result of my analysis shows that ii) a high degree of global clustering - transitivity - supports the possibility for conventions to spread and is therefore also susceptible to spatial acquisition by neighboring regions. 12 The values are normalized to an expected average value for a given population size. 13 For a spatial acquisition event with two participating convention regions, the occupying force is the one with increasing population size, whereas the retreating force is the one with decreasing population size. (a) clustering coe cient (b) transitivity In this study I conducted simulation runs of 500 agents that i) are placed on a scale-free network, ii) play repeated signaling games with connected neighbors, and iii) update behavior according to innovative reinforcement learning. A general result in all runs was the emergence of convention regions. In further examination steps I analyzed the way regions i) are arranged, and ii) interact.
The rst examination step revealed quite a counterintuitive result: agents with a high degree centrality are basically found in small convention regions, whereas large regions entail generally agents with a quite small degree centrality. As a rst suggestion, this phenomenon seems to be an artifact of the speci c learning dynamics and its possibility for innovation. The second examination step points to the fact that a territory with a high transitivity value is easy to occupy, while a low transitivity value supports preservation. Since this result follows from a small number of observed events, the assumption has to be tested for more robustness in subsequent studies with more data.