Turneringslösning

En turneringslösning är en funktion som mappar en orienterad komplett graf till en icke-tom delmängd av dess hörn . Det kan informellt ses som ett sätt att hitta de "bästa" alternativen bland alla alternativ som "tävlar" mot varandra i turneringen. Turneringslösningar härstammar från teorin om sociala val , men har också övervägts i sporttävlingar , spelteori , beslutsanalys med flera kriterier , biologi , webbsidarankning och problem med duellerande banditer .

Inom ramen för teorin om sociala val är turneringslösningar nära besläktade med Fishburns C1 sociala valfunktioner, och försöker på så sätt visa vilka de bästa kandidaterna är bland alla kandidater.

En turnering på 4 hörn: $A=\{1,2,3,4\}$ , $\succ =\{(1,2),(1,4),(2,4),$$(3,1),(3,2),(4,3)\}$

Definition

En turnering (graf) $T$ är en tupel $(A,\succ )$ där $A$ är en uppsättning hörn (kallas alternativ ) och $\succ$ är en konnex och asymmetrisk binär relation över hörnen. I sociala valteorin representerar den binära relationen typiskt den parvisa majoritetsjämförelsen mellan alternativ.

En turneringslösning är en funktion $f$ som mappar varje turnering $T=(A,\succ )$ till en icke-tom delmängd $f(T)$ av alternativen $A$ (kallad valuppsättningen ) och skiljer inte mellan isomorfa turneringar:

Om $h:A\rightarrow B$ är en grafisk isomorfism mellan två turneringar $T=(A,\succ )$ och ${\displaystyle {\widetilde {T}}=(B,{\widetilde {\succ }})} ,$ sedan $a\ i f(T)\vänsterhögerpil h(a)\in f({\widetilde {T}})$

Exempel

Vanliga exempel på turneringslösningar är:

• Copelands metod
• Toppcykel
• Slater set
• Tvåpartiskt set
• Otäckt set
• Banker inställda
• Minimalt täckningsset
• Jämviktsuppsättning för turneringen