On the closest balanced game
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
-
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.
-
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.
-
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.
-
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). -
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
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments