On the closest balanced game
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917216675430400 |
|---|---|
| author | García-Segador, Pedro Grabisch, Michel Mermoud, Dylan Laplace Miranda, Pedro |
| author_facet | García-Segador, Pedro Grabisch, Michel Mermoud, Dylan Laplace Miranda, Pedro |
| contents | 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.e., the orthogonal projection of the game on the set of balanced games. Besides an analytical approach which becomes rapidly intractable, we propose a fast algorithm to find the closest balanced game, avoiding exponential complexity for the optimization problem, and being able to run up to 20 players. 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. We provide a mathematical proof that the proportion of facets whose games have a non-singleton core tends to 0 when the number of players grow, by finding an expression of the aymptotic growth of the number of minimal balanced collections. This permits to prove mathematically the experimental result. Consequently, taking the core of the projected game defines a new solution concept, which we call least square core due to its analogy with the least core, and our result shows that the probability that this is a point solution tends to 1 when the number of players grow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15318 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the closest balanced game García-Segador, Pedro Grabisch, Michel Mermoud, Dylan Laplace Miranda, Pedro Computer Science and Game Theory 91A12 - Cooperative games 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.e., the orthogonal projection of the game on the set of balanced games. Besides an analytical approach which becomes rapidly intractable, we propose a fast algorithm to find the closest balanced game, avoiding exponential complexity for the optimization problem, and being able to run up to 20 players. 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. We provide a mathematical proof that the proportion of facets whose games have a non-singleton core tends to 0 when the number of players grow, by finding an expression of the aymptotic growth of the number of minimal balanced collections. This permits to prove mathematically the experimental result. Consequently, taking the core of the projected game defines a new solution concept, which we call least square core due to its analogy with the least core, and our result shows that the probability that this is a point solution tends to 1 when the number of players grow. |
| title | On the closest balanced game |
| topic | Computer Science and Game Theory 91A12 - Cooperative games |
| url | https://arxiv.org/abs/2601.15318 |