Fariness 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. Our investigations of the above fairness issues will start with the minimum spanning tree problem and the shortest path problem. These classical Discrete Optimization problems offer a wide range of applications and allow a polynomial-time determination of an optimal solution in the case of classical numerical data. Then, we extend our ideas and approaches to other Discrete Optimization problems such as network design problems, scheduling, the maximum flow problem and the knapsack problem.

Many decisions on economic, social or political issues cannot be made by one decision maker alone but require a decision making process which takes the opinions and preferences of many individuals (or voters) into account. Naturally, one will hardly find a result for a complex decision that makes everybody happy. However, one would like to guarantee at least a fair treatment of all submitted opinions. Hence, fairness is a central issue in Social Choice Theory. In addition, the applicability of aggregation and fair division rules is of relevance. In that respect, the focus lies on a rules computational complexity, i.e., whether solutions are easy or hard to find. The development of fair and quick allocation rules, as well as their axiomatic characterizations, in the research areas of normative and algorithmic fair division, underline the relevance of this topic. In the project Fairness and Voting in Discrete Optimization the focus was laid especially on the area of discrete optimization, which offers numerous models, such as network design, shortest paths, etc., for the application to real world decision scenarios in social and economic contexts. In that respect major results on collective decision making have been obtained in situations where individual preferences over this kind of structure are to be aggregated. In particular, the separation line between easy and hard problems has been determined. Many real world situations, however, are not only concerned with fair decisions, but also with the allocation of costs (e.g., in the construction of networks or the payment of a joint transport activity). Various papers in the process of the project deal with this issue and offer cost sharing algorithms, which also were investigated w.r.t. their normative criteria. Finally the project was investigating the allocation of indivisible objects, which occurs, e.g., in divorce negotiations or the assignment of time slots on a single server. In that respect the availability of information is also of certain relevance, i.e., in what way are individuals able to announce their preferences. Based on the information of rankings over the objects, various allocation procedures have been developed and analyzed.