Loading…
Aufgrund des Skaleneffekts (economy of scale), sollte ein einzelner Nutzer eine Kooperation eingehen, um Kosten zu sparen. Eine Herausforderung für die Mitglieder einer Kooperation ist, dass sich alle einigen müssen, wie viel jeder bezahlen muss. Ansonsten kann die Zusammenarbeit nicht realisiert werden. Diese Dissertation befasst sich mit der fairen Verteilung der gemeinsamen Kosten einer Gruppe auf ihre Mitglieder. Die Arbeit verbindet kooperative Spieltheorie und state-of-the-art Algorithmen aus der linearen und ganzzahligen Optimierung, um faire Allokationen zu definieren und sie numerisch für große reale Anwendungen zu berechnen. Unsere Ansätze übertreffen traditionelle Kostenverteilungsmethoden im Sinne der Fairness und der Nutzerzufriedenheit. Kooperative Spieltheorie analysiert die möglichen Gruppierungen von Einzelnen, um Koalitionen zu bilden. Es bietet mathematische Werkzeuge um faire Preise in dem Sinne zu bestimmen, dass der Zusammenbruch der großen Koalition verhindert und die Stabilität erhöht wird. Bei der aktuellen Definition des Kostenallokationsspiels werden weder mögliche Koalitionen von Spielern beschränkt noch Bedingungen an die Preise gestellt, wie es häufig in der realen Anwendungen erforderlich ist. Unsere Verallgemeinerung bringt das Kostenallokationsspiel-Modell einen Schritt näher an die Praxis. Basierend auf unserer Definition, präsentieren und diskutieren wir in dieser Arbeit verschiedene mathematische Konzepte, die Fairness modellieren. Diese These behandelt auch die Frage, ob eine "beste Kostenallokation" existiert, die Menschen präferieren. Es ist bekannt, dass multikriterielle Optimierungsprobleme oftmals keine optimale Lösung besitzen, die gleichzeitig jede Zielfunktion optimiert. Es gibt kein "perfektes" Wahlverfahren, welches die fünf grundlegenden "social choice procedures" aus dem Buch "Mathematics and Politics. Strategy, Voting, Power and Proof" von Taylor et al. erfüllt. Gleiches gilt für das Kostenallokationsproblem. Es gibt keine Kostenallokation, die jede unserer gewünschten Eigenschaften erfüllt. Unsere Spiel-theoretischen Konzepte versuchen den Grad der axiomatischen Verletzung zu minimieren und erhalten gleichzeitig die Gültigkeit einiger wichtiger Eigenschaften. Aus Sicht der Komplexität ist es NP-schwer, die Allokationen, die auf den Spiel-theoretischen Konzepten basieren, zu berechnen. Die größte Herausforderung ist, dass es exponentiell viele mögliche Koalitionen gibt. Allerdings kann diese Schwierigkeit überwunden werden, indem man "constraint generation"-Ansätze benutzt. Einige primale und duale Heuristiken werden vorgestellt, um die Laufzeit des Separierungsproblems zu verringern. Basierend auf diesen Techniken können wir unsere Anwendungen lösen, deren Größen von klein mit 4 Spielern, bis mittel mit 18 Spielern, und groß mit 85 Spielern und 2^{85}-1 möglichen Koalitionen variieren. Durch Rechenergebnisse zeigen wir die Ungerechtigkeit der traditionellen Allokationen. Betrachten wir beispielsweise das Ticketpreis-Problem des niederländischen IC Schienennetzes. Der aktuelle Entfernungstarif resultiert in einer Situation, bei der die Passagiere in der zentralen Region des Landes über 25% mehr zahlen im Vergleich zu den ihnen entstehenden Kosten und dieser Überschuss subventioniert einige andere Bahn-Verbindungen, das ist absolut nicht fair. Im Gegensatz dazu senken unsere Spiel-theoretischen Preise diese Ungerechtigkeit und erhöhen den Anreiz für Spieler in der großen Koalition zu bleiben.
Due to economy of scale, it is suggested that individual users, in order to save costs, should join a cooperation rather than acting on their own. However, a challenge for individuals when cooperating with others is that every member of the cooperation has to agree on how to allocate the common costs among members, otherwise the cooperation cannot be realised. Taken this issue into account, we set the objective of our thesis in investigating the issue of fair allocations of common costs among users in a cooperation. This thesis combines cooperative game theory and state-of-the-art algorithms from linear and integer programming in order to define fair cost allocations and calculate them numerically for large real-world applications. Our approaches outclasse traditional cost allocation methods in terms of fairness and users' satisfaction. Cooperative game theory analyzes the possible grouping of individuals to form their coalitions. It provides mathematical tools to understand fair prices in the sense that a fair price prevents the collapse of the grand coalition and increases the stability of the cooperation. The current definition of cost allocation game does not allow us to restrict the set of possible coalitions of players and to set conditions on the output prices, which often occur in real-world applications. Our generalization bring the cost allocation game model a step closer to practice. Based on our definition, we present and discuss in the thesis several mathematical concepts, which model fairness. This thesis also considers the question of whether there exists a "best" cost allocation, which people naturally like to have. It is well-known that multicriteria optimization problems often do not have "the optimal solution" that simultaneously optimizes each objective to its optimal value. There is also no "perfect" voting-system which can satisfy all the five simple, essential social choice procedures presented in the book "Mathematics and Politics. Strategy, Voting, Power and Proof" of Taylor et al. Similarly, the cost allocation problem is shown to experience the same problem. In particular, there is no cost allocation which can satisfy all of our desired properties, which are coherent and seem to be reasonable or even indispensable. Our game theoretical concepts try to minimize the degree of axiomatic violation while the validity of some most important properties is kept. From the complexity point of view, it is NP-hard to calculate the allocations which are based on the considered game theoretical concepts. The hardest challenge is that we must take into account the exponential number of the possible coalitions. However, this difficulty can be overcome by using constraint generation approaches. Several primal and dual heuristics are constructed in order to decrease the solving time of the separation problem. Based on these techniques, we are able to solve our applications, whose sizes vary from small with 4 players, to medium with 18 players, and even large with 85 players and 2^{85}-1 possible coalitions. Via computational results, we show the unfairness of traditional cost allocations. For example, for the ticket pricing problem of the Dutch IC railway network, the current distance tariff results in a situation where the passengers in the central region of the country pay over 25% more than the costs they incur and these excess payments subsidize operations elsewhere, which is absolutely not fair. In contrast, our game theory based prices decrease this unfairness and increase the incentive to stay in the grand coalition for players.
