Strongly Essential Coalitions and the Nucleolus of Peer Group Games

R. Brânzei, T. Solymosi, S.H. Tijs

Research output: Working paperDiscussion paperOther research output

445 Downloads (Pure)

Abstract

Most of the known efficient algorithms designed to compute the nucleolus for special classes of balanced games are based on two facts: (i) in any balanced game, the coalitions which actually determine the nucleolus are essential; and (ii) all essential coalitions in any of the games in the class belong to a prespeci ed collection of size polynomial in the number of players.We consider a subclass of essential coalitions, called strongly essential coalitions, and show that in any game, the collection of strongly essential coalitions contains all the coalitions which actually determine the core, and in case the core is not empty, the nucleolus and the kernelcore.As an application, we consider peer group games, and show that they admit at most 2n - 1 strongly essential coalitions, whereas the number of essential coalitions could be as much as 2n-1. We propose an algorithm that computes the nucleolus of an n-player peer group game in O(n2) time directly from the data of the underlying peer group situation.
Original languageEnglish
Place of PublicationTilburg
PublisherMicroeconomics
Number of pages16
Volume2003-19
Publication statusPublished - 2003

Publication series

NameCentER Discussion Paper
Volume2003-19

Keywords

  • game theory
  • algorithm
  • cooperative games
  • kernel estimation
  • peer games

Fingerprint

Dive into the research topics of 'Strongly Essential Coalitions and the Nucleolus of Peer Group Games'. Together they form a unique fingerprint.

Cite this