Fairness und Auswahl in der diskreten Optimierung

Zahlreiche ökonomische, soziale oder politische Entscheidungen werden von Gruppen getroffen. Die Kollektiventscheidungstheorie (Social Choice Theory) adressiert diesen fundamentalen Aspekt, nämlich die Aggregation individueller Präferenzen von Gruppenmitgliedern in eine kollektive Entscheidung. Was macht eine kollektive Entscheidung zu einer guten, d.h. „fairen“, Entscheidung? Die Wichtigkeit dieser Frage geht zurück bis in die 1950er Jahre, und die Signifikanz der Forschung auf diesem Gebiet wurde durch Nobelpreise für Kenneth Arrow und Amartya Sen hervorgehoben.

Während der letzten 60 Jahre wurde die Kollektiventscheidungstheorie jedoch viel bedeutender als lediglich ein Analysewerkzeug für die Präferenzaggregation zu sein. Alltägliche Entscheidungsszenarien finden sich im elektronischen Handel, in dem die Interaktion von Menschen und automatisierten Kauf- und Verkaufsagenten analysiert wird. Anwendungen können auch in der multikriteriellen Analyse zum Aufbau von Internetsuchmaschinen gefunden werden. Darüber hinaus können Netzwerkstrukturen untersucht und unterstützende Gruppenentscheidungssysteme entwickelt werden. Schließlich können noch Fairness-Kriterien in unterschiedlichsten Entscheidungssituationen identifiziert und implementiert werden.
In diesem Projekt liegt der Fokus im Speziellen auf Situationen die mithilfe von Modellen der Diskreten Optimierung formuliert werden können. Dieser Zweig der angewandten Mathematik beinhaltet Variablen, die auf diskrete Werte beschränkt sind, z.B. also ganzzahlig oder binär sein müssen. Anwendungen reichen vom Netzwerkdesign, der Routen- bzw. Produktionsplanung bis hin zur Planung der Zuteilung von Arbeitskräften und der Transportplanung.
Unser interdisziplinäres Forschungsprojekt untersucht Gruppenentscheidungen und Fairness in solchen Modellen der Diskreten Optimierung. Ziel ist es, ein präziseres Verständnis des kollektiven Entscheidungsprozesses zu erreichen, der notwendig ist, um die neuen technologischen und sozialen Herausforderungen zu meistern, in denen Entscheidungs- bzw. Fairnessaspekte wichtig sind. Beginnend mit Präferenzen der einzelnen Individuen (oder Maschinen bzw. Kriterien) über eine Menge diskreter Objekte, soll eine „faire“ Gruppenentscheidung getroffen werden. Dies führt zu 2 wesentlichen Forschungsfragen:

1.) Wie können individuelle Präferenzen in richtiger bzw. fairer Weise ausgedrückt werden?
2.) Wie können diese individuellen Präferenzen in fairer Weise aggregiert werden?

Dies ist insofern wichtig, da zurzeit zwar eingeschränkt Literatur über Fairness bei allgemeinen Mengen von Objekten existiert, jedoch spezielle Lösungsstrukturen in der Diskreten Optimierung noch nicht in dieser Art abgehandelt wurden.
Eine offensichtliche und sehr relevante Erweiterung der bisherigen Fragen besteht in der Aufteilung der Kosten (oder Vorteile), die in obige Modelle integriert werden können. Diesbezüglich wird dieses Projekt einen weiteren zentralen Fairnesspunkt bearbeiten:

3.) Wie können die Kosten einer Lösung fair zwischen den teilnehmenden Agenten aufgeteilt werden?

Unsere Forschungsmethodik inkludiert die axiomatische Analyse der konzipierten Entscheidungsregeln bzw. Algorithmen. Wir betrachten die Komplexität (im Sinne des Rechenaufwandes) der Probleme (im Speziellen überprüfen wir auf NP-Schwere) und stellen die worst-case Laufzeiten der verwendeten Algorithmen fest. Im Falle von NP-Schwere, entwickeln wir Approximationsalgorithmen, analysieren deren Qualität im Hinblick auf Distanzmaße und leiten Approximationsgrenzen ab.

Ansprechpartner für dieses Projekt sind Prof. Klamler, Prof. Pferschy und Priv.-Doz. Darmann.