{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:13:02Z","timestamp":1757617982853,"version":"3.44.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T00:00:00Z","timestamp":1747267200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T00:00:00Z","timestamp":1747267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V025562\/1","EP\/V025562\/1"],"award-info":[{"award-number":["EP\/V025562\/1","EP\/V025562\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to rank solutions and make selection decisions. This makes CoEAs a useful tool for optimisation problems that have intrinsically interactive domains. Over the past decades, many ways to aggregate the outcomes of interactions have been considered. At the moment, it is unclear which of these is the best choice. Previous research is fragmented and most of the fitness aggregation methods (fitness measures) proposed have only been studied empirically. We argue that a proper understanding of the dynamics of CoEAs and their fitness measures can only be achieved through rigorous analysis of their behaviour. In this work we make a step towards this goal by using runtime analysis to study two commonly used fitness measures. We show a dichotomy in the behaviour of a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$(1, \\lambda )$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>\u03bb<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\u00a0CoEA when optimising a <jats:sc>Bilinear<\/jats:sc> problem. The algorithm finds a solution near the Nash equilibrium in polynomial time with high probability if the worst interaction is used as a fitness measure but is inefficient if the average of all interactions is used instead.\n<\/jats:p>","DOI":"10.1007\/s00453-025-01313-z","type":"journal-article","created":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T00:06:56Z","timestamp":1747267616000},"page":"1274-1310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems"],"prefix":"10.1007","volume":"87","author":[{"given":"Mario Alejandro","family":"Hevia Fajardo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Per Kristian","family":"Lehre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,15]]},"reference":[{"key":"1313_CR1","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1007\/978-3-540-92910-9_31","volume-title":"Handbook of Natural Computing","author":"E Popovici","year":"2012","unstructured":"Popovici, E., Bucci, A., Wiegand, R.P., De Jong, E.D.: Coevolutionary principles. In: Rozenberg, G., B\u00e4ck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 987\u20131033. Springer, Berlin, Heidelberg (2012)"},{"issue":"3","key":"1313_CR2","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1109\/TEVC.2018.2868770","volume":"23","author":"X Ma","year":"2019","unstructured":"Ma, X., Li, X., Zhang, Q., Tang, K., Liang, Z., Xie, W., Zhu, Z.: A survey on cooperative co-evolutionary algorithms. IEEE Trans. Evol. Comput. 23(3), 421\u2013441 (2019)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"1313_CR3","doi-asserted-by":"crossref","unstructured":"Branke, J., Rosenbusch, J.: New approaches to coevolutionary worst-case optimization. In: Parallel Problem Solving from Nature \u2013 PPSN X, pp. 144\u2013153. Springer, Berlin, Heidelberg (2008)","DOI":"10.1007\/978-3-540-87700-4_15"},{"key":"1313_CR4","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-1-4757-4137-7_17","volume":"86","author":"MT Jensen","year":"2003","unstructured":"Jensen, M.T.: A new look at solving minimax problems with coevolution. Metaheurist. Comput. Decision-Making 86, 369 (2003)","journal-title":"Metaheurist. Comput. Decision-Making"},{"issue":"4","key":"1313_CR5","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1162\/artl.1994.1.4.353","volume":"1","author":"K Sims","year":"1994","unstructured":"Sims, K.: Evolving 3D morphology and behavior by competition. Artif. Life 1(4), 353\u2013372 (1994)","journal-title":"Artif. Life"},{"issue":"1\u20133","key":"1313_CR6","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/0167-2789(90)90076-2","volume":"42","author":"WD Hillis","year":"1990","unstructured":"Hillis, W.D.: Co-evolving parasites improve simulated evolution as an optimization procedure. Phys. D 42(1\u20133), 228\u2013234 (1990)","journal-title":"Phys. D"},{"key":"1313_CR7","doi-asserted-by":"crossref","unstructured":"Flores, D., Hemberg, E., Toutouh, J., O\u2019Reily, U.-M.: Coevolutionary generative adversarial networks for medical image augumentation at scale. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO \u201922, pp. 367\u2013376. Association for Computing Machinery, New York, NY, USA (2022)","DOI":"10.1145\/3512290.3528742"},{"key":"1313_CR8","unstructured":"Luke, S., Wiegand, R.P.: When coevolutionary algorithms exhibit evolutionary dynamics. In: Genetic and Evolutionary Computation Conference Workshop Program, pp. 236\u2013241 (2002)"},{"issue":"1","key":"1313_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco.1997.5.1.1","volume":"5","author":"CD Rosin","year":"1997","unstructured":"Rosin, C.D., Belew, R.K.: New methods for competitive coevolution. Evol. Comput. 5(1), 1\u201329 (1997)","journal-title":"Evol. Comput."},{"issue":"2","key":"1313_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3458845","volume":"1","author":"E Hemberg","year":"2021","unstructured":"Hemberg, E., Toutouh, J., Al-Dujaili, A., Schmiedlechner, T., O\u2019Reilly, U.-M.: Spatial coevolution for generative adversarial network training. ACM Trans. Evol. Learn. Optim. 1(2), 1\u201328 (2021)","journal-title":"ACM Trans. Evol. Learn. Optim."},{"key":"1313_CR11","unstructured":"Wiegand, R.P., Liles, W.C., Jong, K.A.D.: An empirical analysis of collaboration methods in cooperative coevolutionary algorithms. In: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. GECCO\u201901, pp. 1235\u20131242. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2001)"},{"key":"1313_CR12","volume-title":"An analysis of cooperative coevolutionary algorithms","author":"RP Wiegand","year":"2004","unstructured":"Wiegand, R.P.: An analysis of cooperative coevolutionary algorithms. Virginia, USA (2004)"},{"key":"1313_CR13","volume-title":"Emergent geometric organization and informative dimensions in coevolutionary algorithms","author":"A Bucci","year":"2007","unstructured":"Bucci, A.: Emergent geometric organization and informative dimensions in coevolutionary algorithms. Massachusetts, USA (2007)"},{"issue":"4","key":"1313_CR14","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1162\/1063656043138905","volume":"12","author":"T Jansen","year":"2004","unstructured":"Jansen, T., Wiegand, R.P.: The cooperative coevolutionary (1+1) EA. Evol. Comput. 12(4), 405\u2013434 (2004)","journal-title":"Evol. Comput."},{"key":"1313_CR15","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Lin, S.: Is CC-(1+1) EA more efficient than (1+1) EA on separable and inseparable problems? In: 2023 IEEE Congress on Evolutionary Computation (CEC), pp. 1\u20139 (2023)","DOI":"10.1109\/CEC53210.2023.10254149"},{"key":"1313_CR16","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO \u201922, pp. 1408\u20131416. Association for Computing Machinery, New York, NY, USA (2022)","DOI":"10.1145\/3512290.3528853"},{"key":"1313_CR17","doi-asserted-by":"crossref","unstructured":"Hevia\u00a0Fajardo, M.A., Lehre, P.K., Lin, S.: Runtime analysis of a co-evolutionary algorithm: Overcoming negative drift in maximin-optimisation. In: Proceedings of the 17th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms. FOGA \u201923, pp. 73\u201383. Association for Computing Machinery, New York, NY, USA (2023)","DOI":"10.1145\/3594805.3607132"},{"key":"1313_CR18","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Lin, S.: Concentration tail-bound analysis of coevolutionary and bandit learning algorithms. In: Larson, K. (ed.) Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. IJCAI \u201924, pp. 6940\u20136948. International Joint Conferences on Artificial Intelligence Organization, California, USA (2024)","DOI":"10.24963\/ijcai.2024\/767"},{"key":"1313_CR19","doi-asserted-by":"crossref","unstructured":"Benford, A., Lehre, P.K.: Runtime analysis of coevolutionary algorithms on a class of symmetric zero-sum games. In: Li, X., Handl, J. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference. GECCO \u201924. Association for Computing Machinery, New York, NY, USA (2024)","DOI":"10.1145\/3638529.3654216"},{"key":"1313_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-031-70071-2_8","volume-title":"Parallel Problem Solving from Nature - PPSN XVIII","author":"PK Lehre","year":"2024","unstructured":"Lehre, P.K., Lin, S.: Overcoming binary adversarial optimisation with competitive coevolution. In: Affenzeller, M., Winkler, S.M., Kononova, A.V., Trautmann, H., Tu\u0161ar, T., Machado, P., B\u00e4ck, T. (eds.) Parallel Problem Solving from Nature - PPSN XVIII, pp. 117\u2013132. Springer, Cham (2024)"},{"key":"1313_CR21","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-031-70071-2_14","volume-title":"Parallel Problem Solving from Nature - PPSN XVIII","author":"MAH Fajardo","year":"2024","unstructured":"Fajardo, M.A.H., Lehre, P.K.: Ranking diversity benefits coevolutionary algorithms on an intransitive game. In: Affenzeller, M., Winkler, S.M., Kononova, A.V., Trautmann, H., Tu\u0161ar, T., Machado, P., B\u00e4ck, T. (eds.) Parallel Problem Solving from Nature - PPSN XVIII, pp. 213\u2013229. Springer, Cham (2024)"},{"key":"1313_CR22","volume-title":"Advances in Neural Information Processing Systems","author":"E-V Vlatakis-Gkaragkounis","year":"2019","unstructured":"Vlatakis-Gkaragkounis, E.-V., Flokas, L., Piliouras, G.: Poincar\u00e9 recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games. In: Wallach, H., Larochelle, H., Beygelzimer, A., Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 32. Curran Associates Inc, Cannock, UK (2019)"},{"key":"1313_CR23","unstructured":"Zhang, G., Yu, Y.: Convergence of gradient methods on Bilinear zero-sum games. ArXiv e-prints (2020) arXiv:1908.05699"},{"key":"1313_CR24","unstructured":"Liang, T., Stokes, J.: Interaction matters: a note on non-asymptotic local convergence of Generative Adversarial Networks. ArXiv e-prints (2019) arXiv:1802.06132"},{"key":"1313_CR25","unstructured":"Mokhtari, A., Ozdaglar, A., Pattathil, S.: A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach. ArXiv e-prints (2019) arXiv:1901.08511"},{"key":"1313_CR26","doi-asserted-by":"crossref","unstructured":"Hevia\u00a0Fajardo, M.A., Lehre, P.K.: How fitness aggregation methods affect the performance of competitive coeas on bilinear problems. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO \u201923, pp. 1593\u20131601. Association for Computing Machinery, New York, NY, USA (2023)","DOI":"10.1145\/3583131.3590506"},{"key":"1313_CR27","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theoret. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"1313_CR28","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"J Lengler","year":"2020","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer, Cham (2020)"},{"key":"1313_CR29","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2019.08.021","volume":"796","author":"T K\u00f6tzing","year":"2019","unstructured":"K\u00f6tzing, T., Krejca, M.S.: First-hitting times under drift. Theoret. Comput. Sci. 796, 51\u201369 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1313_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-29414-4","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"B Doerr","year":"2020","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer, Cham (2020)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01313-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01313-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01313-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T14:42:54Z","timestamp":1757169774000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01313-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,15]]},"references-count":30,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["1313"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01313-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,5,15]]},"assertion":[{"value":"26 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}