Matching games: the least core and the nucleolus

Walter Kern; Daniël Paulusma

Matching games: the least core and the nucleolus

Walter Kern, Daniël Paulusma

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Professional

201 Downloads (Pure)

Abstract

A matching game is a cooperative game defined by a graph $G=(V,E)$. The player set is $V$ and the value of a coalition $S \subseteq V$ is defined as the size of a maximum matching in the subgraph induced by $S$. We show that the nucleolus of such games can be computed efficiently. The result is based on an alternative characterization of the least core which may be of independent interest. The general case of weighted matching games remains unsolved.

Original language	Undefined
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Number of pages	18
Publication status	Published - 2000

Publication series

Name	Memorandum Faculteit TW
Publisher	Department of Applied Mathematics, University of Twente
No.	1541
ISSN (Print)	0169-2690

Keywords

MSC-90C27
MSC-90D12
EWI-3361
IR-65728
METIS-141197

Access to Document

Cite this

@book{9985b60e6c804fa7816d3d61f8a9cbb1,

title = "Matching games: the least core and the nucleolus",

abstract = "A matching game is a cooperative game defined by a graph $G=(V,E)$. The player set is $V$ and the value of a coalition $S \subseteq V$ is defined as the size of a maximum matching in the subgraph induced by $S$. We show that the nucleolus of such games can be computed efficiently. The result is based on an alternative characterization of the least core which may be of independent interest. The general case of weighted matching games remains unsolved.",

keywords = "MSC-90C27, MSC-90D12, EWI-3361, IR-65728, METIS-141197",

author = "Walter Kern and Dani{\"e}l Paulusma",

note = "Imported from MEMORANDA",

year = "2000",

language = "Undefined",

series = "Memorandum Faculteit TW",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1541",

}

TY - BOOK

T1 - Matching games: the least core and the nucleolus

AU - Kern, Walter

AU - Paulusma, Daniël

N1 - Imported from MEMORANDA

PY - 2000

Y1 - 2000

N2 - A matching game is a cooperative game defined by a graph $G=(V,E)$. The player set is $V$ and the value of a coalition $S \subseteq V$ is defined as the size of a maximum matching in the subgraph induced by $S$. We show that the nucleolus of such games can be computed efficiently. The result is based on an alternative characterization of the least core which may be of independent interest. The general case of weighted matching games remains unsolved.

AB - A matching game is a cooperative game defined by a graph $G=(V,E)$. The player set is $V$ and the value of a coalition $S \subseteq V$ is defined as the size of a maximum matching in the subgraph induced by $S$. We show that the nucleolus of such games can be computed efficiently. The result is based on an alternative characterization of the least core which may be of independent interest. The general case of weighted matching games remains unsolved.

KW - MSC-90C27

KW - MSC-90D12

KW - EWI-3361

KW - IR-65728

KW - METIS-141197

M3 - Report

T3 - Memorandum Faculteit TW

BT - Matching games: the least core and the nucleolus

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -