. .. , let g i be the function from sequences to sequences that swaps the cacti visited in rounds ? (?, i) and T + 1 ? i

. ?-(?,i)-=-?-t-+1?i, ;. .. All-j-?-[t-]-\-{?, and . T-}, T + 1 ? i}, (g i (?)) T . Then, U 2 (g(?)) ? U 2 (?), and for all t ? {?T + 1

. Proof, We proceed by induction, showing that every step g i can only increase the value of U 2

, By definition of A(?), every cactus is visited at most twice in ?, once before ?T and once after ?T + 1. There are three cases to distinguish: Case 0: ? 1 = ? T , i.e, ? (?, T ) = 1. In this case we have g T (?) = ?. Case 1: ? 1 is not revisited, The first step is applying function g T , which swaps the first cactus visited and the cactus visited in round ? (?, T )

, T ? 1} such that ? t * = ? 1 and ? (?, t * ) = 1. In this case, ? ? (g T (?), T ) = ? (?, t * ) = 1, ? ? (g T (?), t * ) = ? (?, T ) > 1, ? ? (g T (?), t) = ? (?, t) for all t ? {?T + 1, . . . , T ? 1} \ {t * }, and therefore, U 2 (g T (?)) ? U 2 (?) = r ? T

, = (r ? T ? r ? t * )(? (?, T ) ? 1)

I. Abraham, D. Dolev, and J. Y. Halpern, Distributed protocols for leader election: A game-theoretic perspective, 27th International Symposium on Distributed Computing (DISC), pp.61-75, 2013.

D. Acemoglu, A. Munther, I. Dahleh, A. Lobel, and . Ozdaglar, Bayesian learning in social networks, The Review of Economic Studies, vol.78, issue.4, pp.1201-1236, 2011.

Y. Afek, Y. Ginzberg, S. L. Feibish, and M. Sulamy, Distributed computing building blocks for rational agents, Symposium on Principles of Distributed Computing (PODC), pp.406-415, 2014.

Y. Afek, S. Rafaeli, and M. Sulamy, Cheating by duplication: Equilibrium requires global knowledge, 2017.

S. Albers and M. Hellwig, Online makespan minimization with parallel schedules. CoRR, abs/1304, vol.5625, 2013.

, A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem, J. Algorithms, vol.7, issue.4, pp.567-583, 1986.

C. Avin, A. Cohen, P. Fraigniaud, Z. Lotker, and D. Peleg, Preferential attachment as a unique equilibrium, The Web Conference (WWW), 2018.

L. Barenboim and M. Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments, Synthesis Lectures on Distributed Computing Theory

S. Bhattacharya, S. Im, J. Kulkarni, and K. Munagala, Coordination mechanisms from (almost) all scheduling policies, Innovations in Theoretical Computer Science, ITCS'14, pp.121-134, 2014.

D. Braess, Über ein paradoxon aus der verkehrsplanung, Unternehmensforschung, vol.12, issue.1, pp.258-268, 1968.

D. Braess, A. Nagurney, and T. Wakolbinger, On a paradox of traffic planning, Transportation science, vol.39, issue.4, pp.446-450, 2005.

C. Broom, M. , and G. Vickers, Multi-player matrix games, Bulletin of Mathematical Biology, vol.59, issue.3, pp.931-952, 1997.

M. Broom and J. Rychtár, Game-theoretical models in biology, 2013.

M. Bukowski and J. Miekisz, Evolutionary and asymptotic stability in symmetric multi-player games, International Journal of Game Theory, vol.33, issue.1, pp.41-54, 2004.

A. Calvó-armengol, J. De-martí, and . Beltran, Information gathering in organizations: Equilibrium, welfare and optimal network structure, Journal of the European Economic Association, vol.7, pp.116-161, 2009.

A. Calvó-armengol, J. De-martí-beltran, and P. A. , Communication and influence. Theoretical Economics, vol.10, pp.649-690, 2015.

K. Subir and . Chakrabarti, Equilibrium in Behavior Strategies in Infinite Extensive Form Games with Imperfect Information, Economic Theory, vol.2, issue.4, pp.481-494, 1992.

X. Chen and X. Deng, Settling the complexity of two-player nash equilibrium, Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pp.261-272, 2006.

C. Cosner, J. Dávila, and S. Martínez, Evolutionary stability of ideal free nonlocal dispersal, Journal of Biological Dynamics, vol.6, issue.2, pp.395-405, 2012.

R. Cressman and V. K?ivan, Migration dynamics for the ideal free distribution, The American Naturalist, vol.168, issue.3, pp.384-397, 2006.

R. Cressman and V. K?ivan, The ideal free distribution as an evolutionarily stable state in density-dependent population games, Oikos, vol.119, issue.8, pp.1231-1242, 2010.

A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria, ACM Trans. Algorithms, vol.3, issue.1, 2007.

C. Daskalakis, W. Paul, C. H. Goldberg, and . Papadimitriou, The complexity of computing a nash equilibrium, SIAM Journal on Computing, vol.39, issue.1, pp.195-259, 2009.

K. N. Dina, . Dechmann, L. Silke, L. Heucke, K. Giuggioli et al., Experimental evidence for group hunting via eavesdropping in echolocating bats, Proceedings of the Royal Society of London B: Biological Sciences, vol.276, pp.2721-2728, 1668.

A. Eldar, Social conflict drives the evolutionary divergence of quorum sensing, Proceedings of the National Academy of Sciences, vol.108, issue.33, pp.13635-13640, 2011.

Y. Emek, T. Langner, D. Stolz, J. Uitto, and R. Wattenhofer, How many ants does it take to find the food? Theor, Comput. Sci, vol.608, pp.255-267, 2015.

Y. Emek, T. Langner, J. Uitto, and R. Wattenhofer, Solving the ANTS problem with asynchronous finite state machines. In Automata, Languages, and Programming -41st International Colloquium, Proceedings, Part II, pp.471-482, 2014.

K. Fan, Fixed-Point and Minimax Theorems in Locally Convex Topological Linear Spaces, vol.38, pp.121-126, 1952.

O. Feinerman and A. Korman, The ANTS problem. Distributed Computing, vol.30, pp.149-168, 2017.

O. Feinerman and A. Korman, Individual versus collective cognition in social insects, Journal of Experimental Biology, vol.220, issue.1, pp.73-82, 2017.

E. Fonio, Y. Heyman, L. Boczkowski, A. Gelblum, A. Kosowski et al., A locally-blazed ant trail achieves efficient collective navigation despite limited information. eLife, vol.5, p.20185, 2016.

P. Fraigniaud, A. Korman, and Y. Rodeh, Parallel exhaustive search without coordination, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp.312-323, 2016.

P. Frazier, D. Kempe, J. Kleinberg, and R. Kleinberg, Incentivizing exploration, Proceedings of the fifteenth ACM conference on Economics and computation, pp.5-22, 2014.

D. Stephen, H. L. Fretwell, and . Lucas, On territorial behavior and other factors influencing habitat distribution in birds, Acta biotheoretica, vol.19, issue.1, pp.16-32, 1969.

D. Stephen, H. Fretwell, and . Lucas, On territorial behavior and other factors influencing habitat distribution in birds, Acta biotheoretica, vol.19, issue.1, pp.16-36, 1969.

D. Fudenberg and D. Levine, Subgame-Perfect Equilibria of Finite-and Infinite-Horizon Games, Journal of Economic Theory, vol.31, issue.2, pp.251-268, 1983.

A. Galeotti, C. Ghiglino, and F. Squintani, Strategic information transmission networks, J. Economic Theory, vol.148, issue.5, pp.1751-1769, 2013.

A. Luc, T. Giraldeau, and . Caraco, Social foraging theory, 2018.

L. Irving and . Glicksberg, A Further Generalization of the Kakutani Fixed Point Theorem with Application to Nash Equilibrium Points, Proceedings of the AMS, vol.3, issue.1, pp.170-174, 1952.

S. Chaitanya, A. Gokhale, and . Traulsen, Evolutionary games in the multiverse, Proceedings of the National Academy of Sciences, vol.107, issue.12, pp.5500-5504, 2010.

T. Gregor, K. Fujimoto, N. Masaki, and S. Sawai, The onset of collective behavior in social amoebae, Science, vol.328, issue.5981, pp.1021-1025, 2010.

J. Hagenbach and F. Koessler, Strategic communication networks, Review of Economic Studies, vol.77, issue.3, pp.1072-1099, 2011.

W. D. Hamilton, Narrow roads of geneland, 1996.

C. Harris, Existence and Characterization of Perfect Equilibrium in Games of Perfect Information, Econometrica: Journal of the Econometric Society, vol.53, issue.3, pp.613-628, 1985.

T. Thomas, . Hills, M. Peter, D. Todd, D. Lazer et al., Exploration versus exploitation in space, mind, and society, Trends in cognitive sciences, vol.19, issue.1, pp.46-54, 2015.

M. O. Jackson, B. W. Rogers, and Y. Zenou, Networks: An economic perspective, 2016.

O. Matthew, Y. Jackson, and . Zenou, Games on networks, Handbook of game theory with economic applications, vol.4, pp.95-163, 2015.

M. Kennedy, D. Russell, and . Gray, Can ecological theory predict the distribution of foraging animals? a critical analysis of experiments on the ideal free distribution, Oikos, pp.158-166, 1993.

M. Kennedy and R. D. Gray, Can ecological theory predict the distribution of foraging animals? a critical analysis of experiments on the ideal free distribution, Oikos, vol.68, issue.1, pp.158-166, 1993.

J. Kleinberg and S. Oren, Mechanisms for (mis) allocating scientific credit, Proceedings of the forty-third annual ACM symposium on Theory of computing, pp.529-538, 2011.

A. Korman and Y. Rodeh, Parallel search without coordination, Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity, 2017.

E. Koutsoupias and C. Papadimitriou, Worst-case equilibria, Annual Symposium on Theoretical Aspects of Computer Science, pp.404-413, 1999.

I. Kremer, Y. Mansour, and M. Perry, Implementing the "wisdom of the crowd, Journal of Political Economy, vol.122, issue.5, pp.988-1012, 2014.

M. David, R. Kreps, and . Wilson, Sequential Equilibria, Econometrica: Journal of the Econometric Society, pp.863-894, 1982.

F. Kuhn, T. Moscibroda, and R. Wattenhofer, Radio network clustering from scratch, 12th European Symposium on Algorithms (ESA), vol.3221, pp.460-471, 2004.

H. W. Kuhn, Extensive Games and the Problem of Information, Contributions to the Theory of Games, volume II, vol.28, pp.193-216, 1953.

E. Carlton, . Lemke, and J. Joseph-t-howson, Equilibrium points of bimatrix games, Journal of the Society for Industrial and Applied Mathematics, vol.12, issue.2, pp.413-423, 1964.

N. Linial, Locality in distributed graph algorithms, SIAM J. Comput, vol.21, issue.1, pp.193-201, 1992.

M. Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem, SIAM J. Comput, vol.15, issue.4, pp.1036-1053, 1986.

Y. Mansour, A. Slivkins, and V. Syrgkanis, Bayesian incentivecompatible bandit exploration, Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp.565-582, 2015.

M. John, A. I. Mcnamara, and . Houston, Integrating function and mechanism, Trends in Ecology & Evolution, vol.24, issue.12, pp.670-675, 2009.

L. Mealey, The sociobiology of sociopathy: An integrated evolutionary model, Behavioral and Brain Sciences, vol.18, issue.3, pp.523-541, 1995.

M. Rodrigo-a-medellin, A. Rivero, . Ibarra, T. P. Antonio-de-la-torre, L. Gonzalez-terrazas et al., Follow me: foraging distances of leptonycteris yerbabuenae (chiroptera: Phyllostomidae) in sonora determined by fluorescent powder, Journal of Mammalogy, vol.99, issue.2, pp.306-311, 2018.

D. Monderer, S. Lloyd, and . Shapley, Potential games, Games and economic behavior, vol.14, issue.1, pp.124-143, 1996.

W. Douglas and . Morris, Shadows of predation: habitat-selecting consumers eclipse competition between coexisting prey, Evolutionary Ecology, vol.17, issue.4, pp.393-422, 2003.

T. Moscibroda and R. Wattenhofer, Maximal independent sets in radio networks, 24th Symposium on Principles of Distributed Computing (PODC), pp.148-157, 2005.

M. Naor and L. J. Stockmeyer, What can be computed locally?, SIAM J. Comput, vol.24, issue.6, pp.1259-1277, 1995.

J. Nash, Non-cooperative games. ph. d. dissertation in mathematics, princeton university, 1950.

J. F. Nash, Non-Cooperative Games, The Annals of Mathematics, vol.54, issue.2, pp.286-295, 1951.

F. John and . Nash, Equilibrium Points in n-Person Games, Proceedings of the national academy of sciences, vol.36, pp.48-49, 1950.

. Aj-nicholson, An outline of the dynamics of animal populations, Australian Journal of Zoology, pp.9-65, 1954.

N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic game theory, 2007.

J. Martin, A. Osborne, and . Rubinstein, A course in game theory, 1994.

H. Christos and . Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and system Sciences, vol.48, issue.3, pp.498-532, 1994.

Y. Papanastasiou, K. Bimpikis, and N. Savva, Crowdsourcing exploration, Management Science, 2017.

A. Geoffrey and . Parker, Searching for mates. Behavioural ecology: an evolutionary approach, vol.1, pp.214-244, 1978.

A. Geoffrey and . Parker, Evolutionary stable strategies. Behavioural ecology: an evolutionary approach, pp.30-61, 1984.

D. Peleg, Distributed Computing: A Locality-Sensitive Approach. Discrete Mathematics and Applications, 2000.

N. Pinter-wollman, T. Dayan, D. Eilam, and N. Kronfeld-schor, Can aggression be the force driving temporal separation between competing common and golden spiny mice, Journal of Mammalogy, vol.87, issue.1, pp.48-53, 2006.

R. Pulliam and T. Caraco, Living in groups: is there an optimal group size. Behavioural ecology: an evolutionary approach, vol.2, pp.122-147, 1984.

R. Pulliam, J. Brent, and . Danielson, Sources, sinks, and habitat selection: a landscape perspective on population dynamics, The American Naturalist, vol.137, pp.50-66, 1991.

N. Quijano and K. M. Passino, The ideal free distribution: Theory and engineering application, IEEE Transactions on Systems, Man, and Cybernetics, vol.37, issue.1, pp.154-165, 2007.

R. Radner, Collusive Behavior in non-Cooperative epsilon-Equilibria of Oligopolies with Long but Finite Lives, Journal of Economic Theory, vol.22, pp.136-154, 1980.

W. Robert and . Rosenthal, A class of games possessing pure-strategy nash equilibria, International Journal of Game Theory, vol.2, issue.1, pp.65-67, 1973.

R. Selten, Spieltheoretische behandlung eines oligopolmodells mit nachfrageträgheit: Teil i: Bestimmung des dynamischen preisgleichgewichts, Zeitschrift für die gesamte Staatswissenschaft/Journal of Institutional and Theoretical Economics, vol.12, pp.301-324, 1965.

R. Selten, Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games, International journal of game theory, vol.4, issue.1, pp.25-55, 1975.

M. Smith and . George-r-price, The logic of animal conflict, Nature, vol.246, issue.5427, p.15, 1973.

J. Smith, Evolution and the Theory of Games, 1982.

G. Szabó and G. Fath, Evolutionary games on graphs, Physics reports, vol.446, issue.4-6, pp.97-216, 2007.

B. Thomas, On evolutionarily stable sets, Journal of Mathematical Biology, vol.22, issue.1, pp.105-115, 1985.

T. Tregenza, Building on the ideal free distribution, Adv. Ecol. Res, pp.253-307, 1995.

A. Vetta, Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions, The 43rd Annual IEEE Symposium on, pp.416-425, 2002.

M. Gandimohan, . Viswanathan, V. Sergey, S. Buldyrev, . Havlin et al., Optimizing the success of random searches, nature, vol.401, issue.6756, p.911, 1999.

V. Neumann and O. Morgenstern, Theory of games and economic behavior, 1944.

Y. Yovel, The bat lab, 2019.