- Updated: January 24, 2026
- 6 min read
On the closest balanced game
Direct Answer
The paper introduces a fast, exact algorithm for finding the closest balanced cooperative game to any given game under Euclidean distance, and it formalizes a new solution concept called the least‑square core. This matters because it provides practitioners with a tractable way to repair or approximate games that violate core feasibility, enabling more reliable analysis and design of multi‑agent economic systems.
Background: Why This Problem Is Hard
Cooperative game theory models how groups of agents (players) can share collective gains. The core—the set of allocations that no coalition can improve upon—is the gold standard for stability. However, many real‑world games derived from data, simulations, or heuristic models are unbalanced: their core is empty, meaning no stable payoff distribution exists. Detecting emptiness is polynomial, but repairing such games—i.e., finding the nearest game that does have a non‑empty core—has been computationally prohibitive.
Existing approaches typically resort to:
- Heuristic adjustments that lack optimality guarantees.
- Linear programming formulations that scale poorly with the number of players (exponential in the number of coalitions).
- Iterative projection methods that converge slowly and provide no bound on distance to the true optimum.
These limitations hinder applications ranging from cost‑allocation in logistics to fairness analysis in AI‑driven marketplaces, where rapid, provably optimal adjustments are essential.
What the Researchers Propose
The authors propose a two‑part contribution:
- A fast exact algorithm that computes the Euclidean‑closest balanced game to any input game. The method leverages orthogonal projection onto the convex polyhedron defined by the core constraints, exploiting the structure of balancedness to avoid enumerating all coalitions.
- The least‑square core, a novel solution concept that selects the point in the core minimizing the squared Euclidean distance to a given (possibly unbalanced) payoff vector. This extends the classic core by providing a principled “best‑fit” allocation when the core is empty.
Key components of the framework include:
- Core feasibility module: checks whether a game is balanced and, if not, identifies the minimal set of violated constraints.
- Projection engine: performs an orthogonal projection of the game’s characteristic function onto the balanced‑game subspace.
- Least‑square optimizer: solves a quadratic program that yields the least‑square core allocation.
How It Works in Practice
The workflow can be visualized as a pipeline:
- Input acquisition: The practitioner supplies a characteristic function \(v\) that maps every coalition to its worth.
- Balance assessment: The core feasibility module quickly determines if \(v\) satisfies the balancedness inequalities. If the core is non‑empty, the algorithm terminates, returning the original game.
- Constraint reduction: When the core is empty, the algorithm isolates a minimal set of “critical” coalitions whose constraints drive infeasibility. This reduction is possible because balancedness can be expressed via a finite set of extreme points of the balancedness polytope.
- Orthogonal projection: The projection engine solves a closed‑form linear system that projects \(v\) onto the subspace spanned by the critical constraints, yielding the closest balanced game \(v^{*}\).
- Least‑square core extraction: With \(v^{*}\) in hand, the least‑square optimizer computes the allocation \(x^{*}\) that minimizes \(\|x – v^{*}\|_{2}^{2}\) subject to core constraints, delivering a stable payoff vector even when the original game was unbalanced.
What sets this approach apart is its avoidance of exponential enumeration. By focusing on the geometry of the balancedness polytope and using matrix‑based projections, the algorithm runs in polynomial time with respect to the number of players, making it practical for games with dozens of participants.
Evaluation & Results
The authors benchmarked their method on synthetic and real‑world cooperative games, including:
- Randomly generated characteristic functions for 5–30 players.
- Cost‑sharing instances from transportation logistics.
- Revenue‑allocation scenarios in ad‑auction consortia.
Key findings:
- Speedup: The new algorithm solved instances up to 30 players in under a second, a 10‑ to 100‑fold improvement over baseline linear‑programming approaches.
- Optimality: The Euclidean distance between the original and repaired games matched the theoretical lower bound, confirming exactness.
- Stability gains: In unbalanced logistics cases, the least‑square core allocation reduced coalition incentives to deviate by an average of 27 % compared with naïve heuristic fixes.
These results demonstrate that the method not only scales but also delivers the mathematically closest balanced representation, preserving as much of the original game’s structure as possible.
Why This Matters for AI Systems and Agents
From an AI engineering perspective, cooperative game models underpin many multi‑agent coordination mechanisms—resource allocation, task scheduling, and incentive design. When the underlying game is unbalanced, agents may pursue selfish strategies that destabilize the system. The fast balanced‑game algorithm enables:
- Real‑time repair of payoff structures in dynamic environments, such as autonomous fleet management, where cost functions evolve rapidly.
- Robust simulation of economic scenarios, ensuring that synthetic agents operate under stable, core‑consistent incentives.
- Automated fairness auditing for AI‑driven marketplaces, by projecting observed transaction data onto the nearest balanced game and exposing systematic imbalances.
Practitioners can integrate the projection engine into existing orchestration platforms to automatically enforce core feasibility before deploying agent policies. For example, see the agent orchestration framework that now supports plug‑in modules for cooperative‑game repair.
What Comes Next
While the algorithm marks a significant step forward, several avenues remain open:
- Scalability to hundreds of players: Extending the projection technique to exploit sparsity patterns in large‑scale coalition structures.
- Alternative distance metrics: Investigating ℓ₁ or weighted norms that may better reflect domain‑specific cost sensitivities.
- Dynamic games: Adapting the method for time‑varying characteristic functions where balance must be maintained across multiple periods.
- Integration with learning agents: Embedding the least‑square core computation into reinforcement‑learning pipelines to guide policy updates toward stable cooperative equilibria.
Future research could also explore hybrid solution concepts that blend the least‑square core with bargaining solutions, offering richer fairness guarantees. Developers interested in prototyping such extensions can leverage the cooperative simulation toolkit that already includes a modular implementation of the projection engine.
For a deeper dive into the theoretical foundations, readers can consult the arXiv paper, which details the polyhedral geometry, proof of optimality, and asymptotic analysis.