Neue Erkenntnisse: Minimalunterstützungen erklären Turnierergebnisse

Ein neues arXiv‑Veröffentlichung beleuchtet, wie man Turnierergebnisse mit minimalen, zertifizierten Erklärungen nachvollziehen kann. In Turnieren, die Paargewinnungen zwischen Kandidaten, Alternativen oder Teams modellieren, wird untersucht, welche Teilturniere ausreichen, um einen Gewinner eindeutig zu bestimmen – unabhängig davon, wie der Rest des Turniers ausgefüllt wird. Solche Teilturniere werden als minimale Unterstützungen bezeichnet und entsprechen einer abduktiven Erklärung der Frage: „Warum gewinnt der Kandidat?“

Die Studie konzentriert sich auf die gängigen Turniersysteme: Top‑Cycle, Uncovered Set, Copeland‑Regel, Borda‑Regel, Maximin‑Regel und das gewichtete Uncovered Set. Für jedes System wird die Größe des kleinsten minimalen Supports ermittelt. Darüber hinaus werden effiziente, polynomialzeitliche Algorithmen vorgestellt, die diese Supports berechnen – mit Ausnahme des gewichteten Uncovered Sets, für das das Problem NP‑schwer ist.

Abschließend wird gezeigt, wie minimale Unterstützungen kompakte, zertifizierte und intuitive Erklärungen liefern können. Diese Ergebnisse bieten einen wichtigen Beitrag zur erklärbaren KI, indem sie klare, nachvollziehbare Gründe für die Auswahl von Gewinnern in komplexen Turnierstrukturen liefern.