Řešení turnaje - Tournament solution

A turnajové řešení je funkce který mapuje orientovaný kompletní graf na neprázdné podmnožina jeho vrcholy. Lze jej neformálně považovat za způsob, jak najít „nejlepší“ alternativy ze všech alternativ, které v turnaji proti sobě „soutěží“. Turnajová řešení pocházejí z teorie sociální volby,^[1]^[2]^[3]^[4] ale byly také zvažovány v sportovní soutěž, herní teorie,^[5] multikriteriální rozhodovací analýza, biologie,^[6]^[7] hodnocení webových stránek,^[8] a problémy s banditskými souboji.^[9]

V kontextu teorie sociální volby jsou turnajová řešení úzce spjata s funkcemi Fishburnovy sociální volby C1^[10], a snažit se tak ukázat, kdo je mezi všemi kandidáty nejlepšími kandidáty.

Turnaj na 4 vrcholech:

{ displaystyle A = {1,2,3,4 }}

,

{ displaystyle succ = {(1,2), (1,4), (2,4),}

{ displaystyle (3,1), (3,2), (4,3) }}

Definice

A turnaj (graf) ${ displaystyle T}$ je n-tice ${ displaystyle (A, succ)}$ kde ${ displaystyle A}$ je sada vrcholů (tzv alternativy) a ${ displaystyle succ}$ je Connex a asymetrické binární relace přes vrcholy. V teorii sociální volby binární vztah obvykle představuje párové většinové srovnání mezi alternativami.

Turnajové řešení je a funkce ${ displaystyle f}$ který mapuje každý turnaj ${ displaystyle T = (A, succ)}$ do neprázdné podmnožiny ${ displaystyle f (T)}$ alternativ ${ displaystyle A}$ (volal výběrová sada^[2]) a nerozlišuje mezi izomorfními turnaji:

Li

{ displaystyle h: A rightarrow B}

je izomorfismus grafu mezi dvěma turnaji

{ displaystyle T = (A, succ)}

a

{ displaystyle { widetilde {T}} = (B, { widetilde { succ}})}

, pak

{ displaystyle a in f (T) Leftrightarrow h (a) in f ({ widetilde {T}})}

Příklady

Běžné příklady turnajových řešení jsou:^[1]^[2]

Copelandova metoda
Nejlepší cyklus
Slater set
Bipartisan set
Odkrytá sada
Banky sada
Minimální krycí sada
Turnajová rovnovážná sada

Reference

^ ^A ^b Laslier J.-F. (1997). Řešení turnajů a hlasování většiny. Springer Verlag.
^ ^A ^b ^C Felix Brandt; Markus Brill; Paul Harrenstein (28. dubna 2016). „Kapitola 3: Turnajová řešení“ (PDF). Ve Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Příručka výpočetní sociální volby. Cambridge University Press. ISBN 978-1-316-48975-8.
^ Brandt, F. (2009). Turnajová řešení - rozšíření maximality a jejich aplikace při rozhodování. Habilitační práce, Fakulta matematiky, informatiky a statistiky, Mnichovská univerzita.
^ Scott Moser. „Kapitola 6: Pravidlo většiny a turnajová řešení“. V J. C. Heckelman; N. R. Miller (eds.). Příručka sociální volby a hlasování. Edgar Elgar.
^ Fisher, D. C .; Ryan, J. (1995). "Turnajové hry a pozitivní turnaje". Journal of Graph Theory. 19 (2): 217–236. doi:10,1002 / jgt.3190190208.
^ Allesina, S .; Levine, J. M. (2011). „Konkurenční síťová teorie rozmanitosti druhů“. Sborník Národní akademie věd. 108 (14): 5638–5642. doi:10.1073 / pnas.1014428108.
^ Landau, H. G. (1951). „O vztazích dominance a struktuře zvířecích společností: I. Vliv inherentních charakteristik“. Bulletin of Mathematical Biofhysics. 13 (1): 1–19. doi:10.1007 / bf02478336.
^ Felix Brandt; Felix Fischer (2007). „PageRank jako slabé řešení turnaje“ (PDF). Přednášky v informatice (LNCS). 3. mezinárodní seminář o internetu a síťové ekonomice (WINE). 4858. San Diego, USA: Springer. 300–305.
^ Siddartha Ramamohan; Arun Rajkumar; Shivani Agarwal (2016). Soubojoví bandité: Kromě vítězů Condorcetu až po řešení obecných turnajů (PDF). 29. konference o systémech zpracování neurálních informací (NIPS 2016). Barcelona, Španělsko.
^ Fishburn, P. C. (1977). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030.

[:0-1] A ^b Laslier J.-F. (1997). Řešení turnajů a hlasování většiny. Springer Verlag.

[BrandtConitzer2016-2] A ^b ^C Felix Brandt; Markus Brill; Paul Harrenstein (28. dubna 2016). „Kapitola 3: Turnajová řešení“ (PDF). Ve Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Příručka výpočetní sociální volby. Cambridge University Press. ISBN 978-1-316-48975-8.

[3] Brandt, F. (2009). Turnajová řešení - rozšíření maximality a jejich aplikace při rozhodování. Habilitační práce, Fakulta matematiky, informatiky a statistiky, Mnichovská univerzita.

[4] Scott Moser. „Kapitola 6: Pravidlo většiny a turnajová řešení“. V J. C. Heckelman; N. R. Miller (eds.). Příručka sociální volby a hlasování. Edgar Elgar.

[5] Fisher, D. C .; Ryan, J. (1995). "Turnajové hry a pozitivní turnaje". Journal of Graph Theory. 19 (2): 217–236. doi:10,1002 / jgt.3190190208.

[6] Allesina, S .; Levine, J. M. (2011). „Konkurenční síťová teorie rozmanitosti druhů“. Sborník Národní akademie věd. 108 (14): 5638–5642. doi:10.1073 / pnas.1014428108.

[7] Landau, H. G. (1951). „O vztazích dominance a struktuře zvířecích společností: I. Vliv inherentních charakteristik“. Bulletin of Mathematical Biofhysics. 13 (1): 1–19. doi:10.1007 / bf02478336.

[8] Felix Brandt; Felix Fischer (2007). „PageRank jako slabé řešení turnaje“ (PDF). Přednášky v informatice (LNCS). 3. mezinárodní seminář o internetu a síťové ekonomice (WINE). 4858. San Diego, USA: Springer. 300–305.

[9] Siddartha Ramamohan; Arun Rajkumar; Shivani Agarwal (2016). Soubojoví bandité: Kromě vítězů Condorcetu až po řešení obecných turnajů (PDF). 29. konference o systémech zpracování neurálních informací (NIPS 2016). Barcelona, Španělsko.

[10] Fishburn, P. C. (1977). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]