Social Choice und Diskrete Optimierung

In dieser interdisziplinären Arbeitsgruppe werden die Entscheidungsmodelle der Kollektiventscheidungstheorie (social choice) und diskrete Optimierungsprobleme zusammengeführt. Dabei werden einerseits Fragen der Kollektiventscheidung auf diskrete Strukturen, wie z.B. Bäume und Pfade in Graphen, Teilmengenauswahl und Reihenfolgen, angewendet. Dies führt zu neuen Modellierungen, für die Komplexitäts- und Approximationsresultate im Sinne der theoretischen Informatik sowie Charakterisierungen der zu Grunde liegenden Lösungsverfahren von Interesse sind.
Andererseits werden bei klassischen diskreten Optimierungsproblemen, wie z.B. Minimum Spanning Tree, Travelling Salesman Problem, Knapsack Problem und Scheduling Problemen, die üblichen linearen Kosten- oder Profit-Zielfunktionen durch neue Zielfunktionen ersetzt, die aus der social choice entlehnt sind. Dadurch entstehen Modelle, welche die soziale Akzeptanz, ausgedrückt beispielsweise durch Fairness (z.B. in Form von Neidfreiheit), von Lösungen optimieren. Hier werden exakte und approximative Lösungsverfahren entwickelt und die dazugehörigen Existenzfragen bearbeitet.

Einen besonderen Schwerpunkt stellen Multi-Agenten Probleme mit spieltheoretischen Elementen dar. Dabei werden Entscheidungssituationen analysiert, die bei zentralisierter Betrachtung in der diskreten Optimierung wohlbekannt sind. Werden jedoch die diskreten Identitäten auf verschiedene Agenten aufgeteilt, entstehen durch das Verfolgen von individuellen Zielfunktionen gänzlich neue Klassen von Modellen.

Um Eigenschaften von Entscheidungsverfahren nicht nur theoretisch zu charakterisieren sondern auch deren konkrete Umsetzung durch Individuen mit geeignetem Datenmaterial untersuchen zu können, werden Simulationsstudien durchgeführt, die das Verhalten von homogenen und heterogenen Populationen unter verschiedenen Annahmen modellieren.

Verwendete Methoden:

Entwicklung und Analyse von Modellen, Worst-case Analyse von Laufzeiten und Lösungsqualität von (Approximations-)Algorithmen, Komplexitätstheorie (im Sinne der theoretischen Informatik), Monte Carlo
Simulation, Axiomatische Analyse.
Intensive internationale Kooperationen.

Beteiligte Institute:

Institut für Finanzwissenschaft und öffentliche Wirtschaft
Institut für Statistik und Operations Research

Beteiligte Forscher:

Andreas Darmann
Daniel Eckert
Hans Kellerer
Christian Klamler
Ulrich Pferschy
Joachim Schauer
mehrere PhD- und Master-Studierende

Einschlägige Drittmittelprojekte:

FWF-Projekt "Fairness and Voting in Discrete Optimization"
FWF-Projekt "Graph Problems with Knapsack Constraints"
EU-Project COST Action IC 0602 "Algorithmic Decision Theory"
Industrieprojekt "Algorithmen für die Marketing-Mix Optimierung"
FFG-Projekt "Integrated Runway Sequencer System"
EPSRC Projekt "Quadratic and Linear Knapsack Problems with Scheduling Applications"
Amadeus Projekt "Scheduling and production planning with unavailability periods for deterministic and imprecise data"