Stable effectivity functions and perfect graphs

Endre Boros; Vladimir Gurvich

doi:10.1016/S0165-4896(99)00017-7

Stable effectivity functions and perfect graphs

Endre Boros
, Vladimir Gurvich

Rutgers Business School, Management & Information Systems

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

We consider the problem of characterizing the stability of effectivity functions (EFF), via a correspondence between game theoretic and well-known combinatorial concepts. To every EFF we assign a pair of hypergraphs, representing clique covers of two associated graphs, and obtain some necessary and some sufficient conditions for the stability of EFFs in terms of graph-properties. These conditions imply, for example, that to check the stability of an EFF is an NP-complete problem. We also translate some well-known conjectures of graph theory into game theoretic language and vice versa.

Original language	English (US)
Pages (from-to)	175-194
Number of pages	20
Journal	Mathematical social sciences
Volume	39
Issue number	2
DOIs	https://doi.org/10.1016/S0165-4896(99)00017-7
State	Published - Mar 2000

All Science Journal Classification (ASJC) codes

Sociology and Political Science
General Social Sciences
General Psychology
Statistics, Probability and Uncertainty

Keywords

Core
Kernel
Kernel-solvable graph
Perfect graph
Stable effectivity function

Access to Document

10.1016/S0165-4896(99)00017-7

Cite this

@article{4679ce9c21a941f08e132c8290a5d33e,

title = "Stable effectivity functions and perfect graphs",

abstract = "We consider the problem of characterizing the stability of effectivity functions (EFF), via a correspondence between game theoretic and well-known combinatorial concepts. To every EFF we assign a pair of hypergraphs, representing clique covers of two associated graphs, and obtain some necessary and some sufficient conditions for the stability of EFFs in terms of graph-properties. These conditions imply, for example, that to check the stability of an EFF is an NP-complete problem. We also translate some well-known conjectures of graph theory into game theoretic language and vice versa.",

keywords = "Core, Kernel, Kernel-solvable graph, Perfect graph, Stable effectivity function",

author = "Endre Boros and Vladimir Gurvich",

note = "Funding Information: The authors gratefully acknowledge the partial support by the National Science Foundation (Grant DMS-98-06389), by the Office of Naval Research (Grant N00014-92-J-1375), and by DIMACS, the National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science (NSF grant STC-88-09648). Appendix A ",

year = "2000",

month = mar,

doi = "10.1016/S0165-4896(99)00017-7",

language = "English (US)",

volume = "39",

pages = "175--194",

journal = "Mathematical social sciences",

issn = "0165-4896",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Stable effectivity functions and perfect graphs

AU - Boros, Endre

AU - Gurvich, Vladimir

N1 - Funding Information: The authors gratefully acknowledge the partial support by the National Science Foundation (Grant DMS-98-06389), by the Office of Naval Research (Grant N00014-92-J-1375), and by DIMACS, the National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science (NSF grant STC-88-09648). Appendix A

PY - 2000/3

Y1 - 2000/3

N2 - We consider the problem of characterizing the stability of effectivity functions (EFF), via a correspondence between game theoretic and well-known combinatorial concepts. To every EFF we assign a pair of hypergraphs, representing clique covers of two associated graphs, and obtain some necessary and some sufficient conditions for the stability of EFFs in terms of graph-properties. These conditions imply, for example, that to check the stability of an EFF is an NP-complete problem. We also translate some well-known conjectures of graph theory into game theoretic language and vice versa.

AB - We consider the problem of characterizing the stability of effectivity functions (EFF), via a correspondence between game theoretic and well-known combinatorial concepts. To every EFF we assign a pair of hypergraphs, representing clique covers of two associated graphs, and obtain some necessary and some sufficient conditions for the stability of EFFs in terms of graph-properties. These conditions imply, for example, that to check the stability of an EFF is an NP-complete problem. We also translate some well-known conjectures of graph theory into game theoretic language and vice versa.

KW - Core

KW - Kernel

KW - Kernel-solvable graph

KW - Perfect graph

KW - Stable effectivity function

UR - https://www.scopus.com/pages/publications/0041491349

UR - https://www.scopus.com/pages/publications/0041491349#tab=citedBy

U2 - 10.1016/S0165-4896(99)00017-7

DO - 10.1016/S0165-4896(99)00017-7

M3 - Article

AN - SCOPUS:0041491349

SN - 0165-4896

VL - 39

SP - 175

EP - 194

JO - Mathematical social sciences

JF - Mathematical social sciences

IS - 2

ER -

Stable effectivity functions and perfect graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this