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

258 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

Fingerprint

Nucleolus
Coalitions
Game
Efficient Algorithms
Polynomial

Keywords

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

Cite this

Brânzei, R., Solymosi, T., & Tijs, S. H. (2003). Strongly Essential Coalitions and the Nucleolus of Peer Group Games. (CentER Discussion Paper; Vol. 2003-19). Tilburg: Microeconomics.
Brânzei, R. ; Solymosi, T. ; Tijs, S.H. / Strongly Essential Coalitions and the Nucleolus of Peer Group Games. Tilburg : Microeconomics, 2003. (CentER Discussion Paper).
@techreport{d2db812ab13a4e839198274d912fc02e,
title = "Strongly Essential Coalitions and the Nucleolus of Peer Group Games",
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.",
keywords = "game theory, algorithm, cooperative games, kernel estimation, peer games",
author = "R. Br{\^a}nzei and T. Solymosi and S.H. Tijs",
note = "Pagination: 16",
year = "2003",
language = "English",
volume = "2003-19",
series = "CentER Discussion Paper",
publisher = "Microeconomics",
type = "WorkingPaper",
institution = "Microeconomics",

}

Brânzei, R, Solymosi, T & Tijs, SH 2003 'Strongly Essential Coalitions and the Nucleolus of Peer Group Games' CentER Discussion Paper, vol. 2003-19, Microeconomics, Tilburg.

Strongly Essential Coalitions and the Nucleolus of Peer Group Games. / Brânzei, R.; Solymosi, T.; Tijs, S.H.

Tilburg : Microeconomics, 2003. (CentER Discussion Paper; Vol. 2003-19).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Strongly Essential Coalitions and the Nucleolus of Peer Group Games

AU - Brânzei, R.

AU - Solymosi, T.

AU - Tijs, S.H.

N1 - Pagination: 16

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - game theory

KW - algorithm

KW - cooperative games

KW - kernel estimation

KW - peer games

M3 - Discussion paper

VL - 2003-19

T3 - CentER Discussion Paper

BT - Strongly Essential Coalitions and the Nucleolus of Peer Group Games

PB - Microeconomics

CY - Tilburg

ER -

Brânzei R, Solymosi T, Tijs SH. Strongly Essential Coalitions and the Nucleolus of Peer Group Games. Tilburg: Microeconomics. 2003. (CentER Discussion Paper).