key: cord-0704175-l0cd8a7b
authors: Alpern, Steve; Zeng, Li
title: Social Distancing, Gathering, Search Games: Mobile Agents on Simple Networks
date: 2022-02-02
journal: Dyn Games Appl
DOI: 10.1007/s13235-022-00427-1
sha: 94e554dd7c8880eb463493486c367bb74304b3e9
doc_id: 704175
cord_uid: l0cd8a7b

During epidemics, the population is asked to socially distance, with pairs of individuals keeping two meters apart. We model this as a new optimization problem by considering a team of agents placed on the nodes of a network. Their common aim is to achieve pairwise graph distances of at least D, a state we call socially distanced. (If [Formula: see text] they want to be at distinct nodes; if [Formula: see text] they want to be non-adjacent.) We allow only a simple type of motion called a lazy random walk: with probability p (called the laziness parameter), they remain at their current node next period; with complementary probability [Formula: see text] , they move to a random adjacent node. The team seeks the common value of p which achieves social distance in the least expected time, which is the absorption time of a Markov chain. We observe that the same Markov chain, with different goals (absorbing states), models the gathering, or multi-rendezvous problem (all agents at the same node). Allowing distinct laziness for two types of agents (searchers and hider) extends the existing literature on predator–prey search games to multiple searchers. We consider only special networks: line, cycle and grid.

To combat epidemics, three actions are recommended to the public: mask wearing, hand washing, social distancing. This paper models the last of these in an abstract model of mobile agents on a network. Social distancing can be considered a group goal (common-interest game) or individual goal (antagonistic, non-cooperative game). We consider both goals in a dynamic model where agents (players) walk on a network (graph). A group of m players, or agents, is placed in some way on the nodes of a network Q. Each agent adopts a lazy random walk (LRW) which stays at his current node with a probability p (called laziness) and moves to a random adjacent node with complementary probability 1 − p (called speed). In the common interest game, we seek a common value of p which minimizes the time for all pairs of players to be at least D nodes apart (socially distanced). Once p is adopted by all, the positions of the agents on the network (called states) follow a Markov chain, with distanced states as absorbing. Standard elementary results on absorption times for Markov chains are used to optimize p, to find the value of p which if adopted by all agents minimizes the absorption time. This work can be seen as an extension to networks of the spatial dispersion problem introduced by Alpern and Reyniers [8] , where agents could move freely between any two locations. That paper also allowed agents knowledge of populations at other locations, whereas here agents have no knowledge of the whereabouts of other agents. (In some cases, we do allow an agent to know the population at his current node, with laziness p i at such a node dependent on the number i of agents at the node. ) We observed that by changing the states which we call absorbing (and not allowing transitions out of these), we can usefully model other existing problems. For example, by taking the absorbing states as those where all agents occupy a common node, we model the multirendezvous (or gathering) problem, and our results extend known results for m = 2 agents on a network found in Alpern [2] . We assume the sticky form of the problem, where agents who meet coalesce into a single agent and move together subsequently. Rendezvous problems were introduced by Anderson and Weber [9] and Alpern [2] in discrete and continuous models. Rendezvous with agents on graphs have been studied in Alpern, Baston and Essegaier [6] and Alpern [4] . See also Gal [16] , Howard [19] and Weber [27] . A survey is given in Alpern [3, 4] .

We also consider a model with two types of agents called searchers and hiders (or predators and prey), who can choose different speeds. Here, the payoff is related to the search or capture time (when a searcher coincides with a hider), with the searchers as minimizers and the hiders as maximizers in a two-person team search game. These problems were proposed by Isaacs [20] and first studied by Zelikin [28] , Alpern [1] and Gal [14] , and later by many others. See Gal [15] and Alpern and Gal [7] for monographs on search games. Until now, such problems with capture time payoffs have mostly had one searcher and one hider. All of these problems start in some prescribed, or possibly random, position and end when the desired position is reached. For rendezvous or search (hide-seek), reaching the desired position clearly ends the game, as all agents will know this. For dispersion, some binary signal (a siren from an observing drone) might ring until a distanced position is reached.

As mentioned above, the forerunner to social distancing problems is the related spatial dispersion problem of Alpern and Reyniers [8] . They consider n locations (with no network structure, so they did not call them nodes, as we do here) with n agents placed randomly on them. The aim to obtain a dispersed situation with one agent at each location (two agents are not allowed to be at the same location). This would correspond to a value of pairwise distance at least D = 1 and m = n in our model. We will also consider this situation at times in this paper. They also considered m = kn agents with the aim of getting k agents at each location. After each period, the distribution of agents over the locations becomes common knowledge. That problem modeled a situation where drivers can take any of n bridges, let us say from New Jersey into Manhattan, and the distribution of yesterday's traffic is announced every night. The aim is to equalize traffic over the bridges for the common good. Grenager et al [18] extended that work to computer science areas and Blume and Franco [11] to economics. See also Simanjuntak [25] .

It is clear that ours is an extremely abstract approach to the problem of social distancing. For a very recent practical analysis of the impact of social distancing on deaths from Covid-19, including a monetary equivalent, see Greenstone and Nigam [17] . For mental health implications of social distancing, see Venkatesh and Edirappuli [26] and for an economic analysis set Maryam Farboodi et al [13] . This paper is organized as follows. Section 2 describes our dynamic model of agents moving on a network according to a common lazy random walk and derives the associated Markov chain. A formula for the time to absorption (desired state) is derived. Section 3 gives some simple examples where the agents attempt to social distance on the cycle graph C n . Section 4 considers several different problems, all having three agents on C 3 : social distancing (4.1), gathering (4.2), a zero sum game with a team of two searchers seeking one hider (4.3). Section 5 considers gathering (5.1) and social distancing (5.2) on C 5 . Section 6 considers a game where n players start together an end of a line graph, each choosing their own laziness in a lazy random walk. At the first time periods where some agents are alone at their node, these agents split a unit prize. When n = 2 (6.1) any pair ( p, p) is an equilibrium, but when n = 2 (6.2) there is no symmetric equilibrium. In Sect. 7, we use Monte Carlo simulation to study social distancing on larger grid (7.1) and line (7.2) graphs. Section 8 concludes. As this is the first paper to introduce the social distancing problem, we confine ourselves to the consideration of some simple networks of small size: the line, cycle and lattice (grid) networks.

The m agents in our model move on a connected network Q with n nodes, n ≥ m, labeled 1 to n. While we could do this analysis on a general network with arbitrary arc lengths, we take a graph theoretic assumption where all arc lengths are 1, so we will from now on call Q a graph. In this section, we describe the dynamic model that we use throughout the paper. We do this in three stages: states, motion of agents, the resulting Markov chain. Since we will restrict the arc length to 1 here (although other lengths could be considered) we will henceforth use the term graph instead of network.

There are several ways to denote the state of the system. A general way is to write square brackets [ j 1 , j 2 , . . . , j n ] , where j i is the number of agents at node i, with m i=1 j i = m. We call the number j i the population of node i. We could also use a notation k j which indicates the node that agent j is occupying, but in this paper we have no need to know this. Attached to every state is a number d denoting the minimum distance between two agents, where we use the graph distance between nodes (the number or arcs in a shortest path). For example, if we number the nodes of the line graph L 6 consecutively, and the state is [1, 0, 0, 1, 0, 1] , then d = 2. If a state has distance d, it is called socially distanced if d ≥ D, where D is a parameter of the problem. For example, the state [1, 0, 0, 1, 0, 1] is socially distanced for D = 1 and D = 2 but not for D = 3. For the social distancing problem, the states with d ≥ D are considered the absorbing states, because we want to calculate the expected time to reach one of them, and the expected time to absorption is a standard problem for Markov chains. For other problems (gathering, search game), we have different absorbing states. The set of all states, the state space, is denoted S.

The unifying idea of this paper is the use of agent motions of the following type.

Definition 1 A lazy random walk (LRW) for an agent on the graph Q, with laziness parameter p (and speed q = 1 − p) is as follows. With probability p, stay at your current node. With probability q = 1 − p, go equiprobably to any of the δ adjacent nodes, where δ is the degree of your current node. If p = 0 this is called simply a random walk. If the graph has constant degree , then an LRW with p = 1/ ( + 1) then the process is called a loop-random walk. That is because it would be a random walk if loops were added to every node. That is, all adjacent nodes are chosen equiprobably, including the current node.

For various problems considered in the paper, random walks or loop-random walks will be optimal, in terms of minimizing the mean time to reach the desired state.

If all the agents in the model follow independent LRWs with the same value of p, i.e., our main assumption, then a Markov chain is thereby defined on the state space S. We only consider triples m (number of agents), D desired distancing and Q (the connected graph), where it is possible for having distanced states. For example, the triple m = 3, D = 2 and Q = C 5 (cycle graph with 5 nodes) has no distanced states. In general, we assume that the D−Independence number (maximum number of D distanced nodes) is at least m. If D = 1 this is called simply the independence number. If n = m and D = 1 we call this the spatial dispersion problem of Alpern an Reyniers [8] , an important special case of social distancing.

Given Q (with n nodes), m and D, there is a Markov chain on the state space S with a non-empty set of absorbing states A. Suppose we number the non-absorbing states as 1, 2, . . . , N , and let B denote the N × N matrix where b i, j is the transition probability from state i to state j. Let t be the vector (t i ) denote the expected time (number of transition steps) to reach an absorbing state from state i. The t i then satisfy the simultaneous equations t 1 = 1 + b 11 t 1 + · · · + b 1 j t j + · · · + b 1n t n . . .

We can write this in matrix terms, where J n the 1 by n matrix of 1s and I N is the N × N identity matrix, as

So the solution for the absorption time vector t is given by

In our model, the Markov chain has a parameter p, so these times t i ( p) will depend on p. This use of the fundamental matrix to calculate absorption times (3) is well known. For example, see Sect. 8 of Kemeny, Snell and Thompson [21] . We use this formula (3) often in this paper, starting in Sect. 3.1. In Sect. 4.2, we do the same calculation using an equivalent method with the original simultaneous equations. In some applications (e.g., two searchers for one hider), we wish to know the probability that a particular absorbing state is reached (which searcher finds the hider). Formulae for this problem are also known, but in the event we find a more direct way to determine this. This will be made clear in Sect. 4.4. In most cases, we consider the problem of finding the laziness value p =p which minimizes the absorption time. However in search game models considered in Sects. 4.3 and 4.4, the hider wishes to maximize the expected absorption time while the searcher wishes to minimize it. We will define the gathering and search game models when they are introduced, respectively, in Sects. 4.2 and 4.3. There are also cases where individual agents do not have the same goal, for example, in Sect. 6.

A useful variation is to allow agents to see the number k of agents at their node, the population of the node. This case may allow a laziness p k that depends on this k. For example, if I find myself at a node with three other agents, I stay there with probability p 4 , which is a number that is part of the overall strategy. But generally, and unless stated, we assume there is only one value of p regardless of the population of the node.

Generally, we will consider problems with at least m = 3 agents on a graph, but to illustrate the main concepts of the paper we begin with a simple example where two agents who start in adjacent nodes try to achieve distance D = 2 on a cycle graph C n with n ≥ 4 nodes. It turns out that the cases n ≥ 5 and n = 4 have different solutions. We take advantage of the symmetry of the cycle graph to use a reduced state space determined by the distance j between the agents. State j covers all configurations where this distance is j − 1, so that we have the usual row and column numbers for our matrices. The three states j = 1, 2, 3 are depicted in Fig. 1 for both C 5 (top) and C 4 bottom. For both cases of n, there are (up to symmetry) two non-absorbing states (1 and 2) and a single absorbing state 3.

To see the difference between n ≥ 5 and n = 4, consider the (expected) absorption time T from state 2 when adopting a random walk (a LRW with p = 0). In C n , n ≥ 5, when both agents move from state 2, if they go in the same direction (probability 1/2) or towards each other (probability 1/4), they stay in state 2. If they go in opposite directions (probability 1/4) they reach the absorbing state 3. So T satisfies the equation

However in the graph C 4 , if they start in state 2, they stay forever in state 2, so T = ∞. In the following two subsections on n ≥ 5 and n = 4, we consider population-dependent lazy random walks, using the notation p 1 = p (used when alone at a node -in state 2) and p 2 = r . We set q = 1 − p and s = 1 − r for the complementary probabilities. We solve this problem and then the simpler LRW problem by setting p 1 = p 2 ( p = r ). 

As illustrated in Sect. 2, we only need to calculate the transition probabilities between the non-absorbing states. Here, these are 1 and 2. This transition matrix is given by

and the fundamental matrix by,

The absorption times from states i = 1, 2 are

Since we are starting in state 2 we minimize t 2 (r , p) at

So when acting optimally, the agents always move when they are with another agent, and move about 63% of the time when they are alone. The absorption time of about 2.6 periods is considerably less than the 4 periods they take if they both follow a random walk.

If the agents must move according to a common LRW because they are unaware of the local population, we seek a minimum absorption time subject to r = p.

with minimum of t 2 (1/5, 1/5) = 25/8 3. 125 at p = 1/5. So even without being aware of the population of their location, they can still do a bit better than the random walk ( p = 0) absorption time of 4. Similar results can be obtained for starting together (state 1) or starting randomly.

On the graph C 4 , the transition matrix changes in the transition probability from state 2 to state 2 because if the agents move away from each other the state remains state 2. The transitions among the non-absorbing states are now

A similar analysis to that for n ≥ 5 now shows that starting from either state 1 or state 2, the optimal strategies are p 2 = r = 0 and p 1 = p = 1/2. Assuming this, we havē t 1 = 2 andt 2 = 3. This is counter-intuitive in that it is quicker to socially distance starting with both agents at the same node than starting with them at adjacent nodes. If we seek the optimal LRW, the solution depends on where we start. If we start at state 2 (two at a node), then it turns out that the random walk ( p = 0) is optimal, with (as shown above) an absorption time of 4. We already know that a random walk starting at state 2 will never achieve social distancing, as in this case state 2 will never be left. In this case, the optimal p is (1/10)

The absorption time for this LRW is approximately 4.46.

Although this example is very simple, with only two agents, it illustrates the use of population dependent strategies. That is, letting agents have awareness of their immediate environment. It also shows why random walks, which maximize the speed of the agents, do not necessarily lead to the quickest dispersal times.

Two important classes of graphs are the cycle graphs C n and the complete graphs K n , which coincide for n = 3 nodes. Due to the symmetry of the graph, we can use a special notation for states, rather than the more general one defined earlier in Sect. 2. The problem is small enough for us to obtain exact solutions, whereas the larger graphs will be studied later using simulation. For the first two results, on dispersion (social distancing) and gathering (multiple rendezvous) of three agents on C 3 , we define three states j = 1, 2, 3 as those where the agents lie on j distinct nodes. The third result, on the search game, will require a different notion of states.

We first consider how three agents placed on the nodes of C 3 can achieve social distancing with D = 1. This means that all pairwise distances must be at least 1, that is, the agents must occupy distinct nodes. This is also called the dispersion problem (one agent at each node). It turns out, surprisingly, that the initial placement of the agents does not affect the optimal strategy, which is the loop-random walk.

If three agents are placed in any way on the nodes of C 3 , then the expected time to the social distanced state j = 3 (one on each node) is uniquely minimized when the agents adopt the loop-random walk ( p = 1/3).

Proof If all agents adopt the same laziness p (speed q = 1 − p), the transition matrix for the non-absorbing states 1 (all at same node) and 2 (two at one node, one at another) is given by

Using the fundamental matrix F = (I − B) −1 , with I the identity matrix of size 2, we obtain the expected times t j from state j to the absorbing state 3 as

To minimize t 1 , we calculate

to observe that t 1 is decreasing for p < 1/3 and increasing for p > 1/3 and hence has a unique minimum at p = 1/3. Similarly, the time to the absorbing state from state 2 is given by

By calculating

and observing that the bracketed expression is positive on (0, 1) , we see as above that t 2 has a unique minimum at p = 1/3. Since 3 = 1 + δ, where δ = 2 is the degree of (every node of) C 3 , we see that this is the loop-random walk.

The rendezvous problem [2] asks how two mobile agents who do not know the location of the other can meet in least expected time, called the Rendezvous Value of the problem. We now a multiple agent version of that problem. Consider the gathering, or multiple sticky rendezvous problem, where agents who meet merge into a single agent and the aim is to have all agents at the same node. We consider the symmetric version of the problem, where all agents must adopt the same strategy. In the present context, this means they all adopt the same laziness p in their LRW. This has previously been considered (see Sect. 5 of Alpern [2] ) only for simple two-agent rendezvous. Here, the absorbing state is state 1, where the agents together occupy 1 node. The sticky version for multiple agents was studied for agents on a line graph, in Baston [10] . Again, our result is surprising in that the initial placement of the agents on C 3 does not affect the solution.

If three agents are placed in any way on C 3 then the unique solution to the gathering problem is the loop-random walk, p = 1/3 in this case. The rendezvous value for the problem starting from state 2 is 3 and from state 3 is 27/7.

Proof If, as required, all agents adopt the same laziness p (speed q = 1 − p), the transition matrix for the non-absorbing states 2 (two at one node, one at another) and 3 (all at different nodes) is given by

So by the general formulae (2) and (5), the fundamental matrix is given by In this and larger gathering problems, every state has some number k of occupied nodes, those any such nodes being considered glued together and a single new agent. Note that the set of states S K with k ≤ K for some K is an invariant, or absorbing set. This means that we can find expressions for those t i ( p) for i in S 2 first, then use this to find t i ( p) for i in S 3 , and so on. This is just a matter of a particular way of solving the simultaneous equations in (1) in a recursive way. For example in the two state problem of this section, we first solve for t 2 in t 2 = b 2,2 (1 + t 2 ) and then for t 3 t 3 ) , where the rows are considered row 2 and row 3. We consider this as recursively solving for the variables in the simultaneous equations rather than as dynamic programming because we cannot optimize However, there is a variation of the gathering problem on C 3 which could be solved with dynamic programming, as suggested by an anonymous referee. In the current model, when two agents meet, the remaining agent is unaware of this and hence must continue with an unchanged strategy p, so he would not be aware he was in a solved case. Suppose we consider a different model in which a central controller sends out a signal to all agents telling how many new agents k there now are, considering gluing of those who have met. For C 3 , the distribution of agents on C 3 (the state) is determined by k. Suppose we let the agents choose a common value of p that depends on k, call it k p. In that case, we could first minimize T 2 for some 2p and then solve the k = 3 problem by using 2p when two agents meet. However, even with this intervention approach we could not solve the general gathering problem of m agents randomly placed on C n because after two meet the m − 1 new agents would not be randomly placed. (We also note that for the particular case of three agents on C 3 the new problem with added information does not lead to a different answer, as all the optimal values of p are the same, 1/3. But it would be a different method.)

We now consider a search game played by two mobile searchers and a mobile hider on C 3 . These games were introduced by Isaacs [20] and studied initially by Zelikin [28] , Alpern [1] and Gal [14] . For a comprehensive treatment, see Gal [15] and Alpern and Gal [7] . We place the three agents on C 3 randomly. The searchers choose a common laziness s and the hider chooses a laziness h. In this instance, we take the point that the searchers are a team, mother and father to a hungry infant. They have the common aim of minimizing the time T taken to find the hider, who wants to maximize T . Here, T is the first time that one of the searchers finds the hider, it does not matter which searcher it is. (We could introduce competition between the searchers, but we shall not do so here.) It is not clear a priori that there will be a saddle point. However in the event, we show that there is one, with h about .51 and s about .28. Thus, the searcher moves more frequently than the hider. Ruckle [24] has considered this problem on C n (cycle graph with n nodes) when there is a single searcher and a single hider.

There are four states (up to symmetry, as usual): states 1 and 2 are non-absorbing (hider is not caught), states 3 and 4 are absorbing (the hider has been caught). See Fig. 2 . A random initial placement results in these states occurring with respective probabilities 2/9, 2/9, 4/9 and 1/9.

To calculate the expected value of the capture time t j (number of periods to absorption) from state j = 1, 2, it is only necessary to know the transition probabilities between these two states, which are given by the following 2×2 matrix B (where h = 1−h and s = 1−s). 

As in previous analyses, we then get the absorption times as

, and expected meeting time We can see that a solution exists by plotting the two curves in Fig. 3 . Note that the curve T h = 0 appears to be close to a straight line. It is also useful to plot the optimal response curve h = R (s) of the hider for the function T . We then can obtain s * exactly as the solution to the fifth degree polynomial equation T (s, 0) = T (s, 1) which simplifies to 14 − 15s − 117s 2 − 33s 3 − 5s 4 + 60s 5 = 0 and has a unique solution for s ∈ [0, 1].

Numerical approximation of the critical point (h * , s * ) gives h * 0.5097 and s * 0.2797, with game value V = T (h * , s * ) 0.8390. To show that it is a saddle point we approximate the determinant of the Hessian at about −2.4, so it is certainly negative. But this fact is clearer from the Fig. 5 , which shows plots where the horizontal axis can be h or s. The top (blue) curve shows that the payoff T is at least V for any value of s = x when the hider adopts h * and is above V if s = x is not the optimal value s * . The bottom (brown) curve shows that the searcher finds the hider in time no more than V when adopting s * . In this case, the capture time is not very sensitive to the value of h.

This analysis considers the two searchers as a team which wishes to minimize the capture time T . Perhaps a male and female who will bring the captured prey back to their offspring, and it does not matter which one makes the kill. A different approach (Payoff function) could model a competition between the two searchers, as carried out in the next section. 

We now model the problem of two searchers and one hider as a three person game, rather than considering the two searchers as a single player (team). As in the previous subsection, the game ends at the first time T when one or both searchers coincide with the hider. The hider's payoff is simply T . A searcher gets payoff 1 if he is the unique player to find the hider; 1/2 if both searchers find the hider at the same time and 0 if the other searcher finds the hider alone. This element of competition between the searchers has been studied in Nakai [23] and Duvocelle [12] , but here the hider is also adversarial. Figure 6 shows the five states. States 1 and 2 are non-absorbing; states 3, 4 and 5 are absorbing. Searcher 2 wins in state 3, searcher 1 wins in state 4, and state 5 is a tie. The hider's payoff depends on the time T to reach an absorbing state.

We seek a Nash equilibrium that is symmetric with respect to the two searchers. Denote the laziness of searcher 1 by r , searcher 2 by s and of the hider by h. Let E = E (s 1 , s 2 , h) now denote the expected absorption time starting from a random state, respectively. Let a j , j = 3, 4, 5, denote the probability the game ends in State j, assuming it starts randomly. Player 2's payoff is equal to a 3 + (1/2) a 5 , with a similar payoff for player 1. We seek parameters r and h such that r , r , h for any hider parameter h , and  • a 3 (r , r , h) + (1/2) a 5 (r , r , h) ≥ a 3 (r , s, h) + (1/2) a 5 (r , s, h) , for any s.

The probabilities that an absorbing Markov chain ends at each absorbing state are easily calculated but we use a qualitative idea to avoid this calculation on a five-state chain. Instead we show that there is a dominating search strategy (depending on h but not the other search strategy) that ensures always capturing in the next period with maximum probability. Such a strategy clearly maximizes the searcher's payoff, regardless of what the other searcher is doing.

To calculate the optimal response of the hider to a symmetric pair (s, s) of strategies of the searchers, we refer to Fig. 4 .

Suppose the hider adopts strategy h. If a searcher can always maximize the probability of finding the hider in the current period, he guarantees doing at least as well as the other (1, 1) , (1, 2) , (0, 1), (0, 2) , (0, 0) left to right searcher. What is the best value of s to maximize this probability? If h = 1 (hider stays still), then probability of capture is (1 − s) /2. If h = 0 (moves) the probability is s/2 + (1 − s) /4. So against a general h, the capture probability in the next period is

(6) The maximizing s will be 1 if 1 4 − 3 4 h is positive, i.e., h < 1/3. The maximizing s will be 0 if h > 1/3. If h = 1/3 (loop-random walk) then all s give the same capture probability. Note that s * = 1/3 gives the searcher a loop-random walk, as C 3 has degree 2 for all nodes. We already showed in the previous subsection that if s = s * then all h give the same expected capture time from a random start. So h = 1/3 and s = s * .278 give the searcher-symmetric equilibrium (s, s, h) = (s * , s * , 1/3).

To see that this equilibrium is unique, suppose s < s * . Then as h is an optimal response to (s, s, _) , we have that h = 0. In this case, we have in particular that h < 1/3 so we showed above that the play of each searcher to maximize the probability he finds the hider first is s = 1. This contradicts our assumption that s < s * . Similarly if s > s * , then the best response is h = 1 > 1/3, so the maximizing s if 0, contradicting our assumption.

The unique searcher-symmetric Nash equilibrium to the competitive search game on C 3 is given by the loop-random walk (h = 1/3) for the hider and a laziness s * for both searchers, where s * 0.2791 is the unique solution to the fifth degree polynomial equation 14 − 15s − 117s 2 − 33s 3 − 5s 4 + 60s 5 = 0 between 0 and 1.

To see why the team solution given in the previous subsection is not an equilibrium with respect to the searchers, note that against h = h * .5097, a searcher playing s = 0 (random walk) has a higher capture probability in each period than one playing s * 0.2791, as W (0, .5097) 0.377 4 compared to W (s * , .5097) 0.340 5, see (6) . Note that the searchers behave the same at equilibrium whether or not they are working as a team, but the hider moves more frequently when the hiders act as a team rather than competitively.

Suppose three agents are located on the cycle network C n . For this section, we take n = 5, but the following representation of states works for all n. We may use the symmetry of the network to reduce that state to three numbers (actually 2, once we know n). Let j denote the distance between the two closest agents and let k denote the distance between the second closest pair. Thus, the arcs between the three agents have distances j, k and n − j − k. For n = 5, we have five states, as shown in Fig. 7 . In general, for three agents on C n , we have a triangular set of states D 3 = {( j, k) : 0 ≤ j ≤ k ≤ (n − j) /2} . For the case n = 5 considered here, the five states (in x = j, y = k space) lie between the lines j = k and k ≤ (5 − j) /2, as shown as black disks in Fig. 8 .

For larger values of n, the states for three agents will be more numerous and from state ( j, k) can transition to ( j + x, k + y) for x, y ∈ {−2, −1, 0, 1, 2} with some exceptions. For example, the nine states in the two extreme corners cannot be reached (these circles are not filled in). See Fig. 9 . The state ( j − 2, k − 2) cannot be reached because if the two closest agents move towards each other two cannot also move closer.

This figure indicates the complexity of analyzing even three agents for larger cycle graphs and explains why will use simulation techniques to obtain approximate solutions for larger cycle graphs.

The gathering problem is defined in the same way on C 5 as earlier on C 3 . The state (0, 0) in Fig. 7 and 8 is the only absorbing state and we number the other four from left to right. For The non-absorbing states (rows) for our transition matrix are thus e (1), d (2), c (3) and b (4) , and the 4 by 4 transition probability matrix for these states, with all agents adopting p (with q = 1 − p) is given by the 4 by 4 matrix B,

We then, as usual, calculate the fundamental matrix F = (I 4 − B) −1 and evaluate the times t i from state i to absorption (gathering) as

The expected time to absorption for the different initial states are shown in Fig. 11 as functions of p for i = 1 blue, 2 yellow, 3 green, 4 red. The random start gives probabilities (6, 6, 6, 6, 1) /25 (the final probability 1/25 is for gathering right away, state 5).

For the social distancing problem on C 5 with m = 3 agents and d = 1 (higher values of d are not attainable on C n , n < 6), we have the same five states as in Fig. 7 . However now the two states ( j, k) with j = 1 are absorbing (distanced) because j is by definition the minimum pairwise distance between agents. We renumber the remaining states as S i = (0, i) , so that S 1 = (0, 0) , S 2 = (0, 1) and S 3 = (0, 2) . As usual we only need to calculate the transition probabilities between non-absorbing states, which are given (with q = 1 − p) by the 3 by 3 matrix

The times t i for absorption from S i , shown in Fig. 12 , are given by It is intuitive that social distancing takes the longest when the agents are in the gathered position. When two are at the same location it takes longer to disperse when the third is closest to them. The random starting process takes a shorter time because there is already a high probability (13/25) that they are dispersed, in which case the dispersal time is 0.

In this section, we consider the game G 1 (n), where n players start together at the end location 1 on the line graph L n with nodes 1, 2, . . . , n. When some players first achieves "ownership" of a node (are alone at their node), these players equally split a prize of 1. Each player i has a single strategic variable, her laziness probability p i . We seek symmetric equilibria (with all p i the same) for the cases n = 2, 3.

We can consider this game as a selfish form of the social distancing problem with D = 1 and m = n (so it is also a dispersion problem) on the line graph L n . In a version of this problem with what we call territoriality, a player who is alone at her node becomes the owner of it. This means she stays there forever and anyone else who lands there immediately moves away randomly in the next period. So the game considered here can be thought of as the beginning of a dispersal problem with territoriality.

This is an almost trivial case. For any p ∈ (0, 1), the game eventually ends with probability one (as soon as one player moves and one stays, in the same period), with a payoff of 1/2, since both players will achieve ownership at the same time. So any pair ( p, p) is a symmetric equilibrium.

By symmetry, it is clear that when all players adopt stay probability p, they all have expected payoff of 1/3. We will show that when any two players adopt the same p, the remaining player can get more than 1/3 by a suitable strategy, and hence there is no symmetric equilibrium. The algebra involved in the proof is greatly simplified if we consider the "modified payoff" M(q, p) to the single player (call her player 1) adopting q when the other two adopt p. It is modified from the actual payoff by not giving her the prize of 1/3 when there is a tie. So it will be enough to show that player 1 can always find a q (for any p adopted by the others) with M (q, p) ≥ 1/3 when a tie is possible and consequently her actual payoff will strictly exceed 1/3. So no triple ( p, p, p) can constitute an equilibrium.

Lemma 5 Suppose two players use a common strategy p < 1/2. Then by always staying at his original node (laziness q = 1), the remaining player (1) can get a payoff above 1/3.

Proof It suffices to show that his payoff for general p is given by the expression (1 − p) 2 / 1 − p 2 , which is greater than 1/3 for p < 1/2. To show this, observe that remaining player wins (payoff 1) unless exactly one of the remaining players moves before both of them move. Let O be the event exactly one moves and B be the event both move, N be the event none moves. The winning sequences for are B, N B, N N B, .. . Since B has probability (1 − p) 2 and N has probability p 2 , these events have total probability

Since this has derivative −2/ ( p + 1) 2 it is decreasing and its value at p = 1/2 is 1/3.

Suppose two players use a common strategy p > 1/2. Then, when foregoing his payoff of 1/3 in a tie, the remaining player can still obtain a payoff exceeding 1/3 by always moving (random walk), q = 0. When p = 1/2, the payoff is exactly 1/3. A ( p) and B ( p) denote the payoff to the "remaining player" who chooses q = 0 (always moves) when the others use p, starting, respectively, with all agents at location 1 (or 3) and all agents at the middle location 2, assuming this player does not accept the payment of 1/3 in case of a tie. This last assumption simplifies the algebra. From position A (all at 1), the remaining player must go to location 2, so there are three possible subsequent states: all go to middle location 2 (payoff B), the other players stay at location 1 (payoff 1) or if he alone stays at location 1. Other outcomes lead to payoff 0 and can be ignored. This gives the formula A = A (q, p) in terms of B = B (q, p).

Similarly, if the players all start at the middle location 2, the remaining player moves to an end (call this end 1). Now there are three subsequent states: both others stay in the middle (payoff 1), both of the others go to the same end as the remaining player (payoff A), both of the other players go to the other end (payoff 1). The other states are either have payoff 0 or have payoff 1/3, which we are reducing to 0 in this calculation. So we have B = B ( p) given by

We are only interested in the solution A, starting from an end, which is

We calculate

The denominator is positive for all p ≥ 1/2 and the numerator is positive for p > 1/2 and equal to 0 for p = 1/2.

There is no symmetric Nash equilibrium for the game G 1 (3).

Proof Lemma 5 shows that p < 1/2 cannot form a symmetric equilibrium and Lemma 6 shows that p > 1/2 cannot form a symmetric equilibrium. Consider that Players 2 and 3 adopt p = 1/2 and player 1 adopts q = 0. According to Lemma 6 , player 1 gets a modified payoff of 1/3 (without getting a prize when there is a tie). However a tie has positive probability. It occurs when 2 and 3 move in the first period and then one stays in the middle and the other moves to the end node not occupied by 1. So the payoff (unmodified) to player 1 in this case exceeds 1/3, her payoff when all three adopt p = 1/2.

Of course in this analysis, the laziness strategies should be thought of as pure strategies. If the players use mixed strategies which are distributions of p's, there might be a symmetric equilibrium.

For larger problems with respect to m and n, we determine expected time to reach social distancing with D = 2 by simple Monte Carlo simulation methods. We place the m agents in some specified initial locations on the network. Then we have them move independently according to LRW's with the same p value. After each step, we find the minimum pairwise distance d between agents in the current state. If d ≥ D (= 2 for the examples here), we stop and record the time T . We carry out 5, 000 trials and record the mean. Contrary to our earlier results, we find for the line and the two-dimensional grid that it is optimal for the agents to follow (independent) random walks, p = 0. When n is very small, it takes a little longer to reach social distancing.

In practice, social distancing is often to be achieved by individuals in a planar region. A good network model for this is the two-dimensional grid graph G R k with n = k 2 nodes in the set {(i, j} : 1 ≤ i, j ≤ k}, as shown in Fig. 13.  Fig. 13 Two-dimensional grids G R k , k = 3, ..., 6

Fig. 14 Time to d = D ≡ 2 on G R k , k = 3 to 6, from corner start A natural starting state is the one with all agents at a corner node (say (1, 1)) or at the center (both coordinates k/2 . Figure 14 illustrates these times for values of p spaced at distance 0.2. Note that for all the four values of k, the mean times to reach distance d = 2 are increasing in p. The means that the random walk, p = 0, is the best. In terms of grid size k, It takes a bit longer for the 3 × 3 grid because reflections from the boundary are more common. For larger values of k, the times do not appear to depend much on k.

If the starting state consists of all agents at the center of the grid then we have similar result, as seen in Fig. 15 .

The graph L n has n nodes arranged in a line and numbered from the left as 1 to n. Like the grid graph, a natural starting state is either all at an end (say node 1) or all at the center. We find that the common value of p should be 0, that is, the agents should adopt independent random walks. Figure 16 shows this for a left start and Fig. 17 shows this for a center start, at n/2 . 

This article introduced the social distancing problem on a connected graph, where agents have a common goal to have all their pairwise distances be at least a given number D. While different motions and information could be given to the agents for this problem, we give them only local knowledge of the graph and no knowledge of locations of other agents. So they know only the degree of their current node and lack memory. These assumptions limit the motions of the agents to lazy random walks. We showed how to optimize their common laziness value p to achieve social distancing in the least expected number of steps. We considered various graphs and both exact and simulated methods. In some cases, the optimal motion was a random walk ( p = 0) or a loop-random walk (choosing their current node with the same probability as each adjacent one). We also considered variations where agents know the current population k of their node and can choose laziness p k accordingly. While mostly we consider the common-interest team version of the problem, we also studied cases where agents had individual selfish motives-we showed that in some cases no symmetric equilibrium exists.

We expect this area of research to be enlarged to other assumptions:

• Agents know locations of some or all of the other agents.

• Agents have some memory.

• Agents know the whole graph.

• Agents can gain "territoriality over a node."

It turns out that our model of mobile agents on a graph is also useful for some other problems (goals). One goal is multi rendezvous, or gathering, where the common goal is for all agents to occupy a common node. This extended earlier result limited to two agents. Another problem is the search game where agents come in two types, searchers and hiders, with obvious associated goals. Here, our methods extend known results to multiple searchers. Many other results in search games could usefully be extended in a similar way.

In this first paper on social distancing, we have restricted ourselves to considering only some simple classes of graph and small sizes. It is to be hoped that further research in this area will find new and stronger methods able to study general graphs.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

The search game with mobile hider on the circle. Differential games and control theory

The Rendezvous Search Problem

Rendezvous search: a personal perspective

Rendezvous search on labeled networks

A new approach to Gal's theory of search games on weakly Eulerian networks

Rendezvous search on a graph

The Theory of Search Games and Rendezvous

Spatial dispersion as a dynamic coordination problem

The rendezvous problem on discrete locations

Two rendezvous search problems on the line

Decentralized learning from failure

A competitive search game with a moving target

Shimer R (2021) Internal and external effects of social distancing in a pandemic

Search games with mobile and immobile hiders

Search Games

Rendezvous search on the line

Does Social Distancing Matter?

Dispersion Games: General Definitions and Some Specific Learning Results

Rendezvous search on the interval and circle

Differential Games

Introduction to Finite Mathematics

Rendezvous search on the line with more than two players

A search game with one object and two searchers

Geometric Games and Their Applications

A Network Dispersion Problem for Non-communicating Agents

Social distancing in covid-19: what are the mental health implications?

Optimal symmetric rendezvous search on three locations

On a differential game with incomplete information

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations