Round-robin-turnering

Exempel på en round-robin-turnering med 10 deltagare

En round-robin-turnering (eller all-go-away-turnering ) är en tävling där varje tävlande möter varannan deltagare, vanligtvis i tur och ordning. En round-robin står i kontrast till en elimineringsturnering , där deltagare/lag slås ut efter ett visst antal förluster.

Terminologi

Termen round-robin kommer från det franska uttrycket ruban , som betyder " band ". Under en lång tidsperiod var termen korrumperad och idiomiserad till robin .

I ett enda round-robin- schema spelar varje deltagare varannan deltagare en gång. Om varje deltagare spelar alla andra två gånger kallas detta ofta för dubbel round-robin . Termen används sällan när alla deltagare spelar mot varandra mer än två gånger, och används aldrig när en deltagare spelar mot andra ett ojämnt antal gånger (som är fallet i nästan alla USA:s stora professionella idrottsligor – se AFL (1940 ) –41) och All-America Football Conference för undantag). I Storbritannien har en round-robin-turnering kallats en amerikansk turnering inom sporter som tennis eller biljard som vanligtvis har knockout- turneringar, även om detta numera sällan, om aldrig, görs. På italienska kallas det girone all'italiana (bokstavligen "grupp i italiensk stil"). På serbiska kallas det för Berger-systemet ( Бергеров систем , Bergerov sistem ), efter schackspelaren Johann Berger . I Brasilien kallas det sistema de pontos corridos ("löpande poängsystem"), och hänvisar till ackumuleringen av redovisade poäng som avgörande för varje deltagares slutliga prestation, när alla deltagare har spelat sina spel.

En round-robin- turnering med fyra spelare kallas ibland "quad" eller "foursome".

Använda sig av

I sporter med ett stort antal tävlingsmatcher per säsong är dubbla round-robins vanliga. De flesta förbundsfotbollsligor i världen är organiserade på dubbel round-robin-basis, där varje lag spelar mot alla andra i sin liga en gång hemma och en gång borta. Detta system används också i kvalificeringen för stora turneringar som fotbolls-VM och de kontinentala turneringarna (t.ex. UEFA European Championship , CONCACAF Gold Cup , AFC Asian Cup , CONMEBOL Copa América och CAF Cup of Nations ). Det finns också round-robin bridge- , schack- , utkast- , go- , ishockey- , curling- och Scrabble- turneringar. Världsmästerskapet i schack beslutade 2005 och 2007 om en dubbel round-robin-turnering med åtta spelare där varje spelare möter varannan spelare en gång som vit och en gång som svart.

I ett mer extremt exempel spelar KBO League of baseball en 16-faldig round robin, där vart och ett av de 10 lagen spelar mot varandra 16 gånger för totalt 144 matcher per lag.

LIDOM (Baseball Winter League i Dominikanska republiken) spelar en 18-faldig round robin som en semifinalturnering mellan fyra klassade lag.

Gruppturneringar rankas vanligtvis efter antal vunna och oavgjorda matcher, med någon av en mängd olika tiebreaker-kriterier.

Ofta genomförs pooletapper inom en bredare turnering på round-robin-basis. Exempel med enkel round-robin schemaläggning inkluderar FIFA World Cup , UEFA European Football Championship och UEFA Cup (2004–2009) i fotboll, Super Rugby ( rugbyunion ) på södra halvklotet under tidigare iterationer som Super 12 och Super 14 ( men inte i dess senare 15- och 18-lagsformat), Cricket World Cup tillsammans med Indian Premier League , stora Twenty-20 Cricket-turneringar och många American Football college-konferenser , såsom Big 12 (som för närvarande har 10 medlemmar) . Gruppfaserna i UEFA-klubbtävlingarna och Copa Libertadores tävlas som en dubbel round-robin, liksom de flesta basketligor utanför USA, inklusive den ordinarie säsongen av EuroLeague (liksom dess tidigare Top 16-fas); United Football League har använt en dubbel round-robin för både säsongerna 2009 och 2010 .

Säsongsavslutande tennisturneringar använder också ett round robin-format före semi på scener.

Utvärdering

Fördelar med formatet

Mästaren i en round-robin-turnering är den tävlande som vinner flest matcher, förutom när oavgjorda drag är möjliga.

I teorin är en round-robin-turnering det mest rättvisa sättet att avgöra mästaren bland ett känt och fast antal tävlande. Varje tävlande, oavsett om det är spelare eller lag, har lika chanser mot alla andra motståndare eftersom det inte finns någon tidigare seedning av tävlande som utesluter en match mellan ett givet par. Inslaget av tur ses vara reducerat jämfört med ett knockout-system eftersom en eller två dåliga prestationer inte behöver förstöra en konkurrents chans till slutseger. Slutliga register över deltagare är mer korrekta, i den meningen att de representerar resultaten över en längre period mot samma motstånd.

Systemet är också bättre för att rangordna alla deltagare, inte bara för att avgöra vinnaren. Detta är användbart för att bestämma den slutliga rangordningen för alla tävlande, från starkaste till svagaste, i syfte att kvalificera sig för en annan etapp eller tävling samt för prispengar.

Inom lagsport betraktas (round-robin) major league-mästarna i allmänhet som det "bästa" laget i landet, snarare än ( eliminerings- ) cupvinnarna.

Dessutom, i turneringar som FIFA eller ICC World Cups, skyddar en första omgångsfas som består av ett antal mini round robins mellan grupper om 4 lag mot möjligheten att ett lag reser möjligen tusentals miles bara för att elimineras efter bara en dålig prestanda i ett rakt knockout-system. Det översta, två eller ibland tre lagen i dessa grupper fortsätter sedan till ett rakt utslagssteg under resten av turneringen.

I dödscirkeln (se nedan) är det möjligt att ingen mästare kommer ut från en round-robin-turnering, även om det inte blir oavgjort. De flesta sporter har dock tie-breaker-system som löser detta.

Nackdelar med formatet

Round-robins kan lida av att vara för långa jämfört med andra turneringstyper, och med senare schemalagda spel som potentiellt inte har någon väsentlig betydelse. De kan också kräva tiebreaking-procedurer.

I schweiziska systemturneringar försöker man kombinera delar av round-robin- och elimineringsformaten för att ge en värdig mästare med färre rundor än round-robin, samtidigt som oavgjorda och förluster tillåts.

Turneringslängd

Den största nackdelen med en round robin-turnering är den tid som krävs för att slutföra den. Till skillnad från en knockout-turnering där hälften av deltagarna elimineras efter varje omgång, kräver en round robin en omgång mindre än antalet deltagare. Till exempel kan en turnering med 16 lag genomföras på bara 4 omgångar (dvs. 15 matcher) i ett knockout- format ( enkel eliminering ); en dubbel elimineringsturnering kräver 30 (eller 31) matcher, men en round-robin skulle kräva 15 omgångar (dvs. 120 matcher) för att slutföra om varje tävlande möter varandra en gång.

Andra frågor härrör från skillnaden mellan den teoretiska rättvisan i round robin-formatet och praktiken i en verklig händelse. Eftersom vinnaren gradvis uppnås genom flera spelomgångar, tvingas lag som presterar dåligt, som kan ha blivit snabbt eliminerade från titelstriden, spela ut sina återstående matcher. Således spelas spel sent i konkurrensen mellan konkurrenter utan återstående chans att lyckas. Dessutom kommer vissa senare matcher att para ihop en konkurrent som har något kvar att spela för mot en annan som inte har det. Det kan också vara möjligt för en konkurrent att spela de starkaste motståndarna i en round robin i snabb följd medan andra spelar dem periodvis med svagare motstånd. Denna asymmetri gör att det inte är helt rättvist att spela samma motståndare.

Det finns heller ingen schemalagd finalmatch om inte (av en tillfällighet) två tävlande möts i den sista matchen i turneringen, med resultatet av den matchen som avgör mästerskapet. Ett anmärkningsvärt exempel på en sådan händelse var 1950 FIFA World Cup -matchen mellan Uruguay och Brasilien .

Kvalificerade lag

Ytterligare problem uppstår när en round-robin används som en kvalificeringsomgång inom en större turnering. En tävlande som redan är kvalificerad för nästa steg före sin sista match kanske antingen inte försöker hårt (för att spara resurser för nästa fas) eller till och med avsiktligt förlora (om den planerade motståndaren i nästa fas för ett lägre kvalificerat spel uppfattas vara lättare än för en högre placerad).

Fyra par i dubbelbadminton för damer 2012, efter att ha kvalificerat sig till nästa omgång, kastades ut från tävlingen för att ha försökt förlora i round robin-stadiet för att undvika landsmän och bättre rankade motståndare. Round robin-steget vid OS var en ny introduktion, och dessa potentiella problem var lätt kända före turneringen; ändringar gjordes inför nästa OS för att förhindra en upprepning av dessa händelser.

Dödens cirkel

En annan nackdel, särskilt i mindre round-robins, är "dödens cirkel", där lag inte kan separeras på ett head-to-head rekord. I en round-robin med tre lag, där A besegrar B, B besegrar C och C besegrar A, kommer alla tre tävlande att ha ett rekord på en vinst och en förlust, och en tiebreaker kommer att behöva användas för att skilja lagen åt. Detta hände välkänt under FIFA World Cup Group E 1994, där alla fyra lagen slutade med en vinst, en oavgjord och en förlust. Detta fenomen är analogt med Condorcet-paradoxen i röstteorin.

Schemaläggningsalgoritm

Om $n$ är antalet tävlande, kräver en ren round robin-turnering ${\begin{matrix}{\frac {n}{2}}\end{matrix} }(n-1)$ spel. Om $n$ är jämnt, då i var och en av $(n-1)$ omgångar, ${\displaystyle {\begin{matrix}{\frac {n}{2} }\end{matrix}}}-$ spel kan köras samtidigt, förutsatt att det finns tillräckliga resurser (t.ex. banor för en tennisturnering ). Om $n$ är udda kommer det att finnas $n$ omgångar, var och en med ${\begin{matrix}{\frac {n-1}{2}}\end {matrix}}$ spel, och en tävlande har inget spel i den omgången.

Cirkelmetod

Cirkelmetoden är standardalgoritmen för att skapa ett schema för en round-robin-turnering . Alla tävlande tilldelas nummer och paras sedan ihop i den första omgången:

Omgång 1. (1 spel 14, 2 spel 13, ...)

1	2	3	4	5	6	7
14	13	12	11	10	9	8

Därefter är en av konkurrenterna i den första eller sista kolumnen i tabellen fixerad (nummer ett i detta exempel) och de andra roteras medurs en position

Omgång 2. (1 spel 13, 14 spel 12, ...)

1	14	2	3	4	5	6
13	12	11	10	9	8	7

Omgång 3. (1 spel 12, 13 spel 11, ...)

1	13	14	2	3	4	5
12	11	10	9	8	7	6

Detta upprepas tills du nästan hamnar tillbaka i utgångspositionen:

Omgång 13. (1 spel 2, 3 spel 14, ...)

1	3	4	5	6	7	8
2	14	13	12	11	10	9

För att se att - med ett jämnt antal $n$ av konkurrenter - den här algoritmen realiserar alla möjliga kombinationer av dem (motsvarande att alla realiserade par är parvis olika), argumenterar vi enligt följande.

För det första realiserar algoritmen uppenbarligen varje par av konkurrenter om en av dem är lika med $1$ (den icke-rörliga konkurrenten).

Därefter, för par av icke- $1$ -tävlande, låt deras avstånd vara antalet $k<{\frac {n}{2}}$ gånger rotationen måste utföras för att en tävlande ska komma till den position den andra hade.

I exemplet som ges ( $n=14$ ) har ${\displaystyle 2} avstånd$$1$ till $3$ och till $14$ och det har avstånd $6$ till $8$ och till $9$ .

I en runda kan en position som inte är längst till vänster (exklusive $1$ ) endast tas av konkurrenter på en fast distans. I omgång $1$ i exemplet, i andra positionen spelar konkurrent $2$ mot $13$ , deras avstånd är $2$ . I omgång $2$ hålls denna position av tävlande $14$ och $12$ , som också har distans $2$ osv. På samma sätt, nästa position ( ${\ displaystyle 3}$ mot $12$ i omgång $1$ , $2$ mot $11$ i omgång $2$ , etc.) kan bara hålla distans- $4$ konkurrenter.

För varje $k<{\frac {n}{2}}$ finns det exakt $n-1$ par av avstånd $k$ . Det finns $n-1$ omgångar och de realiserar alla ett distans- $k$ -par på samma position. Det är klart att dessa par är parvis olika. Slutsatsen är att varje distans- $k$ -par realiseras.

Detta gäller för varje $k$ , därför realiseras varje par.

Om det finns ett udda antal tävlande kan en dummy-konkurrent läggas till, vars schemalagda motståndare i en given omgång inte spelar och har ett bye . Schemat kan därför beräknas som om dummyn vore en vanlig spelare, antingen fast eller roterande.

Istället för att rotera en position kommer valfritt tal relativt primtal till $(n-1)$ att generera ett komplett schema. Den övre och nedre raden kan indikera hemma/borta i sport, vit/svart i schack , etc.; för att säkerställa rättvisa måste detta växla mellan omgångarna eftersom deltagare 1 alltid är på första raden. Om t.ex. tävlande 3 och 8 inte kunde uppfylla sin match i den tredje omgången, skulle det behöva läggas om utanför de andra omgångarna, eftersom båda konkurrenterna redan skulle möta andra motståndare i dessa omgångar. Mer komplexa schemaläggningsbegränsningar kan kräva mer komplexa algoritmer. Detta schema tillämpas i schack- och utkastturneringar i snabbspel, där spelarna fysiskt rör sig runt ett bord. I Frankrike kallas detta Carousel -Berger-systemet (Système Rutch-Berger).

Schemat kan även användas för "asynkrona" round-robin-turneringar där alla spel äger rum vid olika tidpunkter (till exempel eftersom det bara finns en plats). Spelen spelas från vänster till höger i varje omgång, och från den första omgången till den sista. När antalet tävlande är jämnt, fungerar detta schema bra med avseende på kvalitet och rättvisa mått såsom mängden vila mellan spelen. Å andra sidan, när antalet konkurrenter är udda presterar det inte så bra och ett annat schema är överlägset med avseende på dessa mått.

Berger bord

Alternativt används Berger-bord, uppkallade efter den österrikiske schackmästaren Johann Berger , flitigt i planeringen av turneringar. Berger publicerade parningstabellerna i sina två Schach-Jahrbücher (Schackannaler), med vederbörlig hänvisning till dess uppfinnare Richard Schurig.

Omgång 1	1 – 14	2 – 13	3 – 12	4 – 11	5 – 10	6 – 9	7 – 8
Runda 2	14 – 8	9 – 7	10 – 6	11 – 5	12 – 4	13 – 3	1 – 2
Omgång 3	2 – 14	3 – 1	4-13	5 – 12	6 – 11	7 – 10	8 – 9
...	...
Omgång 13	7 – 14	8 – 6	9 – 5	10 – 4	11 – 3	12 – 2	13 – 1

Detta utgör ett schema där spelare 14 har en fast position och alla andra spelare roteras moturs ${\frac {n}{2}}$ positioner. Detta schema genereras enkelt manuellt. För att konstruera nästa omgång går den sista spelaren, nummer 8 i första omgången, till bordets huvud, följt av spelare 9 mot spelare 7, spelare 10 mot 6, tills spelare 1 mot spelare 2. Aritmetiskt motsvarar detta lägga till ${\frac {n}{2}}$ till föregående rad, med undantag för spelare $n$ . När resultatet av additionen är större än ${\displaystyle (n-1)} ,$ subtrahera sedan $(n-1)$ från summan.

Detta schema kan också representeras som ett (n-1, n-1) bord, som uttrycker en runda där spelare möter varandra. Till exempel spelar spelare 7 mot spelare 11 i omgång 4. Om en spelare möter sig själv visar detta ett bye eller ett spel mot spelare n. Alla spel i en omgång utgör en diagonal i tabellen.

Diagonalt schema × 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 2 3 4 5 6 7 8 9 10 11 12 13 2 1 2 3 4 5 6 7 8 9 10 11 12 13 3 1 2 3 4 5 6 7 8 9 10 11 12 13 4 1 2 3 4 5 6 7 8 9 10 11 12 13 5 1 2 3 4 5 6 7 8 9 10 11 12 13 6 1 2 3 4 5 6 7 8 9 10 11 12 13 7 1 2 3 4 5 6 7 8 9 10 11 12 13 8 1 2 3 4 5 6 7 8 9 10 11 12 13 9 1 2 3 4 5 6 7 8 9 10 11 12 13 10 1 2 3 4 5 6 7 8 9 10 11 12 13 11 1 2 3 4 5 6 7 8 9 10 11 12 13 12 1 2 3 4 5 6 7 8 9 10 11 12 13 13 1 2 3 4 5 6 7 8 9 10 11 12 13

Round Robin-schema × 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 2 3 4 5 6 7 8 9 10 11 12 13 2 2 3 4 5 6 7 8 9 10 11 12 13 1 3 3 4 5 6 7 8 9 10 11 12 13 1 2 4 4 5 6 7 8 9 10 11 12 13 1 2 3 5 5 6 7 8 9 10 11 12 13 1 2 3 4 6 6 7 8 9 10 11 12 13 1 2 3 4 5 7 7 8 9 10 11 12 13 1 2 3 4 5 6 8 8 9 10 11 12 13 1 2 3 4 5 6 7 9 9 10 11 12 13 1 2 3 4 5 6 7 8 10 10 11 12 13 1 2 3 4 5 6 7 8 9 11 11 12 13 1 2 3 4 5 6 7 8 9 10 12 12 13 1 2 3 4 5 6 7 8 9 10 11 13 13 1 2 3 4 5 6 7 8 9 10 11 12

Ovanstående schema kan också representeras av en graf, som visas nedan:

Round Robin Schema Span Diagram

Både grafen och schemat rapporterades av Édouard Lucas som ett rekreationsmatematikpussel. Lucas, som beskriver metoden som enkel och genialisk , tillskriver lösningen till Felix Walecki, lärare vid Lycée Condorcet . Lucas inkluderade också en alternativ lösning med hjälp av ett glidande pussel .

Originalkonstruktion av parbord av Richard Schurig (1886)

För ett jämnt tal $n$ eller ett udda antal $n-1$ av konkurrenter bygger Schurig en tabell med $n/2$ vertikala rader och ${\ displaystil n-1}$ horisontella rader. Sedan fyller han i det från det övre vänstra hörnet genom att upprepa talföljden från 1 upp till $n-1$ . Här är en exempeltabell för 7 eller 8 tävlande:

Omgång 1	1	2	3	4
Runda 2	5	6	7	1
Omgång 3	2	3	4	5
Omgång 4	6	7	1	2
Omgång 5	3	4	5	6
Omgång 6	7	1	2	3
Omgång 7	4	5	6	7

Sedan konstrueras ett andra bord för att få motståndarna. Varje horisontell rad $x$ är fylld med samma siffror som rad $x+1$ i föregående tabell (den sista raden är fylld med siffror från den första raden i den ursprungliga tabellen), men i omvänd ordning (från höger till vänster).

Omgång 1	– 1	– 7	– 6	– 5
Runda 2	– 5	– 4	– 3	– 2
Omgång 3	– 2	– 1	– 7	– 6
Omgång 4	– 6	– 5	– 4	– 3
Omgång 5	– 3	– 2	– 1	– 7
Omgång 6	– 7	– 6	– 5	– 4
Omgång 7	– 4	– 3	– 2	– 1

Genom att slå samman ovanstående tabeller kommer vi fram till:

Omgång 1	1 – 1	2 – 7	3 – 6	4 – 5
Runda 2	5 – 5	6 – 4	7 – 3	1 – 2
Omgång 3	2 – 2	3 – 1	4 – 7	5 – 6
Omgång 4	6 – 6	7 – 5	1 – 4	2 – 3
Omgång 5	3 – 3	4 – 2	5 – 1	6 – 7
Omgång 6	7 – 7	1 – 6	2 – 5	3 – 4
Omgång 7	4 – 4	5 – 3	6 – 2	7 – 1

Sedan uppdateras den första kolumnen: om antalet konkurrenter är jämnt, ersätts spelare nummer n {\displaystyle n} omväxlande med första och andra positionen, medan om antalet konkurrenter är udda används ett bye $.$

Parningstabellerna publicerades som en bilaga angående arrangemangen för arrangemanget av masterturneringar. Schurig gav inte något bevis eller en motivering för sin algoritm. För mer historisk information, se Ahrens.

Se även

• Rangordningssystem för gruppturneringar , inklusive information om oavgjort system
• Kombinatorisk design , en balanserad turneringsdesign av ordning n (en BTD( n ) )
• Turnering (grafteori) , matematisk modell av en round-robin-turnering
• Andra turneringssystem:
  • Swiss system tournament
    • McMahon system tournament , en variant av det schweiziska systemet som innehåller rankningar före turneringen för att förhindra tidiga skeva parningar
  • Single-elimineringsturnering
    • Shaughnessy playoff system , en typ av single-elimineringsturnering med fyra lag
  • Dubbelelimineringsturnering
  • McIntyre-system , en serie turneringsformat som kombinerar funktioner i enkel- och dubbelelimineringsturneringar
• Bro:
  • Dubbla brorörelser
• Schack:
  • Lista över round-robin schackturneringar
  • Scheveningen-systemet , där varje medlem i ett lag spelar mot varje medlem i den andra
• Röstning:
  • Condorcet metod
  • Condorcet kriterium

externa länkar

• Round Robin Tournament Scheduling länk till scheman (balanserad, cyklisk, first-fit, whist).
• Round Robin System-tabeller (Poängsättning - Program)
• Gratis utskrivbara Round Robin-fästen