Abstract: |
Alpern and Reyniers (2002) initiated the study of spatial dispersion of agents in the context of non-communicating agents who could move between any two locations, based only on the knowledge of the populations at all locations. The research problem addressed in this paper is to see how the problem of Alpern and Reyniers changes if a network (graph) structure is imposed on the set of locations: An agent only knows the population at his current node (location) and he can only stay still or move to an adjacent node. He can see the number of arcs at his node, but if he moves he must choose among them equiprobably. As we are dealing with non-communicating agents with limited amount of global knowledge, we shall limit our discussion to simple and myopic strategies. In particular, our agents adopt common (Markovian) stunted random walk strategy, completely specified by the probability p of staying still for another period at the same node. Given such strategies, how long will it take, on average, for the agents to achieve dispersion? Our objective is to determine the minimum dispersal time and optimal levels of p for several classes of networks, including line networks, cycle networks, and complete graphs. |