Social Choice and Discrete Optimization

In this interdisciplinary working group, problems of decision making from social choice theory and discrete optimization are combined. On the one hand, questions from social choice theory are applied to discrete structures and problems such as trees and paths in graphs, scheduling and knapsack problems. This leads to a new sort of models for which approximation results as used in theoretical informatics and/or characterizations of the used solution methods are of interest.

On the other hand, in classical discrete optimization problems such as the minimum spanning tree problem, travelling salesman problem, knapsack problem or scheduling problem, the usual objective functions given by linear cost- and profit functions, are replaced by objective functions in the spirit of social choice theory. In that way models are developed, which optimize the social acceptance represented e.g. by fairness. Exact and approximate solution procedures are developed and existence results proved.

Solution methods are not only theoretically analyzed, but also validated for practical use with appropriate data. Therefore simulation studies are undertaken, that model the behavior of homogeneous and heterogeneous populations under different assumptions.

Used methods:

Developement and analysis of models, worst-case analysis of (approximation-)algorithms, complexity analysis, Monte Carlo simulation, axiomatic analysis.
Intensive international cooperations.

Departments involved:

Institute of Public Economics
Institute of Statistics and Operations Research

Researchers involved:

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

Research Grants:

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