## Abstract

All organisms with sexual reproduction undergo a process of mating, which essentially involves the encounter of two individuals belonging to different sexes. During mate search, both sexes should mutually optimize their encounters, thus raising a question of how they achieve this. Here, we show that a population with sexually dimorphic movement patterns achieves the highest individual mating success under a limited lifespan. Extensive simulations found and analytical approximations corroborated the existence of conditions under which sexual dimorphism in the movement patterns (i.e. how diffusively they move) is advantageous over sexual monomorphism. Mutual searchers with limited lifespans need to balance the speed and accuracy of finding their mates, and dimorphic movements can solve this trade-off. We further demonstrate that the sexual dimorphism can evolve from an initial sexually monomorphic population. Our results emphasize the importance of considering mutual optimization in problems of random search.

## 1. Introduction

The most elemental process underlying all kinds of sexual reproduction is syngamy—that is, the fusion of two gamete cells of different mating types. This creates the need to mate (searching and fusing) in individual organisms with sexual reproduction, from isogamous microorganisms to multicellular males and females. Consequently, successful mating emerges as a vital component of fitness for both mates, giving each mate various opportunities to evolve sex-specific characteristics for improved mating success. These characteristics range from principal differentiation of gamete size and number between males (sperm) and females (eggs)—that is, anisogamy [1,2]—to diverse secondary sexual characteristics, including sexually selected communication systems [3,4].

One fundamental prerequisite for biological interactions is that individuals or their gametes move [5]. Here, we focus on the patterns of movement of individuals during the search for a mate. All else being equal, do differential movement patterns between sexes improve mating success? In other words, can sexually dimorphic movement patterns evolve in isogamous cells or in otherwise sexually monomorphic animals?

In the biophysical study of movement patterns, much attention has been paid to the random search problem, which considers how an agent should move to search for targets in the absence of their locational information [5]. The leading hypothetical solution to the problem has been the Lévy walk search (or foraging) hypothesis [6,7], which states that the Lévy walk—a special class of random walk models—should be employed by foragers evolving in the real world because of its relatively high efficiency compared with those of other classes of random walks. A Lévy walker leaves a trajectory with a step length that is defined by straightforward movements between successive changes of direction; the frequency distribution of step lengths follows a certain power-law distribution—that is, there are typically many short-step movements interrupted by rare ballistic ones that are key to higher searching efficiency. Although previous empirical researches have shown that a wide range of animal species perform Lévy-like multi-scale movement in their foraging behaviours [8–11], it has also been demonstrated that some animals shift from Lévy walk to Brownian walk depending on environmental conditions [12]. This calls for further assessment of conditions under which the Lévy walk leads to efficient foraging.

One factor—among others—affecting foraging efficiency is how efficiency is evaluated [13,14]. In evolving biological systems, efficiency is translated into fitness. Fitness can be affected by the search time allowed for the foragers (e.g. lifespan) when the conditions of the targets, such as their abundance and spatial distribution, change over time. This biological reality should be incorporated into studies of the random search problem. Another factor is what the target object is. Although previous theoretical studies have acknowledged that foraging can be for arbitrary types of targets (food, mates or habitats), most have assumed, explicitly or implicitly, that foraging is for food; they have assessed how many prey items a predator can find ([7,15,16] but see [9]). One major difference between foraging for food and foraging for mates is that in the latter case, both males and females can modify their patterns of movement to optimize their encounter rates. Such a random ‘mutual search problem’ has been largely overlooked in studies of the random search problem. Importantly, movement patterns can differ between males and females during the course of maximization of the encounter efficiency; this should provide a novel context in which sexual dimorphism evolves.

Our approach to the mutual search problem lies at the intersection of two research fields, namely evolutionary ecology of sex and biophysics of movement. Our model mimics the biology of isogametes (a gamete without sexual differences in size and shape) of green algae such as *Chlamydomonas*, so that they only move and fuse with their counterpart to form a zygote [17,18]. We start with a simplified model of mutual search in which a male and a female search for each other with certain patterns of random walk in one-dimensional space. Fitness is measured by how likely it is that they encounter one another within a given time frame. Then, we extend it to entail multiple males and females in two-dimensional space. Moreover, we perform coevolutionary simulations and compare evolved patterns of movement between males and females, assessing whether and in what conditions sexual dimorphism of movement patterns evolves.

## 2. Methods

In this study, we use simple models to understand how efficient mutual search of male(s) and female(s) using similar or disparate random walk strategies are for finding mates within a certain time window. The two mating types are denoted by ‘male’ and ‘female’ for notational convenience, but they can be any kind of mating types. Because males and females differ only in their movement patterns (not in size or lifespan), they are interchangeable in our analyses.

We considered the reproductive biology of marine green algae as a model system of our study [17,18]. Most green algae species have two mating types. These mating types are morphologically indistinguishable, but fusion takes place only between gametes of different types (i.e. isogametes [19–21]). Their life cycles are as follows: in every generation, haploid vegetative individuals of each mating type produce gametes by asexual divisions. Each gamete fuses with that of the other mating type to produce a diploid zygote, which persists for some time and then divides to produce a new haploid generation of vegetative individuals. We focused on this gamete fusion process of two different mating types.

Because isogametes no longer search for mates after zygote formation, we assumed a monogamous mating scheme with a 1 : 1 sex ratio (*n*_{m} males and *n*_{f} females searching) under which a male mates with only one female (and vice versa) during its lifespan. On encountering one another, the pair disappears from the searching space; we call this ‘pair annihilation’. The fitness of an individual is then evaluated by the probability that a male and a female meet no later than *t*_{max} units of time (i.e. they reach *t*_{max} steps).

As movement patterns, we considered Lévy walks in which the probability density function of step length *l* has a power-law tail: *P*(*l*) ∼ *l*^{−μ}. The variable *μ* is a power-law exponent that describes the degree of diffusion (1 < *μ* ≤ 3; here, we considered 1.1–3.0 in a bin of 0.1): with *μ* = 1.1, the walker performs a highly diffusive (or ballistic) walk; with *μ* = 3.0, it performs a typical random walk (i.e. Brownian walk) and shows the lowest diffusion; with *μ* = 2.0, it shows a typical Lévy walk pattern with intermediate diffusion. Males and females can have different *μ* values, each denoted by *μ*_{m} and *μ*_{f}. Throughout the analyses, the movement velocity was set at *v* = 1 step per unit time for both males and females; that is, they differed only in their *μ* values.

### 2.1. Individual-based model

We developed an individual-based model to examine whether sexually dimorphic movement patterns could enhance the encounter efficiency of the mutual search. Values and ranges of parameters are given in electronic supplementary material, table S1. The simulation program was implemented in Microsoft Visual Studio C++ 2012.

In our simulations, we considered *n*_{m} male(s) and *n*_{f} female(s) searching for the other sex in a borderless continuous space by performing a Lévy walk at a velocity of *v* until encountering another individual of the other sex. All individuals have spherical bodies with the same diameter *Φ* (=1). When the distance between the centres of a male and a female becomes smaller than *Φ*, the two individuals encounter one another. In this study, we did not consider the encounter of two same-sex individuals that does not result in zygote formation. In one-dimensional simulations, a male and a female are initially separated by the distance *d*, whereas in two-dimensional simulations, multiple males and females are randomly distributed on a square grid, separated by at least *d* (electronic supplementary material, figure S7). A simulation lasts until the maximum search time, *t*_{max}.

The Lévy walk model comprises a rich variety of movements ranging from Brownian motion (*μ* ≥ 3) to ballistic paths (*μ* → 1). Lévy walk is characterized by a power-law distribution for the move lengths, *P*(*l*) ∼ *l*^{−μ} (1 < *μ* ≤ 3), and a uniform distribution for the turning angles [–*π*, *π*]. After generating a uniform random number *u* (0 < *u* ≤ 1), we derived move lengths from the following equation: *l* *=* *l*_{0}*u*^{1/(1–μ)}, where *l*_{0} (= 1) is the minimum move length and *μ* the power-law exponent. The Lévy walk was obtained as follows: once a move length and a direction are sampled from the respective distributions, an individual incrementally walks in a straight line until reaching the specific move length while looking for a mate along its way. We covered the case that an encounter occurred while an individual is on the move by segmenting a move length per unit time (*v*) into 10 substeps and checking the occurrence of encounters at the end of each substep. In simulations to assess the mutual search efficiency of each movement pattern with power-law exponent *μ*, we assumed that all males and all females had the same trait *μ*_{m} and *μ*_{f}, respectively, ranging from 1.1 to 3.0 by 0.1. For each parameter set, we ran 10 000 000 one-dimensional simulations and 1000 two-dimensional simulations to record how many pairs encountered one another by the maximum time *t*_{max}. We set *d* as 4, 10 and 50 for one-dimensional simulations and 10 for two-dimensional simulations. We also examined the temporal development of the distribution of pairwise distances between a male and a female for one-dimensional simulations, where 1 000 000 replications were run with *d* set as 10.

### 2.2. Analytical solution

We explored the analytical solution for the encounter rate of a male and a female in one-dimensional space. We assume that one male and one female move in a non-boundary discrete space in each time step with a constant speed (1 unit distance per time step). We denote their positions at time *t* as *x*_{m}(*t*) and *x*_{f}(*t*). For analytical convenience, we approximated Lévy walkers with *μ* = 3.0 as Brownian walker (BW) and those with *μ* = 1.1 as straight walker (SW) throughout the analysis. The BWs move randomly to the position next to the present one in each time step. In other words, they move from *x*(*t*) to *x*(*t*) + 1 or *x*(*t*) – 1 at probability 1/2. The SWs move unidirectionally after randomly choosing a movement direction at *t* = 0. If the two individuals simultaneously come to the same position—that is, *x*_{m}(*t*) = *x*_{f}(*t*)—they meet and then never move. Here, we obtain the probability *P*(*t*_{max}, *d*) that the male and female will encounter one another within time step *t*_{max} when the initial distance between them *x*_{m}(0) – *x*_{f}(0) is *d*. Note that *d* is an even number because we consider that the two individuals meet at the same position.

When the male and female are both SWs (approx. *μ* = 1.1), the probability that they encounter one another within *t*_{max} is 1/4 because they always meet only when they choose the direction facing each other and walk by just *d*/2 steps. In the other cases, they can never encounter one another. Thus, we obtain
2.1

Next, we consider the case in which the male and female are an SW (approx. *μ* = 1.1) and a BW (approx. *μ* = 3.0), respectively. If the SW chooses a direction in which the BW does not exist, then they cannot encounter one another, whereas if the SW chooses the direction in which the BW exists, there is a possibility that they will meet. We denote the relative distance as *X*(*t*) = [*x*_{m}(*t*) – *x*_{f}(*t*)]/2. A (*d*/2 + 1) × (*d*/2 + 1) transition matrix **A** that represents the probability that *X* changes from *i* to *j* in one time step is described as follows: **A**_{11} = 1, **A**_{ii}*=* 1/2 (2 ≤ *i* ≤ *d*/2 + 1), **A**_{i}_{(i–1)} *=* 1/2 (2 ≤ *i* ≤ *d*/2 + 1), and the other elements are 0. The vector **p** with length (*d*/2 + 1) representing the distribution of the initial relative position is (0, 0, … , 1), and thus we obtain
2.2where (·)_{1} represents the first element of the vector.

When the male and female are both BWs (approx. *μ* = 3.0), a (*d*/2 + *t*_{max} + 1) × (*d*/2 + *t*_{max} + 1) transition matrix **B** that represents the probability that the relative distance *X* changes from *i* to *j* in one time step is described as follows: **B**_{11} = 1, **B*** _{ii}* = 1/2 (2 ≤

*i*≤

*d*/2 +

*t*

_{max}+ 1),

**B**

_{i}_{(i–1)}= 1/4 (2 ≤

*i*≤

*d*/2 +

*t*

_{max}+ 1),

**B**

_{i}_{(i}

_{+}

_{1)}= 1/4 (2 ≤

*i*≤

*d*/2 +

*t*

_{max}) and the other elements are 0. The vector

**q**with length (

*d*/2 +

*t*

_{max}+ 1) is (0, 0, … , 1, … , 0), where the (

*d*/2 + 1)th element is 1, representing the distribution of the initial relative position. Thus, we obtain 2.3where (·)

_{1}represents the first element of the vector.

### 2.3. Scaling of the searching process

The parameters that can affect our results are the number of individuals (*n*_{m} and *n*_{f}), the diameter of an individual (*Φ*), the minimum move length (*l*_{0}), the distance separating individuals (*d*), the moving velocity (*v*) and the length of lifespan (*t*_{max}). Assuming *Φ* to be the same as *l*_{0}, our model system of searching process with a given number of individuals can be scaled into the system with two composite parameters *l*_{0}/*d* and *vt*_{max}/*d*. A sensitivity analysis was performed to know how these two composite parameters affect the optimal combination of males’ and females’ movement patterns. We explored the range of 0.01 < *l*_{0}/*d* < 0.25 and 0.5 < *vt*_{max}/*d* < 50 using one-dimensional simulations with a male and a female. For analytical solutions, we also examined the relationship between the corresponding composite parameters in a similar procedure.

### 2.4. Evolutionary simulations

Finally, we performed evolutionary simulations to examine whether a sexually dimorphic state was achievable from the ancestral sexually monomorphic state as a result of selection acting on the encounter efficiency. We simulated isogametes with two mating types, which were variable only in their movement patterns. Isogamy with two mating types is often assumed as the ancestral state in models of the evolution of anisogamy [20,22,23]. We investigated whether selection acting on the efficiency of encounters drove the evolution of differential movement patterns between the sexes. We assumed that, within a generation, a total of *n* individuals (corresponding to gametes) with equal numbers of males and females (*n*_{m} and *n*_{f}) move in a two-dimensional borderless continuous space and search for individuals of the opposite sex. The searching condition is the same as that in the two-dimensional simulations described above. On encountering one another, the pair stops searching and disappears from the searching space to produce zygotes by fusion. We assumed that reproduction was allowed only for a subset of individuals that had encountered their mates before the proportion of mated individuals reached *r* (0 ≤ *r* ≤ 1). The parameter *r* can be regarded as the inverse of selection intensity. The selection acts on how fast individuals encounter a mate with small *r* and how likely it is that they will encounter one with large *r*. Note that *r* corresponds to *t*_{max} in the above simulations. Searching time lasts until the proportion *r* of individuals encountered or the maximum search time *t*_{max} (=1500) is reached. Then, each zygote divides to produce vegetative individuals, which produce a large number of gametes with a 1 : 1 sex ratio and die. Then, *n*_{m} males and *n*_{f} females are chosen from the offspring to start mating in the next generation.

We considered the power-law exponent *μ* for Lévy walk as an evolving, sex-specific genetic trait. All individuals have their own *μ* values that are inherited by their same-sex offspring with mutations described below. In other words, in our simulations, we assumed haploid genetics without recombination, whereby the gene determining *μ* links to the respective male- and female-determining loci; this is similar to the assumption of the link between loci determining sex and gamete size [18,24]. Mutations take place during the formation of next-generation individuals at a rate of 0.001, where the *μ* value increases or decreases by 0.1 between 1.1 and 3.0. The initial *μ* value, *μ*_{0}, was set at 3.0 for all individuals.

Simulations were performed for 200 000 generations. We calculated the mean *μ* values for males and females at each generation. Then, we evaluated the evolution of sexually dimorphic movement patterns by comparing the distribution of the 50 000 data points of respective *μ* values for males and females over 150 000 and 200 000 generations. We determined the sexual dimorphism by the non-overlap of 95% confidence intervals of the *μ* value distributions for males and females. We tested 336 parameter sets: 16 values of *r* ranging from 0.05 to 0.80 by 0.05 and 21 values of *n* (100, 144, 196, … , 2500).

## 3. Results

First, we simulated the case of *n*_{m} (=*n*_{f}) = 1 in a one-dimensional searching space without boundaries. When the lifespan was intermediate (e.g. 10 < *t*_{max} < 30; initial distance between a male and female *d* = 10), a sexually dimorphic pair of a walker with higher diffusion (e.g. *μ* = 1.1) and one with lower diffusion (e.g. *μ* = 3.0) achieved the highest fitness (figure 1*a,c,d*). Under shorter and longer lifespans, a sexually monomorphic pair of walkers with higher diffusion (*μ*_{m} = *μ*_{f} = 1.1) and of those with lower diffusion (*μ*_{m} = *μ*_{f} ∼ 3.0), respectively, achieved the highest fitness (figure 1*a,c*). These trends did not depend on the initial distance of a male and a female, *d* (electronic supplementary material, figures S1 and S2).

In more detail, the encounter rate of walkers with relatively high *μ* values (e.g. *μ* = 2.0, 2.5 and 3.0) increases gradually as their lifespan increases, whereas the encounter rate of a ballistic (*μ* = 1.1) walker increases early in the lifespan and is immediately saturated; this provides the highest encounter rates with a Brownian (*μ* = 3.0) counterpart when lifespan is intermediate (figure 1*a*). We examined how this saturation pattern of encounter rate could be caused by the combination of movement patterns of a ballistic and a BW. During their lifespans, ballistic walkers tend to go straight in one direction, whereas BWs tend to remain around their initial location (electronic supplementary material, movie S1). Therefore, if the ballistic walker moves correctly towards his or her Brownian counterpart, most such pairs can encounter one another quickly (around *t*_{max} = *d*); if the ballistic walker moves erroneously in the opposite direction, the distance between the pair increases with time, so that they rarely meet successfully (figure 2; electronic supplementary material, movies S2 and S3). This explosive increase in encounter rate in sexually dimorphic pairs easily exceeds the gradual encounter rate in pairs of walkers with relatively high *μ* values, whereby they maintain a certain probability of encounter across time—that is, a certain number of males and females maintain a short distance even at large *t*_{max} (figure 2). Thus, a sexually dimorphic pair of a Brownian (*μ* = 3.0) walker and a ballistic (*μ* = 1.1) walker can achieve the highest encounter rate with intermediate lifespan at the expense of a quite low probability of encounter later in the lifespan.

The simulation results were corroborated by analytical solutions obtained with BW (approx. *μ* = 3) and SW (approx. *μ* = 1.1). We numerically calculated *P*(*t*_{max}, *d*) for SW–SW, SW–BW and BW–BW pairs from equations (2.1) to (2.3) and simulated this model with 5000 iterations for *d* *=* 4, 10, 50. Figure 1*b* and electronic supplementary material, figures S1*b* and S2*b* show the encounter rates of SW–SW, SW–BW and BW–BW, respectively. When *t*_{max} is short, the encounter rate of SW–SW is highest. At the intermediate level of *t*_{max}, SW–BW has the highest encounter rate. When *t*_{max} is long, the BW–BW pair is the most efficient at encountering a mate. These qualitative trends are consistent with the result for Lévy walkers with various power-law exponents (1.1 < *μ* ≤ 3.0), as shown in figure 1*a*; electronic supplementary material, figures S1*a* and S2*a*.

The effect of the values of the parameters is shown in figure 3. The results showed that whether a sexually dimorphic pair can achieve the highest encounter rates is little affected by the composite parameter *l*_{0}/*d* (figure 3). This is consistent with the fact that the ranges in which sexual dimorphic pairs achieve the highest mating efficiency are roughly the same across different *d* (figure 1*c*; electronic supplementary material, figures S1*c* and S2*c*). On the other hand, the optimal combination of males' and females' movement patterns strongly depended on *vt*_{max}/*d* (figure 3), suggesting that whether a certain length of lifespan is short, long or intermediate can be determined by the values of *v* and *d*.

Then, we proceeded to the case of multiple individuals in a two-dimensional searching space without boundaries. The result was qualitatively similar to the one-dimensional case (electronic supplementary material, figure S3). Although the optimal combinations of *μ*_{m} and *μ*_{f} varied depending on the population size and the lifespan, sexually dimorphic movement patterns enhanced the mating encounter rate with a certain lifespan irrespective of the population size (figure 4; electronic supplementary material, figure S3).

Finally, our results of evolutionary simulations show that dimorphic movement patterns evolve under an intermediate *r* (figure 5; electronic supplementary material, figure S4). As population size increases, the strength of selection *r* with which dimorphic movement patterns evolve also slightly increases (figure 5). This is because, with a large number of individuals, the risk of moving in a direction without mates declines and thus the rate of encounter of highly diffusive walkers improves.

## 4. Discussion

In our pair-annihilation system, because each individual encounters only one individual of the other sex, the fitness of each individual (gamete or animal) is shaped by two components: (i) how likely it is that he or she will encounter an individual of the other sex and (ii) how quickly this happens. These two components are in a trade-off relationship. A highly diffusive (e.g. *μ* = 1.1) walker can quickly encounter a mate, but the likelihood of encounter will soon be saturated because his or her mates are not distributed all over the searching space; this situation should be common in the real world. By adopting a less diffusive (e.g. *μ* = 3.0) walk, the waiting time until an encounter will be longer, but the likelihood of encounter will be markedly elevated over time. The importance of balancing these two components depends on the search time allowed for the mate searchers (*t*_{max} in the model): a shorter search time makes highly diffusive walkers advantageous and a longer search time makes less diffusive walkers advantageous. With an intermediate search time, we found that individuals in a sexually dimorphic population of highly and less diffusive walkers can manage this speed and accuracy trade-off [25] even better than individuals in a sexually monomorphic population of typical Lévy walkers with intermediate *μ* values (*μ* ∼ 2.0). In addition, our two-dimensional simulations can be easily extended to a three-dimensional simulation, which would be a more accurate approximation of the environment for algae. As the risk of a ballistic walk must become higher in three-dimensional conditions, one can expect that individuals in a sexually dimorphic population achieve the highest fitness with a shorter lifespan *t*_{max} (or larger selection strength *r*), compared with two-dimensional conditions.

An important assumption is the infinite and borderless searching space. This provides highly diffusive walkers with the risk of searching in an area without mates, and thus mutual searchers need to balance the speed and accuracy trade-off in searching for their mates. Under periodic boundary conditions (PBCs) with multiple individuals, the above risk is cancelled out because mates can become distributed all over the searching space. Consequently, individuals in a sexually monomorphic population of ballistic walkers achieved the highest fitness (electronic supplementary material, figure S5); this finding is consistent with the results of a previous study of a scheme of foraging for food under PBCs [16]. Even under PBCs, however, if we consider the conditions of two individuals in a one-dimensional space, the combination of a ballistic searcher and a Brownian target can achieve the highest encounter efficiency; this has been mentioned as an artefact of adopting PBCs [16] (electronic supplementary material, figure S6). Under such conditions, there is a risk of both individuals moving straight and in the same direction and continuing to chase each other. Combined with the results obtained from the PBC model (see also [16,26]), our findings emphasize the importance of considering the risk of a ballistic walk in real biological situations, where the advantage of movement that is too highly diffusive would be overestimated.

Our evolutionary simulations revealed that the coevolution between sexes occasionally leads to sexually dimorphic movements from sexually monomorphic ancestors. This result can be understood intuitively by interpreting figure 1*d* and electronic supplementary material, figure S3 as fitness landscapes (note that we show only *μ*_{m} ≥ *μ*_{f}). The slope towards the fitness maximum is sometimes so shallow that the stability of the dimorphism can be affected by the population size, mutation rate and its phenotypic effect. Our simulations were consistent with measurements of mating efficiency (figure 1*d*; electronic supplementary material, figure S3), in that the intermediate time span for mate search favours the sexual dimorphism of movement patterns. This suggests that sexual dimorphism is evolutionarily achievable and that its evolution is attributed to its advantage in mating encounters. Previous theoretical studies on the evolution of sex considered anisomotile (sexually dimorphic motion) as a derived trait associated with the other aspects of anisogamy (e.g. gamete dimorphism or pheromone production) (reviewed in [2]). Our study thus adds to those studies by showing that differential movements between sexes can arise only from the selection acting on mating encounters, other things being equal.

The best combination of {*μ*_{m}, *μ*_{f}} varied over *t*_{max} (figures 1*c* and 4), and a sexually dimorphic pair (i.e. *μ*_{m} ≠ *μ*_{f}) achieved the highest mating efficiency roughly within the range of *d* < *t*_{max} < 10*d* in one-dimensional simulations (figures 1*c* and 3; electronic supplementary material, figures S1*c* and S2*c*) and 10*d* < *t*_{max} < 100*d* in two-dimensional simulations (figure 4). As we fixed the moving velocity to 1, this observation indicates that the condition favouring sexually dimorphic movements is when the search time available is enough to move about 1–100 times as long as the shortest initial distance between mates. In a biological context, the available search time is determined by the individual's lifespan, the physiological state suitable for mate search and the environmental conditions and the initial distance is determined by the population density. We feel that many species would fall within this range. Empirical demonstration of sexual differences in movement patterns using algal isogametes, together with measurements of their available search time, moving velocity and their population density (a proxy of *t*_{max}, *v* and *d*, respectively), will validate our prediction. Comparison among populations or among species would also be a promising approach.

Our model can also be applied to the case of sexually monomorphic animals, where a female mates with a male to form a monogamous pair. Sexual differences in the movement patterns has been observed in various animal taxa. In some species of copepods, for example, sexually different movement patterns have been detected [27,28]. Mammals such as macaques and grey seals show sexually dimorphic movement patterns when foraging for food [29,30]. The sexual difference has been hypothesized to be a driver of sex-dependent spatial distributions [31]. These can be a consequence of differential degrees of sexual selection between sexes. For example, male–male competition can favour larger and more energy-consuming males [32], leading to sexually different foraging strategies with males moving more diffusively to obtain more prey items than females [29,30]. Our results provide an alternative explanation for the sexual dimorphism in movement patterns by suggesting that it may evolve for its own sake as a result of mutual optimization for mating encounters. This mechanism works even in animals with lifelong monogamy (i.e. with the least intensity of sexual selection). A potential candidate could be found in subterranean termites. After newly emerged adult termites fly off to disperse from their natal colonies, they shed their wings and run to search for mates without food and locational information; the resulting pair then becomes the royals and maintains lifelong monogamy [33]. Further studies will clarify how the sexually dimorphic movement patterns are associated with the other sexually selected traits.

More generally, the mutual search problem can be applied to any social, biological or biochemical systems involving pairwise interactions between agents, such as mutualistic partners wishing to find each other, as assumed in rendezvous problems [34]; enzymes and their substrates [35]; proteins and their target DNA [36–38] and even between two complementary strands of DNA undergoing polymerase chain reactions. An individual's encounters also may have different fitness (or payoff) consequences depending on the movement strategies of their counterparts, as well as their own, placing the mutual search problem and the classical random search problem along a game-theoretic continuum (see also [26]).

In conclusion, our study showed that mutual search strategies in biological systems are shaped by a coevolutionary feedback between two types of searching agents. Coevolutionary optimization of male and female strategies can result in the emergence of sexually dimorphic movement patterns, thus providing a novel mechanism for the initial evolution of sexual dimorphism. By considering the process of co-optimization of interactions between moving agents, our findings will provide a new direction for identifying the movement patterns that organisms really follow.

## Data accessibility

All data needed to evaluate the conclusions in the paper are present in the paper itself and in the electronic supplementary materials or are available upon request from the authors. Source codes are available from the Dryad Digital Repository: http://dx.doi.org/10.5061/dryad.303hh [39].

## Authors' contributions

N.M., M.S.A. and S.D. conceptualized the study; N.M. simulated extensively; M.S.A. solved analytically; N.M., M.S.A. and S.D. wrote the paper.

## Competing interests

We declare we have no competing interests.

## Funding

This study was supported by Grants-in-Aid for Scientific Research 15J02767 (N.M.), 15H06830 (M.S.A.) and 15K18609 and 26891015 (S.D.) from the Japan Society for the Promotion of Science.

## Acknowledgements

We thank two anonymous referees who significantly improved the manuscript.

## Footnotes

Electronic supplementary material is available online at https://dx.doi.org/10.6084/m9.figshare.c.3759545.

- Received February 5, 2017.
- Accepted April 19, 2017.

- © 2017 The Author(s)

Published by the Royal Society. All rights reserved.