Sportbajnokságok sorsolásának optimalizálása

Számos csapatsport világbajnoksága csoportkörös küzdelmekkel kezdődik, ahol a résztvevő csapatok csak a saját csoportjukba sorsolt csapatokkal játszanak. Ebben az esetben két észszerű célja lehet a szervezőknek. Egyrészt, a torna egyediségének biztosítása és nézettségének növelése érdekében célszerű különböző, például földrajzi, korlátozó feltételekkel szűkíteni a megengedett csoportok halmazát. Másrészt, a csoportsorsolás során használt heurisztikus algoritmus ilyen korlátozó feltételek nem egyenletes eloszlású: bizonyos csapatpárok esetén torzíthatja az egy csoportba kerülés esélyét az elméleti szempontból igazságos valószínűséghez képest. Csató László, a Mérnöki és Üzleti Intelligencia KutatólaboratóriumOperációkutatás és Döntési Rendszerek Kutatócsoport tudományos főmunkatársa egy parametrikus optimalizálási feladatot javasolt a két cél közötti legjobb kompromisszum megtalálására. A módszer segítségével a 2018-as és 2022-es labdarúgó-világbajnokság esetén is meghatározta a hatékony korlátozó feltételek halmazát. Az eredményeket ismertető tanulmány egy operációkutatási folyóirat, az „International Transactions in Operational Research” hasábjain jelent meg, „How to optimise tournament draws: The case of the FIFA World Cup” címmel.

Az elmúlt évtizedekben rendezett labdarúgó-világbajnokságokon a résztvevő válogatottakat négy kalapba sorolták, majd a csoportok mindegyikébe egy-egy csapat sorsoltak minden kalapból. Mivel különböző kontinensek válogatottjai sokkal ritkábban játszanak egymás ellen, mint az azonos kontinensről érkezők, az interkontinentális mérkőzések számának növelésére a szabályok előírták, hogy egy csoportba egy földrészről – Európa kivételével – legfeljebb egy csapat kerülhessen, míg európaiból legalább egy, legfeljebb viszont kettő. Hasonló korlátozó feltételekkel biztosítják a kosárlabda-világbajnokság csoportjainak diverzitását is; ugyanakkor a kézilabdában és a röplabdában nem használják ezeket. Például a 2026-os férfi kézilabda-világbajnokságon öt csoportban kettő, további egy-egy csoportban pedig egy, három, illetve négy európai csapat játszott. Ugyanakkor a négy ázsiai válogatott közül kettő, az öt afrikai közül szintén kettő egy csoportba került.

A probléma

Korlátozó feltételek előírásakor nem használható a szokásos sorsolási eljárás, mert a csapatok véletlenszerű kihúzása a megfelelő sorba rendezett kalapokból nem garantálná a feltételek teljesülését. Ezért a sorsolást rendszerint egy Ugró módszernek nevezett algoritmussal végzik: az éppen kihúzott válogatottat az alfabetikus sorrendben első olyan csoportba helyezték, amivel a hátralevő csapatok még eloszthatók maradnak a fennmaradó helyekre úgy, hogy egyetlen korlátozó feltétel se sérüljön. Az eljárás mégsem olyan egyszerű, mint elsőre tűnhet. Ha például egy afrikai csapatot szeretnénk elhelyezni, nem elég csak azokat a csoportokat kizárni, melyekben már van afrikai csapat – ugyanis előfordulhat, hogy az adott válogatottat még be tudjuk osztani a feltételek sérülése nélkül, de a megmaradó csapatokat már nem.

Az Ugró algoritmus a lehetséges megoldások halmazán nem egyenletes eloszlású, azaz bizonyos csoportbeosztások nagyobb valószínűséggel fordulhatnak elő egy másiknál. Például a 2022-es labdarúgó-világbajnokság sorsolásakor a házigazda Katar és Mexikó pontosan 12,5 százalékos valószínűséggel kerülhetett egy csoportba (amikor a második kalapból elsőként húzták Mexikót), de az igazságos valószínűség csak mintegy 9 százalék; ez utóbbit szimulációval becsültük. Vagyis, e két csapat esetén az Ugró módszer torzítása 3,5 százalékpont.

Az ajánlott módszer

A szervezők célja tehát az interkontinentális csoportmérkőzések számának maximalizálása és a sorsolási módszer által okozott igazságtalanság minimalizálása. A két célfüggvény jellemzően csak egymás rovására javítható: a földrajzi korlátozó feltételek hiánya az első cél szempontjából a lehető legrosszabb, a második cél viszont teljes mértékben elérhető ezzel.

A kompromisszum megtalálására egy parametrikus optimalizálási módszert javasoltunk, amivel a két célfüggvény tetszőleges súlyozása mellett meghatározható a hatékony korlátozó feltételek halmaza. A 2018-as és 2022-es labdarúgó-világbajnokságok esetén a 32-32 vizsgált forgatókönyvből legfeljebb öt bizonyult optimálisnak a két cél szempontjából. Tehát a javasolt megközelítés rendkívül hasznos lehet a döntéshozók számára a sorsolás során használandó feltételhalmaz lényeges szűkítése, a választható opciók számának redukálása révén.

Kép: Fauzan Saari // Unsplash