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

Manfred Besner

MPRA Paper from University Library of Munich, Germany

Abstract: Exponential runtimes of algorithms for TU-values 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 discuss how the hierarchical structure of a level structure improves the runtimes compared to an unstructured set of players. As examples, we examine the Shapley levels value, the nested Shapley levels value, and, as a new LS-value, the nested Owen levels value. Polynomial-time algorithms for these values (under ordinary conditions) are provided. Furthermore, we introduce relevant coalition functions where all coalitions which 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 values of the Harsanyi set and many values from extensions of this set.

Keywords: Cooperative; game; ·; Polynomial-time; algorithm; ·; Level; structure; ·; (Nested); Shapley/Owen; (levels); value; ·; Harsanyi; dividends (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Date: 2020-03-30
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://mpra.ub.uni-muenchen.de/99355/1/MPRA_paper_99355.pdf original version (application/pdf)
https://mpra.ub.uni-muenchen.de/101464/1/MPRA_paper_101464.pdf revised version (application/pdf)
https://mpra.ub.uni-muenchen.de/112329/1/MPRA_paper_101464.pdf revised version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pra:mprapa:99355

Access Statistics for this paper

More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().