Fairness and voting in discrete optimization
Many decisions on economic, social or political issues are made by groups. Social Choice Theory addresses this fundamental issue, namely the aggregation of individual preferences of group members into a collective decision. What makes such a collective decision a good, i.e. “fair”, one? The importance of this question dates back to the 1950s, and the significance of research in this area has been underlined by the Nobel prizes for Kenneth Arrow and Amartya Sen.
Throughout the last sixty years however, Social Choice Theory has become far more important than just being an analysis tool for aggregating individual preferences. Real world decision scenarios can be found in electronic commerce analysing the interaction of human users and automated selling and buying agents. Applications can also be found as a sort of multicriteria analysis in the elaboration of internet search engines. Furthermore, social network structures can be investigated and group decision support frameworks developed. Finally, fairness criteria in many decision situations can be identified and implemented.
In this project we focus in particular on situations which can be formulated by the wide range of Discrete Optimization models. This branch of applied mathematics involves variables which are restricted to take only discrete values, e.g., to be integers or binary. Applications range from network design, routing and production planning to manpower scheduling and transportation.
Our interdisciplinary research project investigates group decision and fairness in such Discrete Optimization models. The goal is to arrive at a precise understanding of the types of collective decision making processes required to serve new technological but also social challenges, in which decision and fairness aspects are of importance. Starting with preferences expressed by single individuals (or machines, or criteria) on the set of all discrete objects, the goal is to provide a “fair” group outcome. This gives rise to two important research questions: 1.) How can individual preferences be expressed in a fair way? 2.) How can the individual preferences be fairly aggregated? This is important insofar that limited literature exists on the fairness of general sets of objects, however, particular solutions structures emerging in Discrete Optimization were never treated in this direction before.
A natural and highly relevant extension to the above questions involves the sharing of costs (or benefits) that can be introduced in the above models. Hence, the project will study a third central question of fairness: 3.) How can we divide the costs of a determined solution in a fair way among the participating agents?
Our research methodology includes an axiomatic analysis of the designed decision rules or algorithms. We consider the computational complexity of the problems (in particular, we check on NP-hardness), and establish the worst-case running time of the designed algorithms. In case of NP-hardness we develop approximation algorithms, analyse their quality in terms of distance measures and derive bounds of approximation.
If you want to learn more about this project, please get in touch with Christian Klamler, Ulrich Pferschy and Andreas Darmann.
