Турнирное решение

Турнирное решение — это функция , которая отображает полный ориентированный граф в непустое подмножество его вершин . Неформально это можно рассматривать как способ найти «лучшие» альтернативы среди всех альтернатив, которые «конкурируют» друг с другом в турнире. Решения для турниров берут начало в теории социального выбора . но также учитывались в спортивных соревнованиях , теории игр , многокритериальный анализ решений , биология , рейтинг веб-страницы , и решать проблемы бандитов .

В контексте теории социального выбора турнирные решения тесно связаны с функциями социального выбора C1 Фишберна. и таким образом стремиться показать, кто в каком-то смысле является наиболее сильным кандидатом.

Турнир на 4 вершины: $A=\{1,2,3,4\}$, $\succ =\{(1,2),(1,4),(2,4),$$(3,1),(3,2),(4,3)\}$

Определение

График турнира $T$ это кортеж $(A,\succ )$ где $A$ представляет собой набор вершин (называемых альтернативами ) и $\succ$ является связным и асимметричным бинарным отношением над вершинами. В теории социального выбора бинарное отношение обычно представляет собой попарное сравнение большинства альтернатив.

Турнирное решение — это функция $f$ который отображает каждый турнир $T=(A,\succ )$ к непустому подмножеству $f(T)$ альтернатив $A$ (называемый набором выбора ) и не различает изоморфные турниры:

Если $h:A\rightarrow B$ является изоморфизмом графов между двумя турнирами $T=(A,\succ )$ и ${\widetilde {T}}=(B,{\widetilde {\succ }})$, затем $a\in f(T)\Leftrightarrow h(a)\in f({\widetilde {T}})$

Примеры

Типичными примерами турнирных решений являются:

• Набор Коупленда
• Верхний цикл
• Слейтер набор
• Двухпартийный набор
• набор Ландау
• Набор банков
• Минимальный комплект покрытия
• Турнирное равновесие установлено