Record link: 
http://hdl.handle.net/20.500.12708/225332
-
Title: 
Partitioned Combinatorial Optimization Games
en
Citation: 
Chen, J., Hatschka, C., & Simola, S. (2025). Partitioned Combinatorial Optimization Games. In I. Lynce, N. Murano, M. Vallati, S. Villata, F. Chesani, M. Milano, A. Omicini, & M. Dastani (Eds.), ECAI 2025 : 28th European Conference on Artificial Intelligence : Including 14th Conference on Prestigious Applications of Intelligent Systems (PAIS 2025). IOS Press. https://doi.org/10.3233/FAIA250962
-
Publisher DOI: 
10.3233/FAIA250962
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Chen, Jiehua 
Hatschka, Christian 
Simola, Sofia 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
ECAI 2025 : 28th European Conference on Artificial Intelligence : Including 14th Conference on Prestigious Applications of Intelligent Systems (PAIS 2025) 
-
ISBN: 
978-1-64368-631-8
-
Volume: 
413
-
DOI of the book: 
10.3233/FAIA413
-
Date (published): 
2025
-
Event name: 
28th European Conference on Artificial Intelligence (ECAI 2025) 
en
Event date: 
25-Oct-2025 - 30-Oct-2025
-
Event place: 
Bologna, Italy
-
Number of Pages: 
8
-
Publisher: 
IOS Press, Amsterdam
-
Peer reviewed: 
Yes
-
Keywords: 
partitioned combinatorial optimization games; graph optimization; core stability verification; core stability existence
en
Abstract: 
We propose a class of cooperative games, called PARTITIONED COMBINATORIAL 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.
en
Project title: 
Structural and Algorithmic Aspects of Preference-based Problems in Social Choice: VRG18-012 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds) 
-
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

9
checked on Jan 23, 2026

Google ScholarTM

Check