On the core of network synthesis games
type: Item
instance of: scholarly article
title: On the core of network synthesis games
zbMATH Open document ID: 0722.90091
DOI: 10.1007/BF01594930
published in: Mathematical Programming. Series A. Series B
publication date: 1991-01-01T00:00:00Z
review text: A formulation is proposed for unifying network design cooperative games which shows that not only the minimum cost spanning tree game satisfies the assumptions of Owen's linear production game. Moreover, since the suggested formulation is polynomial in size, a vector in the core can be computed efficiently by solving a single linear program. Generally, given a formulation for the linear production game, the set of core vectors generated by Owen's scheme from the dual solutions can be a proper subset of the core of the game. In the end, an efficient (polynomial) characterization of the cores of network synthesis games and a strongly polynomial procedure for verifying whether a given vector is in the core of these games is made.
reviewed by: D. Cusmir
Mathematics Subject Classification ID: 91A12
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91B38
Mathematics Subject Classification ID: 91B32
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 4191439
zbMATH Keywords: network design cooperative games
zbMATH Keywords: minimum cost spanning tree game
zbMATH Keywords: linear production game
zbMATH Keywords: core
zbMATH Keywords: network synthesis games
zbMATH Keywords: strongly polynomial procedure
author: Arie Tamir
MaRDI profile type: Publication
cites work: On cost allocation for a spanning tree: A game theoretic approach
cites work: Cost allocation for a spanning tree
cites work: Optimum branchings
cites work: Q4149476
cites work: Packing rooted directed cuts in a weighted directed graph
cites work: Q4198056
cites work: An Application of Generalized Linear Programming to Network Flows
cites work: Synthesis of a Communication Network
cites work: A generalized linear production model: A unifying model
cites work: On cost allocation in communication networks
cites work: Minimum cost spanning tree games
cites work: On the core and nucleolus of minimum cost spanning tree games
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Totally Balanced Games and Games of Flow
cites work: Generalized Network Problems Yielding Totally Balanced Games
cites work: Q3971521
cites work: The kernel and bargaining set for convex games
cites work: Cost allocation for steiner trees
cites work: Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree
cites work: On the core of linear production games
cites work: Traveling salesman games
cites work: The assignment game. I: The core
cites work: On the core of a traveling salesman cost allocation game
cites work: A dual ascent approach for steiner tree problems on a directed graph
full work available at URL: https://doi.org/10.1007/bf01594930
OpenAlex ID: W2060444450
description: scientific article; zbMATH DE number 4191439