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. Wir beginnen die Untersuchung obiger Fairnessaspekte mit dem minimalen Spannbaum Problem. Dieses klassische Problem der Diskreten Optimierung bietet ein breites Spektrum an Anwendungen und erlaubt die Bestimmung der Optimallösung (bei klassischen numerischen Daten) in polynomieller Zeit. Danach wird dieser Ansatz auf andere Probleme der Diskreten Optimierung ausgeweitet, wie z.B. auf das kürzeste Wege Problem, Netzwerkdesign Probleme, Scheduling und Rucksack Probleme.

Viele Entscheidungen in ökonomischen, sozialen oder wirtschaftlichen Fragestellungen können nicht durch einen Entscheidungsträger allein getroffen werden, sondern bedürfen einer kollektiven Entscheidung, welche Meinungen und Präferenzen unterschiedlicher Individuen berücksichtigt. Naturgemäß wird man im Falle einer komplexen Entscheidungssituation kaum eine Lösung finden, mit der alle Beteiligten zufrieden sind; man möchte jedoch zumindest eine faire Behandlung aller abgegebenen Meinungen gewährleisten. Fairness ist somit ein zentrales Thema der Kollektiventscheidungstheorie. Ebenfalls ist die Anwendbarkeit diverser Lösungsmethoden ein wesentliches Kriterium. Hierbei wird vor allem die Berechnungskomplexität dieser Algorithmen, d.h. die Möglichkeit Lösungen auf einfachem Wege zu finden, zum zentralen Forschungskriterium. Die Entwicklung fairer und einfacher Aufteilungsregeln, sowie deren Charakterisierungen, in den Forschungsgebieten der Normativen und Algorithmischen Fair Division, zeigen die Relevanz dieses Themas. Im Projekt Fairness und Auswahl in der Diskreten Optimierung lag der Fokus vor allem auf dem Gebiet der Diskreten Optimierung, welche eine Vielzahl an Modellen, wie z.B. Netzwerke, kürzeste Wege, etc., zur Formulierung praktischer Situationen sozialer oder ökonomischer Art anbietet. Etliche solcher Probleme wurden in Bezug auf Fairness und Komplexität untersucht. Wesentliche Resultate wurden diesbezüglich bei der kollektiven Entscheidungsfindung erzielt wenn individuelle Präferenzen über diese Strukturen aggregiert wurden. Konkret wurde gezeigt wo die Trennlinie zwischen einfachen und schwierigen Problemen liegt. In vielen realen Situationen geht es jedoch nicht nur um die faire Entscheidung, sondern auch um die Auf bzw. Zuteilung von mit dieser Entscheidung verbundenen Kosten (z.B. beim gemeinsamen Bau eines Netzwerkes oder der Zahlung eines gemeinsamen Transports). Diverse Arbeiten des Projekts greifen dieses Thema auf und bieten cost sharing Algorithmen an, die auch auf ihre normativen Kriterien hin untersucht wurden. Abschließend wurde noch das Problem der Aufteilung unteilbarer Güter erforscht, welches z.B. in Scheidungssituation oder der Zuteilung von time slots auf einem Server auftritt. Hier ist auch der Informationsaspekt von gewisser Relevanz, d.h., inwieweit sind die Individuen in der Lage Information über ihre Präferenzen bekanntzugeben. Ausgehend von Rangordnungen über diese Güter wurden diverse Aufteilungsalgorithmen entwickelt und analysiert.