A Linear Programming Approach to Estimate the Core in Cooperative Games

2025/10/02 by José Camacho, Camacho, J, Juan Carlos Gonçalves-Dosantos +3
Business, Management and Accounting · #90C05 #91A12 #91A68 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Supply Chain and Inventory Management

paper · pdf · doi:10.48550/arxiv.2510.01766

openalex publication_date 2025/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper proposes a novel algorithm to approximate the core of transferable utility (TU) cooperative games via linear programming. Given the computational hardness of determining the full core, our approach provides a tractable approximation by sampling extreme points through randomized linear problems (LPs). We analyze its convergence and computational complexity, and validate its effectiveness through extensive simulations on various game models. Our results show that the method is scalable and achieves high accuracy in terms of core reconstruction.

Citations

• Parallelizing the dual revised simplex method
• Bounding the Estimation Error of Sampling-based Shapley Value Approximation
• A Stochastic Programming Duality Approach to Inventory Centralization Games
• A natural selection from the core of a TU game: the core-center
• On the Complexity of Cooperative Solution Concepts
• Cores of convex games
• The assignment game I: The core
• A BEHAVIORAL MODEL OF RATIONAL CHOICE

Related

• Approximating the Core via Iterative Coalition Sampling
• Coreness of Cooperative Games with Truncated Submodular Profit Functions
• Algorithmic Solutions for Maximizing Shareable Costs
• Characterising and Verifying the Core in Concurrent Multi-Player Mean-Payoff Games (Full Version)
• Cooperative Games with Overlapping Coalitions: Charting the Tractability Frontier