Similarity suppresses cyclicity: why similar competitors form hierarchies. (English) Zbl 1530.91060
Summary: Competitive systems can exhibit both hierarchical (transitive) and cyclic (intransitive) structures. Despite theoretical interest in cyclic competition, which offers richer dynamics and occupies a larger subset of the scope of possible competitive systems, most real-world systems are predominantly transitive. Why? Here, we introduce a generic mechanism that promotes transitivity, even when there is ample room for cyclicity. We demonstrate that, if competitive outcomes depend smoothly on competitor attributes, then similar competitors compete transitively. We quantify the rate of convergence to transitivity given the similarity of the competitors and the smoothness of the performance function. Thus, we prove the adage regarding apples and oranges. Similar objects admit well-ordered comparisons; diverse objects may not.
Keywords:
evolutionary game theory; competitive systems; transitivity; hierarchy; Helmholtz-Hodge decompositionSoftware:
GitHubReferences:
| [1] | Abrams, P. A., Modelling the adaptive dynamics of traits involved in inter- and intraspecific interactions: An assessment of three methods, Ecol. Lett., 4 (2001), pp. 166-175. |
| [2] | Arrow, K. J., Social Choice and Individual Values, 3rd ed., Yale University Press, 2012. · Zbl 0984.91513 |
| [3] | Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnecki, W., Perolat, J., Jaderberg, M., and Graepel, T., Open-ended learning in symmetric zero-sum games, in Proceedings of the International Conference on Machine Learning, PMLR, , 2019, pp. 434-443. |
| [4] | Balduzzi, D., Tuyls, K., Perolat, J., and Graepel, T., Re-evaluating evaluation, in Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), , Montréal, Canada, , Bengio, S. et al., eds., Curran Associates, 2018. |
| [5] | Bell, R. M. and Koren, Y., Lessons from the Netflix prize challenge, ACM SIGKDD Explorations Newsletter, 9 (2007), pp. 75-79. |
| [6] | Bell, R. M., Koren, Y., and Volinsky, C., The Bellkor Solution to the Netflix Prize, Association for Computing Machinery, New York, NY, 2007, doi:10.1145/2835776.2835787. |
| [7] | Bell, R. M., Koren, Y., and Volinsky, C., All together now: A perspective on the Netflix prize, Chance, 23 (2010), pp. 24-29. |
| [8] | Bozóki, S., Csató, L., and Temesi, J., An application of incomplete pairwise comparison matrices for ranking top tennis players, Eur. J. Oper. Res., 248 (2016), pp. 211-218. · Zbl 1346.90530 |
| [9] | Brin, S. and Page, L., Reprint of: The anatomy of a large-scale hypertextual web search engine, Comput. Netw., 56 (2012), pp. 3825-3833. |
| [10] | Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S., A survey of Monte Carlo tree search methods, IEEE Trans. Comput. Intell. AI Games, 4 (2012), pp. 1-43. |
| [11] | Bryan, K. and Leise, T., The 25,000,000,000 eigenvector: The linear algebra behind Google, SIAM Rev., 48 (2006), pp. 569-581, doi:10.1137/050623280. · Zbl 1115.15007 |
| [12] | Cabrales, A., Stochastic replicator dynamics, Internat. Econom. Rev., 41 (2000), pp. 451-481. |
| [13] | Candogan, O., Menache, I., Ozdaglar, A., and Parrilo, P. A., Flows and decompositions of games: Harmonic and potential games, Math. Oper. Res., 36 (2011), pp. 474-503. · Zbl 1239.91006 |
| [14] | Cebra, C., https://github.com/ccebra/Trait-Concentration-and-Self-Organization, 2023. |
| [15] | Cebra, C. and Strang, A., Similarity Suppresses Cyclicity: Why Similar Competitors Form Hierarchies, preprint, arXiv:2205.08015, 2022. |
| [16] | Cesa-Bianchi, N., Gentile, C., Lugosi, G., and Neu, G., Boltzmann exploration done right, in Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), , Long Beach, CA, , Guyon, I. et al., eds., Curran Associates, 2017, pp. 6287-6296. |
| [17] | Chen, S. and Joachims, T., Modeling intransitivity in matchup and comparison data, in Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, , 2016, pp. 227-236. |
| [18] | Cressman, R., Coevolution, adaptive dynamics, and the replicator equation for a single species with a continuous trait space, in Proceedings, International Society of Dynamic Games, , Tucson, AZ, 2004. |
| [19] | Cressman, R., Stability of the replicator equation with continuous strategy space, Math. Social Sci., 50 (2005), pp. 127-147. · Zbl 1115.91010 |
| [20] | Cressman, R. and Hofbauer, J., Measure dynamics on a one-dimensional continuous trait space: Theoretical foundations for adaptive dynamics, Theoret. Popul. Biol., 67 (2005), pp. 47-59. · Zbl 1071.92025 |
| [21] | Cressman, R., Hofbauer, J., and Riedel, F., Stability of the replicator equation for a single species with a multi-dimensional continuous trait space, Theoret. Biol., 239 (2006), pp. 273-288. · Zbl 1445.92190 |
| [22] | Cressman, R. and Tao, Y., The replicator equation and other game dynamics, Proc. Natl. Acad. Sci. USA, 111 (2014), pp. 10810-10817. · Zbl 1355.91011 |
| [23] | Czarnecki, W. M., Gidel, G., Tracey, B., Tuyls, K., Omidshafiei, S., Balduzzi, D., and Jaderberg, M., Real world games look like spinning tops, in Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS 2020), , Vancouver, Canada, , Larochelle, H. et al., eds., Curran Associates, 2020, pp. 17443-17454. |
| [24] | De Vladar, H. P. and Barton, N. H., The contribution of statistical physics to evolutionary biology, Trends Ecol. Evol., 26 (2011), pp. 424-432. |
| [25] | Dieckmann, U. and Law, R., The dynamical theory of coevolution: A derivation from stochastic ecological processes, J. Math. Biol., 34 (1996), pp. 579-612. · Zbl 0845.92013 |
| [26] | Doebli, M. and Ispolatov, I., Complexity and diversity, Science, 328 (2010), pp. 494-497. · Zbl 1226.92053 |
| [27] | Drews, C., The concept and definition of dominance in animal behaviour, Behaviour, 125 (1993), pp. 283-313. |
| [28] | Elkind, E., Lackner, M., and Peters, D., Preference restrictions in computational social choice: Recent progress, in Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, , 2016. |
| [29] | Flanagan, T., The staying power of the legislative status quo: Collective choice in Canada’s parliament after Morgentaler, Canad. J. Political Sci./Revue canadienne de science politique, 30 (1997), pp. 31-53. |
| [30] | Foster, D. and Young, P., Stochastic evolutionary game dynamics, Theoret. Popul. Biol., 38 (1990), pp. 219-232. · Zbl 0703.92015 |
| [31] | Frean, M. and Abraham, E. R., Rock-scissors-paper and the survival of the weakest, Proc. R. Soc. Lond. Ser. B Biol. Sci., 268 (2001), pp. 1323-1327. |
| [32] | Friedman, J., Higgins, L. M., and Gore, J., Community structure follows simple assembly rules in microbial microcosms, Nat. Ecol. Evol., 1 (2017), 0109. |
| [33] | Fudenberg, D., Drew, F., Levine, D. K., and Levine, D. K., The Theory of Learning in Games, , MIT Press, 1998. · Zbl 0939.91004 |
| [34] | Fudenberg, D. and Harris, C., Evolutionary dynamics with aggregate shocks, J. Econ. Theory, 57 (1992), pp. 420-441. · Zbl 0766.92012 |
| [35] | Gaubatz, K. T., Intervention and intransitivity: Public opinion, social choice, and the use of military force abroad, World Polit., 47 (1995), pp. 534-554. |
| [36] | Gehrlein, W. V., Condorcet’s paradox and the Condorcet efficiency of voting rules, Math. Jpn., 45 (1997), pp. 173-199. · Zbl 0869.90013 |
| [37] | Gehrlein, W. V., Condorcet’s paradox and the likelihood of its occurrence: Different perspectives on balanced preferences, Theory and Decision, 52 (2002), pp. 171-199. · Zbl 1030.91500 |
| [38] | Gehrlein, W. V., Condorcet’s Paradox, Springer, 2006. · Zbl 1122.91027 |
| [39] | Gehrlein, W. V. and Lepelley, D., Condorcet efficiency and social homogeneity, in Voting Paradoxes and Group Coherence, Springer, 2011, pp. 157-198. · Zbl 1252.91001 |
| [40] | Godoy, O., Stouffer, D. B., Kraft, N. J., and Levine, J. M., Intransitivity is infrequent and fails to promote annual plant coexistence without pairwise niche differences, Ecology, 98 (2017), pp. 1193-1200. |
| [41] | Haley, M. P., Deutsch, C. J., and Boeuf, B. J. Le, Size, dominance and copulatory success in male northern elephant seals, Mirounga angustirostris, Anim. Behav., 48 (1994), pp. 1249-1260. |
| [42] | Higgins, L. M., Friedman, J., Shen, H., and Gore, J., Co-occurring Soil Bacteria Exhibit a Robust Competitive Hierarchy and Lack of Non-Transitive Interactions, preprint, BioRxiv 175737, 2017. |
| [43] | Hofbauer, J. and Sigmund, K., Evolutionary game dynamics, Bull. Amer. Math. Soc., 40 (2003), pp. 479-519. · Zbl 1049.91025 |
| [44] | Imhof, L. A., The long-run behavior of the stochastic replicator dynamics, Ann. Appl. Probab., 15 (2005), pp. 1019-1045. · Zbl 1081.60045 |
| [45] | Jiang, X., Lim, L.-H., Yao, Y., and Ye, Y., Statistical ranking and combinatorial Hodge theory, Math. Program., 127 (2011), pp. 203-244. · Zbl 1210.90142 |
| [46] | Kandori, M., Mailath, G. J., and Rob, R., Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), pp. 29-56. · Zbl 0776.90095 |
| [47] | Keener, J. P., The Perron-Frobenius theorem and the ranking of football teams, SIAM Rev., 35 (1993), pp. 80-93, doi:10.1137/1035004. · Zbl 0788.62064 |
| [48] | Kendall, M. G. and Smith, B. B., On the method of paired comparisons, Biometrika, 31 (1940), pp. 324-345. · Zbl 0023.14803 |
| [49] | Kerr, B., Riley, M. A., Feldman, M. W., and Bohannan, B. J., Local dispersal promotes biodiversity in a real-life game of rock-paper-scissors, Nature, 418 (2002), pp. 171-174. |
| [50] | Klass, K. and Cords, M., Agonism and dominance in female blue monkeys, Amer. J. Primatol., 77 (2015), pp. 1299-1315. |
| [51] | Koenig, A., Competition for resources and its behavioral consequences among female primates, Int. J. Primatol., 23 (2002), pp. 759-783. |
| [52] | Kurrild-Klitgaard, P., An empirical example of the Condorcet paradox of voting in a large electorate, Public Choice, 107 (2001), pp. 135-145. |
| [53] | Kurrild-Klitgaard, P., Voting paradoxes under proportional representation: Evidence from eight Dutch elections, Scand. Polit. Stud., 31 (2008), pp. 242-267. |
| [54] | Kwiesielewicz, M., The logarithmic least squares and the generalized pseudoinverse in estimating ratios, European J. Oper. Res., 93 (1996), pp. 611-619. · Zbl 0912.90005 |
| [55] | Kwiesielewicz, M. and Van Uden, E., Ranking decision variants by subjective paired comparisons in cases with incomplete data, in International Conference on Computational Science and Its Applications (ICCSA 2003), , , Kumar, V. et al., eds., Springer, 2003, pp. 208-215. |
| [56] | Lagerspetz, E., Social choice in the real world II: Cyclical preferences and strategic voting in the Finnish presidential elections, Scand. Polit. Stud., 20 (1997), pp. 53-67. |
| [57] | Laird, R. A. and Schamp, B. S., Competitive intransitivity promotes species coexistence, Amer. Nat., 168 (2006), pp. 182-193. |
| [58] | Langville, A. N. and Meyer, C. D., Who’s #1?: The Science of Rating and Ranking, Princeton University Press, 2012. · Zbl 1285.00005 |
| [59] | Leimar, O., Multidimensional convergence stability and the canonical adaptive dynamics, Elem. Adapt. Dyn., 2 (2005), pp. 117-128. |
| [60] | Lim, L.-H., Hodge Laplacians on graphs, SIAM Rev., 62 (2020), pp. 685-715, doi:10.1137/18M1223101. · Zbl 1453.05061 |
| [61] | Luca, M. and Smith, J., Salience in quality disclosure: Evidence from the U.S. News college rankings, J. Econ. Manag. Strategy, 22 (2013), pp. 58-77. |
| [62] | Marrow, P., Dieckmann, U., and Law, R., Evolutionary dynamics of predator-prey systems: An ecological perspective, J. Math. Biol., 34 (1996), pp. 556-578. · Zbl 0845.92018 |
| [63] | Massey, K., Statistical Models Applied to the Rating of Sports Teams, Bluefield College, 1997. |
| [64] | May, R. M. and Leonard, W. J., Nonlinear aspects of competition between three species, SIAM J. Appl. Math., 29 (1975), pp. 243-253, doi:10.1137/0129022. · Zbl 0314.92008 |
| [65] | Maynard Smith, J., Evolution and the Theory of Games, Cambridge University, 1982. · Zbl 0526.90102 |
| [66] | McDonough, P. M., Lising, A., Walpole, A. M., and Perez, L. X., College rankings: Democratized college knowledge for whom?, Res. High. Educ., 39 (1998), pp. 513-537. |
| [67] | McKelvey, R. D., Intransitivities in multidimensional voting models and some implications for agenda control, J. Econom. Theory, 12 (1976), pp. 472-482. · Zbl 0373.90003 |
| [68] | McKelvey, R. D., General conditions for global intransitivities in formal voting models, Econometrica, 47 (1979), pp. 1085-1112. · Zbl 0411.90009 |
| [69] | Meszena, G., Kisdi, E., Dieckmann, U., Geritz, S. A., and Metz, J. A., Evolutionary optimisation models and matrix games in the unified perspective of adaptive dynamics, Selection, 2 (2002), pp. 193-220. |
| [70] | Monks, J. and Ehrenberg, R. G., U.S. News & World Report’s college rankings: Why they do matter, Change Mag. High. Learn., 31 (1999), pp. 42-51. |
| [71] | Morse, J. R., Constitutional rules, political accidents, and the course of history: New light on the annexation of Texas, Independent Rev., 2 (1997), pp. 173-200. |
| [72] | Muniz, L., Perry, S., Manson, J. H., Gilkenson, H., Gros-Louis, J., and Vigilant, L., Male dominance and reproductive success in wild white-faced capuchins (Cebus capucinus) at Lomas Barbudal, Costa Rica, Amer. J. Primatol., 72 (2010), pp. 1118-1130. |
| [73] | Munkøe, M., Cycles and instability in politics. Evidence from the 2009 Dutch municipal elections, Public Choice, 158 (2014), pp. 383-397. |
| [74] | Oechssler, J. and Riedel, F., Evolutionary dynamics on infinite strategy spaces, Econom. Theory, 17 (2001), pp. 141-162. · Zbl 0982.91002 |
| [75] | Omidshafiei, S., Tuyls, K., Czarnecki, W. M., Santos, F. C., Rowland, M., Connor, J., Hennes, D., et al., Navigating the landscape of multiplayer games, Nat. Commun., 11 (2020), pp. 1-17. |
| [76] | Park, H. J., Pichugin, Y., and Traulsen, A., Why is cyclic dominance so rare?, eLife, 9 (2020), e57857. |
| [77] | Ralaivaosaona, D., Rasendrahasina, V., and Wagner, S., On the probability that a random digraph is acyclic, in Proceedings of the 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), , , Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020, 25. · Zbl 07651064 |
| [78] | Regenwetter, M., Adams, J., and Grofman, B., On the (sample) Condorcet efficiency of majority rule: An alternative view of majority cycles and social homogeneity, Theory Decis., 53 (2002), pp. 153-186. · Zbl 1032.91583 |
| [79] | Regenwetter, M., Dana, J., and Davis-Stober, C. P., Transitivity of preferences, Psychol. Rev., 118 (2011), pp. 42-56. |
| [80] | Regenwetter, M., Kim, A., Kantor, A., and Ho, M.-H. R., The unexpected empirical consensus among consensus methods, Psychol. Sci., 18 (2007), pp. 629-635. |
| [81] | Reichenbach, T. and Frey, E., Instability of spatial patterns and its ambiguous impact on species diversity, Phys. Rev. Lett., 101 (2008), 058102. |
| [82] | Reichenbach, T., Mobilia, M., and Frey, E., Coexistence versus extinction in the stochastic cyclic Lotka-Volterra model, Phys. Rev. E, 74 (2006), 051907. |
| [83] | Reichenbach, T., Mobilia, M., and Frey, E., Mobility promotes and jeopardizes biodiversity in rock-paper-scissors games, Nature, 448 (2007), pp. 1046-1049. |
| [84] | Reichenbach, T., Mobilia, M., and Frey, E., Noise and correlations in a spatial population model with cyclic competition, Phys. Rev. Lett., 99 (2007), 238105. |
| [85] | Riker, W. H., Liberalism Against Populism: A Confrontation between the Theory of Democracy and the Theory of Social Choice, Vol. 34, W.H. Freeman, 1982. |
| [86] | Schlag, K. H., Why imitate, and if so, how?: A boundedly rational approach to multi-armed bandits, J. Econom. Theory, 78 (1998), pp. 130-156. · Zbl 0895.90003 |
| [87] | Sella, G. and Hirsh, A. E., The application of statistical physics to evolutionary biology, Proc. Natl. Acad. Sci. USA, 102 (2005), pp. 9541-9546. |
| [88] | Shizuka, D. and McDonald, D. B., A social network perspective on measurements of dominance hierarchies, Anim. Behav., 83 (2012), pp. 925-934. |
| [89] | Shoemaker, H. H., Social hierarchy in flocks of the canary, The Auk, 56 (1939), pp. 381-406. |
| [90] | Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., et al., Mastering the game of Go with deep neural networks and tree search, Nature, 529 (2016), pp. 484-489. |
| [91] | Sinervo, B. and Lively, C. M., The rock-paper-scissors game and the evolution of alternative male strategies, Nature, 380 (1996), pp. 240-243. |
| [92] | Sismanis, Y., How I Won the “Chess Ratings - Elo vs the Rest of the World” Competition, preprint, arXiv:1012.4571, 2010. |
| [93] | Slater, P., Inconsistencies in a schedule of paired comparisons, Biometrika, 48 (1961), pp. 303-312. |
| [94] | Smale, L., Frank, L. G., and Holekamp, K. E., Ontogeny of dominance in free-living spotted hyaenas: Juvenile rank relations with adult females and immigrant males, Anim. Behav., 46 (1993), pp. 467-477. |
| [95] | Solberg, E. J. and Ringsby, T. H., Does male badge size signal status in small island populations of house sparrows, Passer domesticus?, Ethology, 103 (1997), pp. 177-186. |
| [96] | Soliveres, S. and Allan, E., Everything you always wanted to know about intransitive competition but were afraid to ask, J. Ecol., 106 (2018), pp. 807-814. |
| [97] | Soliveres, S., Maestre, F. T., Ulrich, W., Manning, P., Boch, S., Bowker, M. A., Prati, D., et al., Intransitive competition is widespread in plant communities and maintains their species richness, Ecol. Lett., 18 (2015), pp. 790-798. |
| [98] | Stefani, R. T., Football and basketball predictions using least squares, IEEE Trans. Syst. Man Cybernet., 7 (1977), pp. 117-121. |
| [99] | Stefani, R. T., Improved least squares football, basketball, and soccer predictions, IEEE Trans. Syst. Man Cybernet., 10 (1980), pp. 116-123. |
| [100] | Stefani, R. T., The methodology of officially recognized international sports rating systems, J. Quant. Anal. Sports, 7 (2011), 10. |
| [101] | Strang, A., Abbott, K. C., and Thomas, P. J., The network HHD: Quantifying cyclic competition in trait-performance models of tournaments, SIAM Rev., 64 (2022), pp. 360-391, doi:10.1137/20M1321012. · Zbl 1489.90010 |
| [102] | Strauss, E. D. and Holekamp, K. E., Social alliances improve rank and fitness in convention-based societies, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8919-8924. |
| [103] | Taylor, P. D., Allele-frequency change in a class-structured population, Amer. Nat., 135 (1990), pp. 95-106. |
| [104] | Tesauro, G., Programming backgammon using self-teaching neural nets, Artif. Intell., 134 (2002), pp. 181-199. · Zbl 0982.68124 |
| [105] | Tesauro, G., Temporal difference learning and TD-Gammon, Commun. ACM, 38 (1995), pp. 58-68. |
| [106] | Tideman, N., Collective Decisions and Voting: The Potential for Public Choice, Ashgate Publishing, Ltd., 2006. |
| [107] | Van Deemen, A. M., On the empirical relevance of Condorcet’s paradox, Public Choice, 158 (2014), pp. 311-330. |
| [108] | Van Deemen, A. M. and Vergunst, N. P., Empirical evidence of paradoxes of voting in Dutch elections, Public Choice, 97 (1998), pp. 475-490. |
| [109] | Wright, E. S. and Vetsigian, K. H., Inhibitory interactions promote frequent bistability among competing bacteria, Nat. Commun., 7 (2016), 11274. |
| [110] | Xue, C. and Goldenfeld, N., Coevolution maintains diversity in the stochastic “Kill the Winner” model, Phys. Rev. Lett., 119 (2017), 268101. |
| [111] | Zeeman, E. C., Dynamics of the evolution of animal conflicts, J. Theoret. Biol., 89 (1981), pp. 249-270. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
