Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.18449 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915463041122304 |
|---|---|
| author | Chen, Jiehua Hatschka, Christian Simola, Sofia |
| author_facet | Chen, Jiehua Hatschka, Christian Simola, Sofia |
| contents | We propose a class of cooperative games, called d Partitioned Compbinatorial Optimization Games (PCOGs). The input of PCOG consists of a set of agents and a combinatorial structure (typically a graph) with a fixed optimization goal on this structure (e.g., finding a minimum dominating set on a graph) such that the structure is divided among the agents. The value of each coalition of agents is derived from the optimal solution for the part of the structure possessed by the coalition. We study two fundamental questions related to the core: Core Stability Verification and Core Stability Existence. We analyze the algorithmic complexity of both questions for four classic graph optimization tasks: minimum vertex cover, minimum dominating set, minimum spanning tree, and maximum matching. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18449 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partitioned Combinatorial Optimization Games Chen, Jiehua Hatschka, Christian Simola, Sofia Computer Science and Game Theory We propose a class of cooperative games, called d Partitioned Compbinatorial Optimization Games (PCOGs). The input of PCOG consists of a set of agents and a combinatorial structure (typically a graph) with a fixed optimization goal on this structure (e.g., finding a minimum dominating set on a graph) such that the structure is divided among the agents. The value of each coalition of agents is derived from the optimal solution for the part of the structure possessed by the coalition. We study two fundamental questions related to the core: Core Stability Verification and Core Stability Existence. We analyze the algorithmic complexity of both questions for four classic graph optimization tasks: minimum vertex cover, minimum dominating set, minimum spanning tree, and maximum matching. |
| title | Partitioned Combinatorial Optimization Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2508.18449 |