Munich Personal RePEc Archive

Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations

Besner, Manfred (2020): Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations.

This is the latest version of this item.

[img]
Preview
PDF
MPRA_paper_101464.pdf

Download (573kB) | Preview

Abstract

Exponential runtimes of algorithms for values for games with transferable utility like the Shapley value are one of the biggest obstacles in the practical application of otherwise axiomatically convincing solution concepts of cooperative game theory. We investigate to what extent the hierarchical structure of a level structure improves runtimes compared to an unstructured player set. Representatively, we examine the Shapley levels value, the nested Shapley levels value, and, as a new value for level structures, the nested Owen levels value. For these values, we provide polynomial-time algorithms (under normal conditions) which are exact and therefore not approximation algorithms. Moreover, we introduce relevant coalition functions where all coalitions that are not relevant for the payoff calculation have a Harsanyi dividend of zero. Our results shed new light on the computation of values of the Harsanyi set as the Shapley value and many values from extensions of this set.

Available Versions of this Item

UB_LMU-Logo
MPRA is a RePEc service hosted by
the Munich University Library in Germany.