Limited Cognitive Abilities and Dominance Hierarchies^††thanks: We sincerely thank the editor F.J.A. Jacobs and two anonymous reviewers for their suggestions that help to greatly improve the paper. We also thank Jonathan Newton for his comments.

Consider a population of $N$ agents who are randomly matched in pairs to play the Hawk-Dove (HD) game. The HD game has been widely used to model pairwise interactions where individuals contest a beneficial resource with a possibility of an escalated fight at a large cost, which constructs a simple situation where players have a choice to either being harsh (play Hawk) or soft (play Dove) on their opponents. The earliest illustration of the HD game is presented by Smith and Price [1973] in their analysis of animal behavioral strategies in contest situations. In this paper, we adopt the game form provided by Smith and Parker [1976] as shown in Figure 1.

In this game, $V$ is the value of the contested resource and $C$ is the cost of an escalated fight. It is assumed that the value of the resource is less than the cost of a fight, that is, $C>V>0$. Players split the beneficial resource equally if they both play Dove. They equally split the difference between the resource and fighting cost if they both play Hawk. The player who plays Hawk exclusively wins the resource if the other player plays Dove.

The HD game carries three Nash equilibria (NEs), with two in pure strategy, $(Hawk,Dove)$ and $(Dove,Hawk)$, and one in mixed strategy, where each player plays Hawk with a probability of $V/C$. The expected fitness from playing the mixed NE strategy is $(1-V/C)(V/2)$.

We assume that each agent is assigned with an identity. Identity plays the role of a name tag and it is unique for each agent. With this information, it is possible for the agents to condition their strategies on their opponents’ identities. The difference in identities between two agents can be interpreted on the basis of differences in some of their biological characteristics, such as body size and reproductive ability, whereas in a social interpretation, it can be a label (e.g., representing different social classes in human societies) attached to the agents.

A linear social rank over the agents’ identities is assumed. With this assumption, identities can be written as numbers such that their values reflect the relative ranks. Without loss of generality, we say agents with smaller-valued identities are ranked higher.

There is also a social convention that gives favor to those who rank higher. This is done by imposing a suggestive rule on the agents, regulating their actions in the HD game in accordance with the predetermined social rank. Specifically, it suggests that agents play $Hawk$ against opponents with lower ranks, and play $Dove$ against opponents with higher ranks. Since everyone is assumed to have a unique identity, if the social convention is followed, in any equilibrium, one player plays $Hawk$ and the other plays $Dove$ in each pairwise interaction.

Importantly, a linear social rank is assumed for the purpose of designing the social convention. The numerical values of the numbers are meaningless to the agents, and they do not need to know the social rank. For example, if an agent’s assigned number is 5 and it knows the identity of the agent whose assigned number is 1, then given the suggestion of the social convention, the number 5 agent should play Dove to the number 1 agent.

A pertinent question is, who design the social convention? We assume nature acts as the principal, trying to maximize the fitness of the population by indirectly influencing agents’ behavior [Binmore, 1994]. The social convention based on the linear social rank can guide agents to avoid playing $(Hawk,Hawk)$, which is the only strategy profile that generates fitness loss ($C$) on the scale of the full population in the HD game (Figure 1).

In a complete information environment, each agent’s identity is common knowledge to all agents; therefore the agents can condition their strategies on their opponents’ identities for every possible opponent. However, given their limited cognitive abilities, it seems unrealistic to assume that all agents can access all others’ identities any time at no cost, especially in a large population. We use the concept of memory to model the limitations of the cognitive ability of the agents. The limitation is the maximum number of agents that an agent can have memory of, which we refer to as the individual memory size ($m$). In other words, the agents can memorize the identities of at most $m$ other agents, but not those of the rest. Once encountered, agents can recognize the identities of those who they remember. Therefore, on the one hand, the agents can prepare a corresponding strategy for each of the agents that they have a memory of, conditioned on the basis of their identities. On the other hand, they can have only one universal strategy of responding to the rest of the agents, whom they do not have a memory of, because they have no way to distinguish these opponents.

With limited memory, the predetermined social rank and the social convention will be effective for the agents only in situations when they are facing opponents with identities that they memorize. This is because social convention provides agents with suggestions on their actions according to their relative ranks to their opponents. If an agent does not know the identity of its opponent, it cannot act accordingly as suggested by the social convention.²²2It is still possible for the agents to infer the relative ranks between themselves and their opponents without having the identities of their opponents in memory. For example, the top ranked agent can infer that all its opponents have lower ranks; the bottom ranked agent can infer that all its opponents have higher ranks; the second top ranked agent who has the top ranked agent in its memory can infer that all other opponents have lower ranks. Nevertheless, inferring about the ranks of those agents that an agent has no memory of arguably requires strong cognitive ability, which cannot simply be modeled as memory. Hence, we do not consider such a possibility in this paper.

To summarize, in our model, a population of agents is randomly matched in pairs to play the HD game, as shown in Figure 1. Each agent in the population carries a unique number as its identity. The numbers provide a natural linear social rank among the agents. There is a social convention suggesting that agents play $Hawk$ against opponents with lower ranks, and play $Dove$ against opponents with higher ranks. Each agent can memorize the identities of a limited number of agents. We assume that all the agents in the population have the same memory capacity. Note that an agent is not required to use all of its memory. In addition, we do not explicitly model the cost of memorizing an agent’s identity. Nevertheless, if we encounter two equilibria that induce the same level of total fitness of the population and one equilibrium requires fewer memory slots than the other, we consider that the former is favored by natural selection.

Each equilibrium constructs a hierarchical social structure in the sense that it assigns each agent a hierarchical position resulting in some agents enjoying a higher fitness than the others. The assignment is purely based on the agents’ identities, which have nothing to do with superior rationality, information, or contribution.

However, the benefit of forming a hierarchical social structure may be more significant at the population level than at the individual level. Indeed, at the individual level, some agents (those with dominant roles in the hierarchies) may benefit and the rest (those with submissive roles) may suffer from a hierarchical social structure compared to an anarchical state where the only equilibrium is everyone always playing $M$. However, at the population level, a hierarchical social structure may increase the total fitness of the entire population (the sum of individual fitnesses), which helps the population stand out in the competition with other populations, if there are multiple populations. Hence, a population with a hierarchical social structure may be favored by natural selection.

We seek a social structure that maximizes the total fitness of the population. Recall that $(Hawk,Hawk)$ is the only strategy profile that generates fitness loss, and under our potential equilibrium social structures, this only happens when two players have equal status and they play $(M,M)$ (then $(Hawk,Hawk)$ occurs at a probability of $V^{2}/C^{2}$). Therefore, an optimal social structure must have the fewest pairs of agents with the same social status.

A secondary evaluation of the total fitness of the population is performed to examine the total memory usage among all agents. Memorizing an agent’s identity is potentially costly, although the cost may be minimal compared with the fitness loss from the $Hawk-Hawk$ clash in the game. Hence, we only use such an evaluation as a tie-breaker for social structures that provide the same level of total fitness.

First, we consider the case in which memory size is smaller than one. This occurs when agents’ cognitive ability is sufficiently low. Since the memory size is not sufficient for the agents to memorize the identity of any single agent, the only possible memory table for this population is as shown in Figure 4(A) (we use a population of five agents for illustration). Then, the only equilibrium strategy table that can be supported in this case is where everyone plays the mixed strategy in the mixed NE in the original HD game ($M$) to all others, as shown in Figure 4 (B). Thus, the corresponding social structure gives an anarchical (or some refer to it as egalitarian) social structure, as shown in Figure 5.

When evaluating the total fitness, because every pair in the population plays $(M,M)$, the probability of having a $Hawk-Hawk$ clash, the major source of fitness loss in the game, is $V^{2}/C^{2}$. Therefore, the expected fitness loss for each pair is $(V^{2}/C^{2})(C)=V^{2}/C$ and all agents have an identical average fitness value of $(1-V/C)(V/2)$. Note that in this case, the social convention is not followed as the agents cannot access others’ identities.

The agents are able to memorize all other agents’ identities if their memory size equals the population size minus 1 ($N-1$). In this case, with everyone’s identity in memory, each agent can condition its strategy for every possible opponent, making $(Hawk,Dove)$ and $(Dove,Hawk)$, in addition to $(M,M)$, possible equilibria in meetings between any two agents. Thus, in the population, there are $2^{\frac{N(N-1)}{2}}$ different ways to form a social structure in which each pair of agents is playing $(H,D)$ or $(D,H)$. Under such a social structure, every pair of agents is arranged with a dominant-submissive relation. Hence, there is no fitness loss in the population from the $Hawk-Hawk$ clash. We refer to these fitness-loss-free social structures as ordered social structures.

With the presence of linear rank in their identities and the fact that agents memorize the identities of all other agents, a linear social hierarchical structure (Figure 7) is the only ordered social structure that follows social convention. Figures 6 (A) and 6(B) show the corresponding memory table and strategy stable. Again, we use a population of five agents for illustration purposes.

We consider agents as having sufficient memory if they are able to memorize at least half minus one ($\lceil N/2-1\rceil$), but not all the identities of the other agents.³³3$\lceil x\rceil$ is the ceiling function, which gives the least integer greater than or equal to $x$. We demonstrate that sufficient memory is sufficient for a population to form an ordered social structure. In particular, we show that a linear hierarchy can be formed.

Note that if we treat the use of memory as a minor source of fitness loss, the optimal memory size that gives rise to the linear structure is $\lceil N/2-1\rceil$. Moreover, only the agent(s) situated in the middle of the linear social rank require(s) the use of its entire memory, while others can use less. Figure 8 (A) illustrates the optimal memory table for a population of five agents. We call this form of memory usage as a “triangular memory structure” because the usage of memory gradually increases as we move from either the top or the bottom toward the middle of the rank of agents, and the agents who need the largest memory size are those who are situated in the middle. The total memory usage is $\lceil N(N-2)/4\rceil$ for a triangular memory structure in a population of $N$ agents. When compared with Figure 6 (A), one can observe that the memory cost is greatly reduced in Figure 8 (A), and it is sufficient to ensure that the strategy table in Figure 8 (B) (identical to Figure 6 (B)) constitutes an equilibrium that follows social convention.

When the memory size is smaller than $\lceil N/2-1\rceil$, it is impossible for the population to form a linear hierarchical structure that follows social convention. Any equilibrium formed with agents’ memory size smaller than $\lceil N/2-1\rceil$ will involve some pairs of agents playing $M$ to each other, causing a fitness loss from the $Hawk-Hawk$ clash. Therefore, the optimal structures are those that induce the fewest pairs of agents playing $(M,M)$ as their equilibrium strategies.

We first examine the case in which the agents can memorize at the most one other agent’s identity, which we refer as the singular memory. We use a computational method⁴⁴4See the appendix for a description of the computation method. The code can be found at https://github.com/harrisonhhy/optimal_social_structure. to find all equilibrium social structures by examining all possible strategy tables that can be supported by at least one memory table (i.e., the agents must be able to perform the strategy they choose in the strategy table given the memory table). The results show that the despotic social system, where one agent dominates all others ($Hawk-Dove$ relation), is an equilibrium social structure that follows social convention and maximizes the total fitness in a population of five agents (Figures 9 and 10) and in a population of six agents as well.⁵⁵5Symmetrically, a social system in which one agent is dominated by all others is also an equilibrium social structure that follows social convention and maximizes the total fitness. Note that in a population with five agents, there exists another equilibrium social structure, which we refer as the “proxy despotism,” where the top-ranked (in the linear social rank) agent only dominates (plays $H$ to) the second top-ranked agent and plays $M$ with the rest. The second top-ranked agent dominates (plays $H$ to) all agents besides the top-ranked agent but plays $D$ to the top.⁶⁶6Symmetrically, a social system in which the bottom ranked agent is dominated by the second bottom ranked and the second top ranked agent is dominated by all agents beside the bottomed ranked agent is also an equilibrium social structure that follows social convention and maximizes the total fitness. It is equally as good as the despotic structure in terms of total fitness. As shown in Figure 11, proxy despotism has the same probability of having $Hawk-Hawk$ clash as the despotic social structure (4 out of 10 pairs do not have clash). However, their difference is that the proxy despotism requires full use of all agents’ singular memory size, while under the despotic structure, the use of memory for the top-ranked agent can be waived. Consequently, the despotic social structure has a fitness advantage over the proxy despotic structure. This may explain their relative frequencies (Sasaki et al. [2016]).

The intuition behind the optimality of the despotic social structure is that when the top-ranked agent is memorized by all others, each usage of memory creates a non-clash ($Hawk-Dove$) pairwise interaction between the top-ranked agent and the agent who uses the memory (in the example of a population with five agents, there are four memories used and four corresponding non-clash relations).

More generally, we conjecture that with insufficient memory ($1\leq m<\lceil N/2-1\rceil$), the optimal way for agents to use their memories in terms of social efficiency is described as follows.⁷⁷7We thank an anonymous reviewer for the suggestion. There are $m$ out of $N$ agents, marked as group A, and other $N-m$ agents, marked as group B. Agents in group A form a clash-free linear hierarchy among themselves, and the most fitness-efficient way to do so is to use the triangular memory structure according to Proposition 1. Under the triangular memory structure, agents in group A will be separated into two halves, where the higher-ranked half (lower-ranked half) agents only memorize agents who have higher (lower) ranks than them, and then they play $D$ ($H$) to the agents in their memory and $H$ ($D$) to those who are not in their memory (including those agents in group B). The $N-m$ agents in group B will memorize (and only memorize) all agents in group A, play $D$ to the higher-ranked half in group A, play $H$ to the lower-ranked half in group A, and play $M$ to other agents in group B, whom they do not memorize, forming an anarchical/egalitarian sub-social structure within group B. With this form of memory structure and the corresponding strategies, all $m(N-m)$ pairs between group A and group B agents and $m(m-1)/2$ pairs among group A agents have $Hawk-Dove$ as their strategies in equilibrium. Hence, there are $(m(N-m)+m(m-1)/2)$ out of $N(N-1)/2$ clash-free pairs, and every one pairwise clash-free relation is maintained by at most one memory. Specifically, the $H-D$ relationship between a group A agent and a group B agent is maintained by the group B agent’s memory of the group A agent. The $H-D$ relation between a pair of agents within the higher-ranked (lower-ranked) half in group A is maintained by the lower-ranked (higher-ranked) agent’s memory of the higher-ranked (lower-ranked) agent. The $H-D$ relation between one agent from the higher-ranked half and one agent from the lower-ranked half in group A requires no memory to sustain. We call this social structure the “three-layer dominance hierarchy” because society is separated into three classes. When $m$ is even, the upper class contains the top $m/2$ ranked agents with a linear hierarchy, the middle class contains the middle $N-m$ ranked agents with an egalitarian social structure, and the lower class contains the bottom $m/2$ ranked agents with a linear hierarchy. When $m$ is odd, the upper class contains the top $\lceil m/2\rceil$ (or $\lceil m/2\rceil-1$) ranked agents, and the lower class contains the bottom $\lceil m/2\rceil-1$ (or $\lceil m/2\rceil$) ranked agents. The total amount of memory required for the three-layer dominance hierarchy is $m(N-m)+\lceil m(m-2)/4\rceil$. Note that the despotic social system is consistent with the description of the three-layer dominance hierarchy for the special case of $m=1$. Figure 13 provides a general illustration of the “three-layer dominance hierarchy”

We confirm our conjecture in a population of seven agents with $m=2$, using our computation method. The social structure at equilibrium that induces the least fitness loss is that the top-ranked agent dominates all others, the bottom-ranked agent is dominated by all others, and the remaining five agents form an egalitarian social structure among themselves. This is supported by a memory structure where the five middle-ranked agents memorize the top-ranked and the bottom-ranked agents, and the top- and bottom-ranked agents do not memorize any agent (Figures 14 and 15).