Design optimaler unparteiischer Mechanismen

• Antragsteller: Professor Dr. Max Klimm
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 431465007

Ein grundlegendes Problem des Computational Social Choice ist es, einzelne oder mehrer Agenten aus einer Menge von Agenten auszuwählen oder zu ordnen, wobei Nominierungen der Agenten untereinander beachtet werden. Dieses Prinzip findet sich in vielen Anwendungen, beispielsweise im Begutachtungsprozess des Peer Review wenn (wie bei Konferenzen der theoretischen Informatik nicht unüblich) die Menge der Gutachter und die Menge der Autoren nicht disjunkt sind, beim Peer Grading für Massen-Online-Kurse (MOOC), beim Abstimmen innerhalb von Komitees oder beim Leader-Election-Problem für Multi-Agenten-Systeme.Ein grundlegendes Problem in den oben genannten Anwendungen ist, dass einzelnen Agenten gewillt sein könnten, ihre wahren Meinungen über die Eignung der anderen Agenten zu verschweigen, um ihre eigenen Chancen ausgewählt zu werden zu verbessern. Diese Einsicht motiviert die Definition unparteiischer Mechanismen, die sich durch die Eigenschaft auszeichnen, dass die Wahrscheinlichkeit, dass ein bestimmter Agent ausgewählt wird, unabhängig von dessen Nominierungen anderer Agenten ist. In den letzten Jahren wurden im Bereich der theoretischen Informatik fundamentale Fortschritt beim Verständnis unparteiischer Mechanismen zur Auswahl eines einzelnen Agenten gemacht, die Forschung bezüglich komplizierter Mechanismen steckt jedoch noch in den Kinderschuhen. Diese Lücke soll im Rahmen des Projekts geschlossen werden. Vor dem Hintergrund der eingangs genannten Anwendungen, wäre insbesondere ein besseres Verständnis von unparteiischen Mechanismen, die mehrere Agenten auswählen wünschenswert. In diesem Projekt sollen dafür neue unparteiische Mechanismen entworfen und bezüglich ihres worst-case Approximationsfaktors analysiert werden. Dieser gibt das Verhältnis der gesamten Nominierungen der vom Mechanismus gewählten Agenten gegenüber dem theoretischen Maximum an. Motiviert durch die Anwendungen im Peer Review und Peer Grading soll zudem eine Erweiterung der bisher betrachteten Modelle analysiert werden, in der anstelle einfacher (binärer) Nominierungen Noten vergeben werden. Ein weitere interessante Erweiterungen stellt die unparteiische Ordnung von Agenten auf Basis von Bewertungen der Agenten untereinander dar. Dies ist unter anderem beim Peer Grading in MOOCs von Interesse, wenn die Agenten sich untereinander beurteilen und Noten auf der Basis is relativen Rankings in ihrer Peer Group bekommen.Neben der theoretischen Analyse sollen die entworfenen Algorithmen auch empirisch evaluiert werden sowie als Implementation öffentlich verfügbar gemacht werden.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Großbritannien
• Kooperationspartner: Dr. Felix Fischer