Axiomatizations of Harsanyi Solutions and Extensions, Values for Level Structures, and Polynomial-Time Algorithms

Besner, Manfred

This thesis focuses on solution concepts for cooperative games with transferable utility (TU-games), which are single-valued (TU-values). In the first chapter, we present value dividends, a new concept for TU-values. Value dividends are, similar to Harsanyi dividends, recursively defined and can be considered as the pure cooperation benefit a player receives for participating in a coalition. We propose new characterizations of TU-values from the Harsanyi set, known as Harsanyi solutions, which use also axioms that apply value dividends. In addition, we generalize the Harsanyi set, where each TU-value from this new class is defined by distributing the Harsanyi dividends by weights that may depend on the whole coalition function. As a representative of the generalized Harsanyi set, the proportional Harsanyi solution is introduced. This new proportional TU-value distributes the worth of the grand coalition proportionally to the ratio of the sums of the value dividends over all subcoalitions in that the players are involved. The proportional Shapley value, a weighted TU-value with the worths of the singletons as weights, is part of the generalized Harsanyi set as well. We present new characterizations as proportional counterparts to famous axiomatizations of the Shapley value. Two new axioms, proportionality and player splitting, mark the key difference to the Shapley value. The player splitting axiom states that players’ payoffs do not change if another player splits into two new players who have the same impact on the game as the original player. In particular, this axiom justifies the use of the proportional Shapley value in many economic situations, especially for cost allocation. The second chapter deals with games with level structures. In these hierarchical structures, each level corresponds to a partition of the player set, that becomes increasingly coarse from the trivial partition containing only singletons to the partition containing only the grand coalition. Together with a TU-game, we receive games on level structures (LS-games) with appropriate solutions (LS-values). A top-down algorithm introduces the weighted Shapley hierarchy levels values as a new class of LS-values, an extension of the class of weighted Shapley values. This class contains, as a special case, the Shapley levels value, the most famous extension of the Shapley value for LS-games. Other extensions of the Shapley value that we present with a top-down algorithm are the nested Shapley levels value and the nested Owen levels value. As a further new class, we introduce the Harsanyi support levels set, which extends the Harsanyi solutions of the Harsanyi set to LS-values. Here again, payoffs are made in such a way that the Harsanyi dividends are distributed among the players, this time weighted by special hierarchical weight systems. As an important subset of the Harsanyi support levels set, we investigate the class of the weighted Shapley support levels values. The LS-Values from this class also extend the weighted Shapley values and include the Shapley levels value as a special case too. Exponential runtimes of algorithms for TU-values such as the Shapley value are a major barrier to the application of otherwise axiomatically convincing solution concepts of cooperative game theory. In the third and last chapter, we discuss how the hierarchical structure of a level structure improves the runtimes compared to an unstructured set of players. As examples, we investigate the Shapley levels value, the nested Shapley levels value, and the nested Owen levels value. Polynomial-time algorithms for these LS-values, under ordinary conditions, are provided. Furthermore, we introduce relevant coalition functions where all coalitions that are not relevant for the payoff calculation have a Harsanyi dividend of zero. By these coalition functions, our results shed new light on the computation of TU-values of the Harsanyi set and many TU-values from extensions of this set. This closes the circle to the TU-values from the first chapter.

In dieser Dissertation untersuchen wir Lösungskonzepte für kooperative Spiele mit übertragbarem Nutzen (TU-Games), die eine eindeutige Lösung aufweisen (TU-Values). Im ersten Kapitel werden Value-Dividenden eingeführt, ein neues Konzept für TU-Values. Value-Dividenden sind, ähnlich wie Harsanyi-Dividenden, rekursiv definiert und können als der reine Kooperationsgewinn eines Spielers betrachtet werden, den ein Spieler für die Mitwirkung in einer Koalition erhält. Wir stellen neue Charakterisierungen von TU-Values aus dem Harsanyi-Set, die Harsanyi-Solutions, vor, bei denen Axiome benutzt werden, die Value-Dividenden verwenden. Des Weiteren verallgemeinern wir das Harsanyi-Set, wobei jeder TU-Value aus dieser neuen Klasse dadurch definiert ist, dass die Harsanyi-Dividenden auf die Spieler durch Gewichte verteilt werden, die von der ganzen Koalitionsfunktion abhängen können. Als eine Vertreterin des verallgemeinerten Harsanyi-Sets wird die Proportional-Harsanyi-Solution vorgestellt. Dieses neue proportionale Lösungskonzept verteilt den Wert der großen Koalition proportional zum Verhältnis der Summen der Value-Dividenden aller Teilkoalitionen, an denen die Spieler beteiligt sind. Der Proportional-Shapley-Value, ein gewichteter TU-Value mit den Werten der Einerkoalitionen als Gewichte, ist ebenfalls Teil des verallgemeinerten Harsanyi-Sets. Wir schlagen neue Charakterisierungen als proportionale Pendants zu berühmten Axiomatisierungen des Shapley-Values vor. Zwei neue Axiome, Proportionality und Player-Splitting, zeigen dabei den Hauptunterschied zum Shapley-Value auf. Das Player- Splitting-Axiom besagt, dass sich die Auszahlungen der Spieler nicht ändern, wenn sich ein anderer Spieler in zwei neue Spieler aufteilt, die zusammen die gleichen Auswirkungen auf das Spiel haben wie der ursprüngliche Spieler. Insbesondere dieses Axiom rechtfertigt die Anwendung des Proportional-Shapley-Values in vielen ökonomischen Situationen, insbesondere für die Kostenanrechnung. Das zweite Kapitel beschäftigt sich mit Spielen mit Level-Structures. Bei diesen hierarchischen Strukturen entspricht jede Ebene (Level) einer Partition der Spielermenge, die von der trivialen Partition, die nur Einerkoalitionen enthält, bis zu der Partition, die nur die große Koalition enthält, immer gröber werden. Zusammen mit einem TU-Game erhalten wir Spiele auf Level-Structures (LS-Games) mit entsprechenden Lösungskonzepten (LS-Values). Mit einem Top-Down-Algorithmus führen wir als neue Klasse von LS-Values die Weighted-Shapley-Hierarchy-Levels-Values ein, eine Erweiterung der Klasse der Weighted-Shapley-Values. Diese Klasse enthält als Spezialfall den Shapley-Levels-Value, die bekannteste Erweiterung des Shapley-Values für LS-Games. Andere Erweiterungen des Shapley-Values, die wir mit einem Top-Down-Algorithmus vorstellen, sind der Nested- Shapley-Levels-Value und der Nested-Owen-Levels-Value. Als eine weitere neue Klasse führen wir das Harsanyi-Support-Levels-Set ein, das die Harsanyi-Solutions des Harsanyi-Sets zu LS-Values erweitert. Die Auszahlungen werden so vorgenommen, dass die Harsanyi-Dividenden unter den Spielern aufgeteilt werden, diesmal gewichtet mit speziellen hierarchischen Gewichtungssystemen. Als wichtige Teilmenge des Harsanyi-Support-Levels-Set untersuchen wir die Klasse der Weighted-Shapley-Support-Levels-Values. Die LS-Values aus dieser Klasse erweitern auch die Weighted-Shapley-Values und enthalten, als Sonderfall, ebenfalls den Shapley-Levels-Value. Exponentielle Laufzeiten von Algorithmen für TU-Values wie den Shapley-Value sind eines der größten Hindernisse bei der praktischen Anwendung von ansonsten axiomatisch überzeugenden Lösungskonzepten der kooperativen Spieltheorie. Im dritten und letzten Kapitel erörtern wir, wie die hierarchische Struktur einer Level-Structure die Laufzeiten im Vergleich zu einer unstrukturierten Spielermenge verbessert. Beispielhaft untersuchen wir den Shapley-Levels-Value, den Nested-Shapley-Levels-Value und den Nested-Owen- Levels-Value. Es werden Polynomzeitalgorithmen für diese LS-Values (unter normalen Bedingungen) angegeben. Darüber hinaus führen wir relevante Koalitionsfunktionen ein, bei denen alle Koalitionen, die für die Auszahlungsberechnung nicht relevant sind, eine Harsanyi-Dividende von Null haben. Anhand dieser Koalitionsfunktionen werfen unsere Ergebnisse auch ein neues Licht auf die Berechnung der TU-Values aus dem Harsanyi-Set und vieler TU-Values aus Verallgemeinerungen dieses Sets. Damit schließt sich der Kreis zu den TU-Values aus dem ersten Kapitel.

Vorschau

Zitieren

Zitierform:

Besner, Manfred: Axiomatizations of Harsanyi Solutions and Extensions, Values for Level Structures, and Polynomial-Time Algorithms. Hagen 2020. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe