Algorithmic Aspects of the Core of Combinatorial Optimization Games

DOI10.1287/moor.24.3.751zbMath1064.91505OpenAlexW2113370239MaRDI QIDQ4951047

Toshihide Ibaraki, Hiroshi Nagamochi, Xiaotie Deng

Publication date: 19 July 2000

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.24.3.751

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Cooperative games (91A12) Combinatorial games (91A46)

Related Items (73)

The computational complexity of the Edge-Perfect Graph and the Totally Balanced Packing Game recognition problems ⋮ Three-valued simple games ⋮ Complexity of core allocation for the bin packing game ⋮ Population monotonicity in matching games ⋮ Stochastic linear programming games with concave preferences ⋮ Component Acquisition Games ⋮ New techniques for cost sharing in combinatorial optimization games ⋮ Minimum coloring problems with weakly perfect graphs ⋮ Computing Stable Coalitions: Approximation Algorithms for Reward Sharing ⋮ The stable fixtures problem with payments ⋮ Simple and three-valued simple minimum coloring games ⋮ On the convexity of independent set games ⋮ Clique games: a family of games with coincidence between the nucleolus and the Shapley value ⋮ Allocating costs in set covering problems ⋮ On the cores of games arising from integer edge covering functions of graphs ⋮ Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner ⋮ On the complexity of nucleolus computation for bipartite \(b\)-matching games ⋮ Stabilization of capacitated matching games ⋮ The enemy of my enemy is my friend: new conditions for network games ⋮ Strategic cooperation in cost sharing games ⋮ Approximate core allocations for edge cover games ⋮ Computing the least-core and nucleolus for threshold cardinality matching games ⋮ Buyer-supplier games: optimization over the core ⋮ Computing Near-Optimal Stable Cost Allocations for Cooperative Games by Lagrangian Relaxation ⋮ Arboricity games: the core and the nucleolus ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Network bargaining: using approximate blocking sets to stabilize unstable instances ⋮ A parametric worst-case approach to fairness in cooperative games with transferable utility ⋮ Recent development in computational complexity characterization of Nash equilibrium ⋮ On the complexity of core, kernel, and bargaining set ⋮ Fair cost allocations under conflicts - a game-theoretic point of view - ⋮ Approximately fair cost allocation in metric traveling salesman games ⋮ A note on maximal covering location games ⋮ Production-inventory games and PMAS-games: Characterizations of the Owen point ⋮ Computing solutions for matching games ⋮ Finding nucleolus of flow game ⋮ Enforcing fair cooperation in production-inventory settings with heterogeneous agents ⋮ Balancedness of edge covering games ⋮ Monotonic stable solutions for minimum coloring games ⋮ LINEAR AND INTEGER PROGRAMMING TECHNIQUES FOR COOPERATIVE GAMES ⋮ Dynamic linear programming games with risk-averse players ⋮ Efficient stabilization of cooperative matching games ⋮ Non-cooperative facility location and covering games ⋮ Population monotonic allocation schemes for vertex cover games ⋮ On complexity of single-minded auction ⋮ Dominating set games. ⋮ Algorithms for core stability, core largeness, exactness, and extendability of flow games ⋮ The nucleolus of arborescence games in directed acyclic graphs ⋮ Graph Stabilization: A Survey ⋮ Multi-sided assignment games on \(m\)-partite graphs ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ A fast approximation algorithm for solving the complete set packing problem ⋮ Production-inventory games: A new class of totally balanced combinatorial optimization games ⋮ Computing the nucleolus of weighted cooperative matching games in polynomial time ⋮ Network strength games: the core and the nucleolus ⋮ Social exchange networks with distant bargaining ⋮ Total balancedness condition for Steiner tree games. ⋮ Stabilizing Weighted Graphs ⋮ Answers set programs for non-transferable utility games: expressiveness, complexity and applications ⋮ ASSIGNMENT SITUATIONS WITH MULTIPLE OWNERSHIP AND THEIR GAMES ⋮ The Stable Fixtures Problem with Payments ⋮ Gain-sharing in urban consolidation centers ⋮ Traveling salesman games with the Monge property ⋮ On core stability, vital coalitions, and extendability ⋮ Cooperative games with overlapping coalitions: charting the tractability frontier ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ Set-weighted games and their application to the cover problem ⋮ On the population monotonicity of independent set games ⋮ On the properties of weighted minimum colouring games ⋮ A note on balancedness of dominating set games ⋮ Universally balanced combinatorial optimization games ⋮ A Combinatorial Characterization for Population Monotonic Allocations in Convex Independent Set Games

This page was built for publication: Algorithmic Aspects of the Core of Combinatorial Optimization Games