Hogyan csökkenthető egy sportbajnokság csoportsorsolásának torzítása?

Egy sportverseny csoportkörének sorsolásakor gyakran korlátozó feltételekkel kerülik el a valamilyen szempontból hasonló csapatok mérkőzéseit; például a labdarúgó-világbajnokságon minimalizálják az azonos kontinensről érkező csapatok közötti csoportmérkőzések számát. A feltételek teljesülését egy heurisztikus algoritmussal garantálják, ami azonban nem egyenletes eloszlású, azaz a lehetséges megoldások előfordulási valószínűsége különböző lehet. 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 ezt a torzítást elemezte akkor, ha egy csoportba legfeljebb két azonos halmazba tartozó csapat osztható be. Egyszerű elméleti modellekben azonosította az optimális, a torzítás mértékét minimalizáló húzási sorrendet, és három valós példán keresztül illusztrálta az eredmények gyakorlati relevanciáját. Az eredményeket összegző tanulmány egy számítástudományi folyóirat, az Applied Soft Computing hasábjain jelent meg, Reducing the non-uniformity of the group draw in sports tournaments címmel.

Egy sportbajnokság csoportsorsolásával szemben felmerülő három legfontosabb követelmény a kiegyensúlyozottság, a transzparencia, és a véletlenszerűség. A kiegyensúlyozottság érdekében a csapatokat múltbeli teljesítményeik alapján kalapokba sorolják, és minden csoportba minden kalapból egy csapatot osztanak be, ami közel azonos erősségű csoportokat biztosít. A transzparencia a sorsolási módszer átláthatóságát, érthetőségét jelenti, a véletlenszerűség pedig azt, hogy az összes lehetséges csoportba osztásnak azonos valószínűséggel kell előfordulnia.

A sorsolás nehézsége korlátozó feltételek mellett

Számos sportverseny esetén a csoportsorsolás további korlátozó feltételek teljesülését is megköveteli. A cikkben tárgyalt példák közül a kosárlabda- és labdarúgó-világbajnokságon egy csoportba egy kontinensről legfeljebb egy válogatott kerülhet, kivéve Európát, ahonnan legalább egy, de legfeljebb kettő. Hasonlóan, a labdarúgó-világbajnokság európai selejtőzéjében az északi ország közül legfeljebb kettő osztható be egy csoportba, különben túl sok mérkőzést kellene kockázatos téli időjárási viszony között játszani.

Ezeket a korlátozó feltételeket az egy heurisztikus, könnyen érthető és ellenőrizhetőeljárás, az Ugró módszer biztosítja: az éppen kihúzott válogatottat az alfabetikus sorrendben első olyan csoportba helyezik, amivel a hátralevő csapatok még eloszthatók maradnak a fennmaradó helyekre a korlátozó feltételek sérülése nélkül. Az algoritmus mégsem olyan egyszerű, mint elsőre tűnhet. Ha például egy európai csapat helyét keressük a kosárlabda-világbajnokságon, nem elég csak azokat a csoportokat kizárni, melyekben már két európai csapat van – hiszen 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 azonban nem véletlenszerű eloszlású a lehetséges megoldások halmazán. Például a 2018-as labdarúgó-világbajnokságon Oroszország és Spanyolország pontosan 12,5%-os valószínűséggel kerülhetett egy csoportba (pontosan akkor, ha a második kalapból elsőként húzott csapat Spanyolország), az igazságos valószínűség viszont csak 9,2%. Vagyis e két csapat esetén az Ugró módszer torzítása 3,3 százalékpont.

Azaz, az Ugró algoritmus használata biztosítja a kiegyensúlyozottságot és a transzparenciát, azonban a véletlenszerűséget nem. Jelen tudásunk szerint a három követelmény egyszerre nem garantálható.

A kutatási kérdés

Az Ugró módszer számára komoly kihívást jelent egy olyan, a fentiekhez hasonló feltétel, mely szerint egy adott S halmazba tartozó csapatok közül legfeljebb kettő kerülhet egy csoportba. Ugyanis az algoritmus „rövidlátó”, nem képes felismerni, hogy az S halmazból két csapatot egy csoportba helyezve ez a csoport már elérhetetlenné válik az S halmazba tartozó többi, még nem kihúzott csapat számára. A lehetségesség természetesen megmarad, de a valószínűségek jelentősen torzulhatnak az egyenletes eloszlásból adódóhoz képest.

Mivel az algoritmus torzítása függ a kalapok sorrendjétől, a kutatás során azt vizsgáltuk, egy ilyen összetett korlátozó feltétel esetén a kalapok melyik sorrendje minimalizálja azt.

Eredmények

Elsőként egy egyszerű elméleti modellt vizsgáltunk, ahol az S halmazból legfeljebb két csapat helyezhető egy csoportba, a kalapok száma pedig három. Analitikus kiszámoltuk bármely két csapat párosítási valószínűségét és annak torzítását, ha az S halmaz két kalapból csak egy-egy csapatot tartalmaz. Numerikusan meghatároztuk ezeket az összes lehetséges konfiguráció mellett, ha a csoportok száma legfeljebb öt. Végül a 2018-as labdarúgó- és a 2019-es kosárlabda-világbajnokság esetén szimulációval választottuk ki a négy kalap 24 lehetséges sorrendje közül az optimálisat, illetve egy harmadik valós példa esetén összehasonlítottuk 11 húzási sorrend torzítását.

Elemzésünk alapján az optimális megoldás a kalapok az S halmazba tartozó csapatok száma alapján csökkenő sorrendbe helyezése, ami minimalizálja az Ugró mechanizmus torzítását. A 2018-as labdarúgó-világbajnokságon éppen ezt használták. A 2019-es kosárlabda-világbajnokságon a csoportsorsolás két független, négy-négy csoportos részből állt, az egyikben használt sorrend biztosította az egyenletes eloszlást, a másikban viszont az átlagos torzítás 1,8, a maximális 8,5 százalékpont volt, ami az optimális húzási sorrend használatával 0,3, illetve 1 százalékpontra csökkenthető.