Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
On the computation of the nucleolus of a cooperative game
Autore:
Faigle, U; Kern, W; Kuipers, J;
Indirizzi:
Univ Cologne, Zentrum Angew Informat, D-50931 Cologne, Germany Univ Cologne Cologne Germany D-50931 Informat, D-50931 Cologne, Germany Univ Twente, Dept Appl Math, NL-7500 AE Enschede, Netherlands Univ TwenteEnschede Netherlands NL-7500 AE 500 AE Enschede, Netherlands Maastricht Univ, Dept Math, NL-6200 MD Maastricht, Netherlands Maastricht Univ Maastricht Netherlands NL-6200 MD aastricht, Netherlands
Titolo Testata:
INTERNATIONAL JOURNAL OF GAME THEORY
fascicolo: 1, volume: 30, anno: 2001,
pagine: 79 - 98
SICI:
0020-7276(200109)30:1<79:OTCOTN>2.0.ZU;2-7
Fonte:
ISI
Lingua:
ENG
Soggetto:
SPANNING TREE GAMES; COST ALLOCATION; COMPLEXITY; ALGORITHM; TIME; CORE;
Keywords:
core; nucleolus; prekernel; kernel; computational complexity; convex games; MCST-games; ellipsoid method;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Social & Behavioral Sciences
Citazioni:
27
Recensione:
Indirizzi per estratti:
Indirizzo: Faigle, U Univ Cologne, Zentrum Angew Informat, Weyertal 80, D-50931 Cologne, Germany Univ Cologne Weyertal 80 Cologne Germany D-50931 logne, Germany
Citazione:
U. Faigle et al., "On the computation of the nucleolus of a cooperative game", INT J GAME, 30(1), 2001, pp. 79-98

Abstract

We consider classes of cooperative games. We show that we can efficiently compute an allocation in the intersection of the prekernel. and the least core of the game if we can efficiently compute the minimum excess for any given allocation. In the case where the prekernel of the game contains exactly one core vector, our algorithm computes the nucleolus of the game. This generalizes both a recent result by Kuipers on the computation of the nucleolus for convex games and a classical result by Megiddo on the nucleolus of standard tree games to classes of more general minimum cost spanning tree games. Our algorithm is based on the ellipsoid method and Maschler's scheme for approximating the prekernel.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 27/11/20 alle ore 13:49:01