Wat was het zwakste team op het EK voetbal, en is het team dat straks de cup wint echt het sterkste van allemaal? Omdat lang niet alle 24 teams tegen elkaar spelen tijdens het toernooi, blijft daar altijd discussie over mogelijk.  Maar de ploegen rangschikken naar analogie van hoe Google dat doet met websites, is een goede maat voor hun werkelijke speelsterkte.  

Ranking the Stars op het EK Voetbal

Door Arnout Jaspers

Ook de krachtsverhouding van elftallen die niet tegen elkaar speelden, is te bepalen

Was Nederland of Kroatië sterker op het EK 2021? Kijken naar het onderlinge resultaat kan niet, want ze zaten in verschillende poules en stonden in verschillende achtste-finales, waarna ze er allebei uit vlogen. Andere vraag: op 11 juli weten we wie het EK gewonnen heeft, maar weten we dan ook zeker dat dit de sterkste ploeg van allemaal was?

Hoewel zulke vragen niet met absolute zekerheid te beantwoorden zijn, valt er dankzij wiskundige technieken toch wel wat zinnigs over te zeggen. Vanwege de opbouw van een EK of WK, met poules van maar vier teams en daarna een knock-out systeem, kun je met elementaire kansrekening al aantonen, dat zo’n toernooi meestal niet door de beste ploeg gewonnen wordt.

Michiel Hochstenbach, universitair hoofddocent aan de TU Eindhoven, heeft nu met een methode die ook wordt gebruikt door Google’s page rank algoritme, een ranglijst van alle 24 EK deelnemers gemaakt.  Uitgangspunt is een ‘gerichte graaf’ waarin voetbalelftallen de knooppunten (‘knopen’) zijn, en tussen twee knopen A en B loopt een pijl als team A gewonnen heeft van team B (‘gericht’ slaat op het feit dat de verbinding tussen twee knopen een richting heeft).
Hieronder staat een willekeurig voorbeeld van zo’n graaf met 4 ploegen A, B, C en D. Als A, B, C en D websites waren, zou een pijl tussen twee knopen betekenen dat de ene website linkt naar de andere.

Voor het EK moet je dus een graaf tekenen met 24 knopen en (op het eind, als alle 51 wedstrijden gespeeld zijn), 51 pijlen daar tussen. 

Een equivalente manier om dit wiskundig te beschrijven, is alle teams een nummer geven, en dan een matrix van 24 kolommen en 24 rijen opstellen, dus in totaal 24×24 = 552 getallen. Als twee teams, zeg team 3 en team 21, niet tegen elkaar gespeeld hebben, staat in kolom 3, rij 21 het getal 0.  Omdat lang niet alle teams tegen elkaar spelen op het EK, bestaat deze matrix dus vooral uit nullen (501 van de 552 getallen).
Als bijvoorbeeld team 10 en team 15 wel tegen elkaar gespeeld hebben, staat in kolom 10, rij 15 een positief getal ongeijk aan nul. Welk getal dat is, hangt af van de waarde (het ‘gewicht’) die je toekent aan een overwinning, een gelijkspel, elk gemaakt doelpunt, en dergelijke. Dat zijn dus parameters die je vastlegt voordat je de ranglijst gaat uitrekenen.
Hochstenbach: “Omdat er relatief maar zo weinig wedstrijden gespeeld worden, kan één wedstrijd al heel veel invloed hebben. Het blijkt dat juist de gelijke spelen een grote rol spelen. De uitdaging is, om daar een goed gewicht op te plakken.”

Zo meteen meer over de wiskundige methode om uit zo’n graaf of matrix een ranglijst te destilleren, maar eerst twee resultaten; eerst zonder, dan mét meetellen van gelijke spelen:

Hoe kom je nu, op basis van de graaf, aan zo’n ranglijst?  Het idee is dat je een groot aantal keren (in theorie oneindig vaak), beginnend bij een willekeurige knoop, een wandeling door die graaf gaat maken waarbij je de pijlen volgt. Als van een knoop meerdere pijlen uit gaan, gooi je een dobbelsteen op om te beslissen welke pijl je volgt. De technische term voor zo’n wandeling door een graaf is ‘Markov-keten’.
Daarnaast zit er nóg een toevalscomponent in die wandelingen: bij elke stap springt die met een zekere kans (zeg, 15%) niet via een pijl over naar de volgende knoop, maar naar een volkomen willekeurige knoop. Dit is vooral bedoeld om er voor te zorgen dat wandelingen niet te snel vast lopen, en de hele graaf op den duur bezocht wordt.
Tenslotte tel je voor al die wandelingen op hoe vaak je in welke knoop geweest bent. De vaakst bezochte knoop is dan nummer 1 in de ranglijst, de op een na vaakst bezochte nummer 2, enzovoort.

Google bepaalt volgens hetzelfde principe welke websites het belangrijkst zijn. Je maakt dan, door telkens at random een link aan te klikken op een webpagina, heel veel wandelingen door het world wide web, en de websites waar je op het eind het vaakst geweest bent,  zijn blijkbaar de belangrijkste.

Wiskundig komt dit neer op het bepalen van de grootste eigenvector van de matrix waar de graaf equivalent mee is. Die eigenvector (in wezen een kolom getallen) is dan de ranglijst. Al ruim een eeuw geleden bewezen de wiskundigen Perron en Frobenius dat zo’n vierkante matrix met alleen maar positieve (inclusief 0) getallen altijd een unieke grootste eigenvector heeft. [https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem]  Met andere woorden: deze methode levert altijd een zinnige ranglijst op, en een zinnige Google page ranking.

Niettemin, de ranglijst die uit zo’n berekening rolt, wordt stevig beïnvloed door allerlei parameters die je vrij kunt kiezen. Hochstenbach experimenteerde onder meer met de kans dat een wandeling puur toevallig overspringt van de ene naar de volgende knoop. Google kiest bij het uitrekenen van z’n ranking voor een kans van 15%, maar volgens Hochstenbach is dit niet voldoende voor de EK-ranglijst, omdat één wedstrijd dan een te grote invloed heeft op de plaats van een team op de ranglijst. Daarom heeft hij de EK-ranglijst ook uitgerekend met een toevalsparameter van 50%.
‘Dat zijn parameters waar iedereen mee kan spelen’, aldus Hochstenbach. Dit is allemaal al lang bekende wiskunde, benadrukt hij; deze EK-ranglijsten zijn slechts een mooie  illustratie van de wiskunde van grafen en Markov-ketens.