The network HHD: quantifying cyclic competition in trait-performance models of tournaments. (English) Zbl 1489.90010
Summary: Competitive tournaments appear in sports, politics, population ecology, and animal behavior. All of these fields have developed methods for rating competitors and ranking them accordingly. A tournament is intransitive if it is not consistent with any ranking. Intransitive tournaments contain rock-paper-scissors type cycles. The discrete Helmholtz-Hodge decomposition (HHD) is well adapted to describing intransitive tournaments. It separates a tournament into perfectly transitive and perfectly cyclic components, where the perfectly transitive component is associated with a set of ratings. The size of the cyclic component can be used as a measure of intransitivity. Here we show that the HHD arises naturally from two classes of tournaments with simple statistical interpretations. We then discuss six different sets of assumptions that define equivalent decompositions. This analysis motivates the choice to use the HHD among other existing methods. Success in competition is often mediated by the traits of the competitors. A trait-performance model assumes that the probability that one competitor beats another is a function of their traits. We show that if the traits of each competitor are drawn independently and identically from a trait distribution, then the expected degree of intransitivity in the network can be computed explicitly. We show that increasing the number of pairs of competitors who could compete promotes cyclic competition, and that correlation in the performance of \(A\) against \(B\) with the performance of \(A\) against \(C\) promotes transitive competition. The expected size of cyclic competition can thus be understood by analyzing this correlation.
Keywords:
cyclic competition; intransitivity measures; least squares rating; Helmholtz-Hodge decomposition; trait-performance modelsReferences:
| [1] | D. Aldous, Elo ratings and the sports model: A neglected topic in applied probability?, Statist. Sci., 32 (2017), pp. 616-629. · Zbl 1383.60057 |
| [2] | M. C. Appleby, The probability of linearity in hierarchies, Animal Behav., 31 (1983), pp. 600-608. |
| [3] | J. Bartholdi, C. A. Tovey, and M. A. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice Welfare, 6 (1989), pp. 157-165. · Zbl 0672.90004 |
| [4] | J. L. Beacham, The relative importance of body size and aggressive experience as determinants of dominance in pumpkinseed sunfish, Lepomis gibbosus, Animal Behav., 36 (1988), pp. 621-623. |
| [5] | B. Bollobás, Modern Graph Theory, Grad. Texts in Math. 184, Springer Science & Business Media, 2013. |
| [6] | S. Bozóki, L. Csató, and J. Temesi, An application of incomplete pairwise comparison matrices for ranking top tennis players, European J. Oper. Res., 248 (2016), pp. 211-218. · Zbl 1346.90530 |
| [7] | R. A. Bradley, Incomplete block rank analysis: On the appropriateness of the model for a method of paired comparisons, Biometrics, 10 (1954), pp. 375-390. · Zbl 0058.35803 |
| [8] | R. A. Bradley and M. E. Terry, Rank analysis of incomplete block designs: I. The method of paired comparisons, Biometrika, 39 (1952), pp. 324-345. · Zbl 0047.12903 |
| [9] | S. Brin and L. Page, Reprint of: The anatomy of a large-scale hypertextual web search engine, Comput. Networks, 56 (2012), pp. 3825-3833. |
| [10] | O. Candogan, I. Menache, A. Ozdaglar, and P. A. Parrilo, Flows and decompositions of games: Harmonic and potential games, Math. Oper. Res., 36 (2011), pp. 474-503. · Zbl 1239.91006 |
| [11] | P. Charbit, S. Thomassé, and A. Yeo, The minimum feedback arc set problem is NP-hard for tournaments, Combin. Probab. Comput., 16 (2007), pp. 1-4. · Zbl 1120.05038 |
| [12] | I. D. Chase, C. Bartolomeo, and L. A. Dugatkin, Aggressive interactions and inter-contest interval: How long do winners keep winning?, Animal Behav., 48 (1994), pp. 393-400. |
| [13] | I. D. Chase, C. Tovey, D. Spangler-Martin, and M. Manfredonia, Individual differences versus social dynamics in the formation of animal dominance hierarchies, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 5744-5749. |
| [14] | W. Colley, Colley’s Bias Free College Football Ranking Method, Ph.D. thesis, Princeton University, 2002. |
| [15] | H. de Vries, An improved test of linearity in dominance hierarchies containing unknown or tied relationships, Animal Behav., 50 (1995), pp. 1375-1389. |
| [16] | H. de Vries, Finding a dominance order most consistent with a linear hierarchy: A new procedure and review, Animal Behav., 55 (1998), pp. 827-843. |
| [17] | H. de Vries and M. C. Appleby, Finding an appropriate order for a hierarchy: A comparison of the I&SI and the BBS methods, Animal Behav., 59 (2000), pp. 239-245. |
| [18] | C. Drews, The concept and definition of dominance in animal behaviour, Behaviour, 125 (1993), pp. 283-313. |
| [19] | P. Eades, X. Lin, and W. F. Smyth, A fast and effective heuristic for the feedback arc set problem, Inform. Process. Lett., 47 (1993), pp. 319-323. · Zbl 0787.68078 |
| [20] | U. Endriss and R. de Haan, Complexity of the Winner Determination Problem in Judgment Aggregation: Kemeny, Slater, Tideman, Young, Report PP-2015-23, https://eprints.illc.uva.nl/534/, 2016. |
| [21] | M. Frean and E. R. Abraham, Rock-scissors-paper and the survival of the weakest, Proc. Roy. Soc. London Ser. B Biol. Sci., 268 (2001), pp. 1323-1327. |
| [22] | G. Galbiati, On optimum cycle bases, Electron. Notes Discrete Math., 10 (2001), pp. 113-116. · Zbl 1182.05123 |
| [23] | F. Galimberti, A. Fabiani, and L. Boitani, Socio-spatial levels in linearity analysis of dominance hierarchies: A case study on elephant seals, J. Ethol., 21 (2003), pp. 131-136. |
| [24] | W. V. Gehrlein, Condorcet’s paradox and the Condorcet efficiency of voting rules, Math. Japon., 45 (1997), pp. 173-199. · Zbl 0869.90013 |
| [25] | M. E. Glickman, Parameter estimation in large dynamic paired comparison experiments, J. Roy. Statist. Soc. Ser. C Appl. Statist., 48 (1999), pp. 377-394. · Zbl 0939.62071 |
| [26] | O. Godoy, D. B. Stouffer, N. J. Kraft, and J. M. Levine, Intransitivity is infrequent and fails to promote annual plant coexistence without pairwise niche differences, Ecology, 98 (2017), pp. 1193-1200. |
| [27] | M. P. Haley, C. J. Deutsch, and B. J. Le Boeuf, Size, dominance and copulatory success in male northern elephant seals, Mirounga angustirostris, Animal Behav., 48 (1994), pp. 1249-1260. |
| [28] | E. Hemaspaandra, H. Spakowski, and J. Vogel, The complexity of Kemeny elections, Theoret. Comput. Sci., 349 (2005), pp. 382-391. · Zbl 1086.68046 |
| [29] | Y. Hsu and L. L. Wolf, The winner and loser effect: Integrating multiple experiences, Animal Behav., 57 (1999), pp. 903-910. |
| [30] | L. M. Hvattum and H. Arntzen, Using Elo ratings for match result prediction in association football, Internat. J. Forecasting, 26 (2010), pp. 460-470. |
| [31] | J. Jackson and L. Buss, Alleopathy and spatial competition among coral reef invertebrates, Proc. Natl. Acad. Sci. USA, 72 (1975), pp. 5160-5163. |
| [32] | W. M. Jackson and R. L. Winnegrad, Linearity in dominance hierarchies: A second look at the individual attributes model, Animal Behav., 36 (1988), pp. 1237-1240. |
| [33] | X. Jiang, L.-H. Lim, Y. Yao, and Y. Ye, Statistical ranking and combinatorial Hodge theory, Math. Program., 127 (2011), pp. 203-244. · Zbl 1210.90142 |
| [34] | C. R. Johnson and I. Seinen, Selection for restraint in competitive ability in spatial competition systems, Proc. Roy. Soc. London Ser. B Biol. Sci., 269 (2002), pp. 655-663. |
| [35] | J. P. Keener, The Perron-Frobenius theorem and the ranking of football teams, SIAM Rev., 35 (1993), pp. 80-93, https://doi.org/10.1137/1035004. · Zbl 0788.62064 |
| [36] | M. G. Kendall and B. B. Smith, On the method of paired comparisons, Biometrika, 31 (1940), pp. 324-345. · Zbl 0023.14803 |
| [37] | B. Kerr, M. A. Riley, M. W. Feldman, and B. J. Bohannan, Local dispersal promotes biodiversity in a real-life game of rock-paper-scissors, Nature, 418 (2002), pp. 171-174. |
| [38] | K. Klass and M. Cords, Effect of unknown relationships on linearity, steepness and rank ordering of dominance hierarchies: Simulation studies based on data from wild monkeys, Behav. Process., 88 (2011), pp. 168-176. |
| [39] | K. Klass and M. Cords, Agonism and dominance in female blue monkeys, Amer. J. Primatology, 77 (2015), pp. 1299-1315. |
| [40] | A. Koenig, Competition for resources and its behavioral consequences among female primates, Internat. J. Primatology, 23 (2002), pp. 759-783. |
| [41] | S. A. Kovalchik, Searching for the GOAT of tennis win prediction, J. Quantit. Anal. Sports, 12 (2016), pp. 127-138. |
| [42] | M. Kwiesielewicz, The logarithmic least squares and the generalized pseudoinverse in estimating ratios, European J. Oper. Res., 93 (1996), pp. 611-619. · Zbl 0912.90005 |
| [43] | M. Kwiesielewicz and E. Van Uden, Ranking decision variants by subjective paired comparisons in cases with incomplete data, in Proceedings of the 2003 International Conference on Computational Science and Its Applications, Springer, 2003, pp. 208-215. |
| [44] | R. A. Laird and B. S. Schamp, Competitive intransitivity promotes species coexistence, Amer. Naturalist, 168 (2006), pp. 182-193. |
| [45] | H. G. Landau, On dominance relations and the structure of animal societies: I. Effect of inherent characteristics, Bull. Math. Biophys., 13 (1951), pp. 1-19. |
| [46] | A. N. Langville and C. D. Meyer, Who’s # \(1\)?: The Science of Rating and Ranking, Princeton University Press, 2012. · Zbl 1285.00005 |
| [47] | R. A. Lankau and S. Y. Strauss, Mutual feedbacks maintain both genetic and species diversity in a plant community, Science, 317 (2007), pp. 1561-1563. |
| [48] | R. A. Lankau, E. Wheeler, A. E. Bennett, and S. Y. Strauss, Plant-soil feedbacks contribute to an intransitive competitive network that promotes both genetic and species diversity, J. Ecology, 99 (2011), pp. 176-185. |
| [49] | J. Lasek, Z. Szlávik, and S. Bhulai, The predictive power of ranking systems in association football, Internat. J. Appl. Pattern Recog., 1 (2013), pp. 27-46. |
| [50] | M. Lewis, Moneyball: The Art of Winning an Unfair Game, Norton, 2004. |
| [51] | L.-H. Lim, Hodge Laplacians on graphs, SIAM Rev., 62 (2020), pp. 685-715, https://doi.org/10.1137/18M1223101. · Zbl 1453.05061 |
| [52] | K. Massey, Statistical Models Applied to the Rating of Sports Teams, Bluefield College, 1997. |
| [53] | R. M. May and W. J. Leonard, Nonlinear aspects of competition between three species, SIAM J. Appl. Math., 29 (1975), pp. 243-253, https://doi.org/10.1137/0129022. · Zbl 0314.92008 |
| [54] | I. McHale and A. Morton, A Bradley-Terry type model for forecasting tennis match results, Internat. J. Forecasting, 27 (2011), pp. 619-630. |
| [55] | L. Muniz, S. Perry, J. H. Manson, H. Gilkenson, J. Gros-Louis, and L. Vigilant, Male dominance and reproductive success in wild white-faced capuchins (Cebus capucinus) at Lomas Barbudal, Costa Rica, Amer. J. Primatology, 72 (2010), pp. 1118-1130. |
| [56] | R. F. Oliveira, P. K. McGregor, and C. Latruffe, Know thine enemy: Fighting fish gather information from observing conspecific interactions, Proc. Roy. Soc. London Ser. B Biol. Sci., 265 (1998), pp. 1045-1049. |
| [57] | M. Ozanian and K. Badenhausen, Baseball team values 2019: Yankees lead league at 4.6 billion, Forbes, 2019. |
| [58] | P. S. Petraitis, Competitive networks and measures of intransitivity, Amer. Naturalist, 114 (1979), pp. 921-925. |
| [59] | T. Reichenbach and E. Frey, Instability of spatial patterns and its ambiguous impact on species diversity, Phys. Rev. Lett., 101 (2008), art. 058102. |
| [60] | T. Reichenbach, M. Mobilia, and E. Frey, Coexistence versus extinction in the stochastic cyclic Lotka-Volterra model, Phys. Rev. E, 74 (2006), art. 051907. |
| [61] | T. Reichenbach, M. Mobilia, and E. Frey, Mobility promotes and jeopardizes biodiversity in rock-paper-scissors games, Nature, 448 (2007), pp. 1046-1049. |
| [62] | T. Reichenbach, M. Mobilia, and E. Frey, Noise and correlations in a spatial population model with cyclic competition, Phys. Rev. Lett., 99 (2007), art. 238105. |
| [63] | R. M. Sapolsky and L. J. Share, Rank-related differences in cardiovascular function among wild baboons: Role of sensitivity to glucocorticoids, Amer. J. Primatology, 32 (1994), pp. 261-275. |
| [64] | D. Shizuka and D. B. McDonald, A social network perspective on measurements of dominance hierarchies, Animal Behav., 83 (2012), pp. 925-934. |
| [65] | H. H. Shoemaker, Social hierarchy in flocks of the canary, The Auk, (1939), pp. 381-406. |
| [66] | J. B. Silk, Male bonnet macaques use information about third-party rank relationships to recruit allies, Animal Behav., 58 (1999), pp. 45-51. |
| [67] | B. Sinervo and C. M. Lively, The rock-paper-scissors game and the evolution of alternative male strategies, Nature, 380 (1996), pp. 240-243. |
| [68] | Y. Sismanis, How I Won the “Chess Ratings – Elo vs the Rest of the World” Competition, preprint, https://arxiv.org/abs/1012.4571, 2010. |
| [69] | P. Slater, Inconsistencies in a schedule of paired comparisons, Biometrika, 48 (1961), pp. 303-312. |
| [70] | L. Smale, L. G. Frank, and K. E. Holekamp, Ontogeny of dominance in free-living spotted hyaenas: Juvenile rank relations with adult females and immigrant males, Animal Behav., 46 (1993), pp. 467-477. |
| [71] | S. Soliveres, F. T. Maestre, W. Ulrich, P. Manning, S. Boch, M. A. Bowker, D. Prati, M. Delgado-Baquerizo, J. L. Quero, I. Schöning, et al., Intransitive competition is widespread in plant communities and maintains their species richness, Ecology Lett., 18 (2015), pp. 790-798. |
| [72] | R. Stefani, The methodology of officially recognized international sports rating systems, J. Quantit. Anal. Sports, 7 (2011), art. 10, https://doi.org/10.2202/1559-0410.1347. |
| [73] | R. T. Stefani, Football and basketball predictions using least squares, IEEE Trans. Syst. Man Cybernet., 7 (1977), pp. 117-121. |
| [74] | R. T. Stefani, Improved least squares football, basketball, and soccer predictions, IEEE Trans. Syst. Man Cybernet., 10 (1980), pp. 116-123. |
| [75] | G. Strang, The fundamental theorem of linear algebra, Amer. Math. Monthly, 100 (1993), pp. 848-855. · Zbl 0802.15002 |
| [76] | E. D. Strauss and K. E. Holekamp, Social alliances improve rank and fitness in convention-based societies, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8919-8924. |
| [77] | D. M. Stuart-Fox, D. Firth, A. Moussalli, and M. J. Whiting, Multiple signals in chameleon contests: Designing and analysing animal contests as a tournament, Animal Behav., 71 (2006), pp. 1263-1271. |
| [78] | W. Ulrich, S. Soliveres, W. Kryszewski, F. T. Maestre, and N. J. Gotelli, Matrix models for quantifying competitive intransitivity from species abundance data, Oikos, 123 (2014), pp. 1057-1070. |
| [79] | C. S. Valero, Predicting win-loss outcomes in MLB regular season games-A comparative study using data mining methods, Internat. J. Comput. Sci. Sport, 15 (2016), pp. 91-112. |
| [80] | C. Xue and N. Goldenfeld, Coevolution maintains diversity in the stochastic “Kill the Winner” model, Phys. Rev. Lett., 119 (2017), art. 268101. |
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.
