Ranking Probleme bei unvollständiger Information
Final Report Abstract
Bei Ranking Problemen gibt es Kandidaten, die von Wählern bewertet und eine Reihenfolge gebracht werden. Wenn mehrere Wähler beteiligt sind, kommt es zu unterschiedlichen Bewertungen einzelner Kandidaten, x vor y und an anderer Stelle y vor x. Es stellen sich zwei vorrangige Aufgaben: die Berechung des Unterschieds zwischen Bewertungen - das so genannte Distanzproblem - und die Berechung eines optimalen Kompromisses - das Ranking Problem. Bei vollständiger Information wird jeder Kandidat bewertet. Jedes Ranking ist dann eine totale Ordnung oder eine Permutation der Kandidaten. Der Unterschied bemisst sich in den unterschiedlichen Bewertungen, hier x vor y und dort y vor x. Das ist die Kendall-tau Distanz. Bei totalen Ordnungen, also bei vollständiger Information, lässt sich das Distanzproblem effizient in O(n logn) lösen, aber das Ranking Problem ist schon für vier Wähler NP-hart. In vielen Fällen kann oder will ein Wähler nicht alle Kandidaten bewerten. Sein Ranking ist unvollständig und nur eine partielle Ordnung. Diese Unvollständigkeit an Information hat gravierende Auswirkungen auf die Komplexität der Distanz und Ranking Probleme. Es konnte gezeigt werden, dass diese Probleme schon für eine totale und eine partielle Ordnung NP-hart sind. Aber, die Probleme lassen sich mit konstanter Güte approximieren und sind Fixed Parameter Tractable (FPT). Dies wurde für die Kendall-tau Distanz, die Spearman Footrule (oder L1-Norm) Distanz und 8 weitere Metriken auf Permutationen bewiesen. Es gibt zwei Gründe, warum ein Wähler Kandidaten nicht reihen kann. Die Kandidaten sind für ihn gleichwertig und es ist ihm egal, in welcher Reihenfolge diese Kandidaten erscheinen oder sie Kandidaten sind unvergleichbar, wie Äpfel und Birnen. Dieser Unterschied wurde in früheren Arbeiten zum Ranking ignoriert und Unvergleichbarkeit hatte zur Folge, dass man nicht mehr unter die Top-k eingereiht wurde. Wir konnten beweisen, dass dieser Unterschied essentiell ist. Reihungen mit „ist mir egal“ sind Bucket Ordnungen oder eine Kette aus Anti-Ketten in der Ordnungstheorie. Komplementär dazu sind Chain Sum Ordnungen oder eine Anti-Kette aus Ketten. Es hat sich herausgestellt, das die Grenze zwischen polynomial lösbar und NP-hart genau dazwischen verläuft: das Distanzproblem bei Bucket Ordnungen ist effizient in O(n logn) lösbar und für Chain Sum Ordnungen ist es NP-hart, sogar wenn die Ketten nur die Länge 12 haben. Letzteres hat zur Folge, dass Rankings aus einer Weltrangliste (nach Punkten oder Preisgeldern) und aus einem Turnier (der Verlierer scheidet aus) algorithmisch nur schwer vergleichbar sind, d.h. das Distanzproblem ist NP-hart. Das Problem ist FPT und damit effizient lösbar, wenn die Top-Spieler oder Mannschaften in die Endrunden einziehen und damit der Unterschied zwischen der Weltrangliste und dem Turnierausgang nicht zu groß ist.
Publications
- Comparing and Aggregating Partial Orders with Kendall tau Distances. Discrete Math., Alg. and Appl. 5(2) (2013)
F.J. Brandenburg, A. Gleißner, A. Hofmeier
- On Maximum Rank Aggregation Problems. Proc. IWOCA 2013, LNCS 8288 (2013), 14-27
C. Bachmaier, F.J. Brandenburg, A. Gleißner, A. Hofmeier
- The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders. J. Comb. Optim. 26(2): 310-332 (2013)
F.J. Brandenburg, A. Gleißner, A. Hofmeier
- On the hardness of maximum rank aggregation problems Journal of Discrete Algorithms. Online Oktober 2014
C. Bachmaier, F.J. Brandenburg, A. Gleißner, A. Hofmeier
(See online at https://doi.org/10.1016/j.jda.2014.10.002) - Ranking Chain Sum Orders. Theoretical Computer Science, Volume 636, 11 July 2016, Pages 66-76
F.J. Brandenburg, A. Gleißner
(See online at https://doi.org/10.1016/j.tcs.2016.05.026)
