On the closest balanced game

arXiv:2601.15318 · cs.GT · Submitted 2026-01-16 · Read on arXiv

Pedro GARCIA-SEGADOR, Michel GRABISCH, Dylan LAPLACE MERMOUD, Pedro MIRANDA

National Statistical Institute of Madrid · Charles University of Prague · Université Paris I Panthéon-Sorbonne Centre d’Economie de la Sorbonne Paris France · UMA ENSTA Institut Polytechnique de Paris CEDRIC Conservatoire National des Arts et Métiers Complutense University of Madrid

cs.GT

Submitted: 2026-01-16

Updated: 2026-11-17

Code: https://github.com/pgsegador/CloBalGame

The gist: Cooperative games with nonempty core are called balanced, and the set of balanced games is a polyhedron Given a game with empty core, we look for the closest balanced game…

Terminology

Summary

Cooperative games with nonempty core are called balanced, and the set of balanced games is a polyhedron Given a game with empty core, we look for the closest balanced game, in the sense of the (weighted) Euclidean distance, i. p. 0e., the orthogonal projection of the game on the set of balanced games We show experimentally that the probability that the closest game has a core reduced to a singleton tends to 1 when the number of players grow

The Problem and Proposed Solution

The paper addresses finding the closest balanced game to a given game with an empty core, which is equivalent to finding the orthogonal projection of the game onto the set of balanced games The authors propose a fast algorithm to solve this optimization problem, avoiding exponential complexity for up to 20 players This approach leads to a new solution concept called the least square core, defined as the core of the projected game

Analytical and Optimization Approaches

The problem of projecting onto a polyhedron is generally not analytically feasible because the projection may fall on an unknown facet or face The optimization approach involves minimizing the weighted sum of squared differences between game values and balanced game values, leading to a quadratic programming problem While this problem is equivalent to a simpler problem involving only one constraint, solving it exactly for large numbers of players remains computationally intensive with exponential complexity

Convergence of the Singleton Core Property

The simulation study reveals that as the number of players increases, the probability that the closest game has a core reduced to a singleton tends to 1 This is supported by a mathematical proof showing that the proportion of facets whose games have a non-singleton core tends to 0 when the number of players grows The authors establish this by analyzing the asymptotic growth of minimal balanced collections

Mathematical Proof and Conclusion

The paper provides a mathematical proof that the proportion of facets whose games have a singleton core tends to 0 when the number of players grows This is achieved by finding an expression of the asymptotic growth of the number of minimal balanced collections Consequently, they prove that the probability that the closest game has a singleton core tends to 1 as n tends to infinity

New Solution Concept and Algorithm

The results lead to the definition of a new solution concept called the least square core, which is analogous to the least core The CLOBIS algorithm is proposed as an efficient method to compute this closest balanced game up to 20 players The final output of the algorithm, when it terminates, is a core element of the projected game

Simulation Results and Hypothesis

Simulation studies indicate that for different values of n and L, the probability that the projection v∗ has a single core tends to 1 very quickly Furthermore, the results suggest that typical random procedures satisfy the No Excessive Face Probability Concentration (NEFPC) Hypothesis This hypothesis implies that the probability of the closest balanced game having a non-singleton core tends to zero as n increases

Final Summary of Findings

In conclusion, the paper successfully studied both finding the closest balanced game and determining whether it has a singleton core Experiments show that as n grows, the probability that the closest game has a singleton core tends to 1 A mathematical proof establishes that the proportion of facets with non-singleton cores tends to 0 as n increases This allows for the definition of the least square core solution concept. The fast algorithm makes this concept easily computable up to 20 players The empirical results confirm that the NEFPC Hypothesis is satisfied, supporting the theoretical result that the probability of a non-singleton core tends to zero. p. 0 The paper concludes by stating that for large n, most often the probability to fall on some facet is greater than the probability to fall on a face of lower dimension The study provides a new solution concept and an efficient algorithm for finding it. p. 1 The references are listed in the concluding remarks section. p. 1

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Implement a fast algorithm for finding balanced games by reducing an exponential complexity problem to one solvable in seconds for up to 20 players, allowing practical computation beyond analytical intractability.

  2. Develop a new solution concept called least square core based on the projection of a game onto the set of balanced games, enabling researchers to define this concept through the orthogonal projection of the game on the set of balanced games.

  3. Create an iterative algorithm called CLOBIS that solves for an allocation x in C(v) by iteratively minimizing a convex function, which is equivalent to finding v star via Problem (7), allowing computation up to 20 players efficiently.

  4. Enhance game theory solvers by utilizing the relationship derived in Corollary 1, which states that v star(S) = min(x(S), v(S)) for all S subset of N, providing a direct method to derive the closest balanced game from any core imputation x in C(v star).

  5. Improve analysis of solution concepts by leveraging the results on the core of projected games, which show that the probability that this is a point solution tends to 1 when the number of players grow, suggesting that most solutions are single points.

Related papers