An efficient algorithm for nucleolus and prekernel computation in some classes of TU-games

U. Faigle, Walter Kern, J. Kuipers

Research output: Book/ReportReportOther research output

98 Downloads (Pure)

Abstract

We consider classes of TU-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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 1998

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
No.1464
ISSN (Print)0169-2690

Keywords

  • MSC-90D12
  • IR-65653
  • MSC-90C27
  • EWI-3284

Cite this