.png){kind=icon}
.png){kind=icon}
Return
Solving coalitional resource games
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2009.09.005.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Coalitional Resource Games (CRGS) are a form of Non-Transferable Utility (NTU) game, which provide a natural formal framework for modelling scenarios in which agents must pool scarce resources in order to achieve mutually satisfying sets of goals. Although a number of computational questions surrounding CRGs have been studied, there has to date been no attempt to develop solution concepts for CRGS, or techniques for constructing solutions. In this paper, we rectify this omission. Following a review of the CRG framework and a discussion of related work, we formalise notions of coalition structures and the core for CRGs, and investigate the complexity of questions such as determining nonemptiness of the core. We show that, while such questions are in general computationally hard, it is possible to check the stability of a coalition structure in time exponential in the number of goals in the system, but polynomial in the number of agents and resources. As a consequence, checking stability is feasible for systems with small or bounded numbers of goals. We then consider constructive approaches to generating coalition structures. We present a negotiation protocol for CRGS, give an associated negotiation strategy, and prove that this strategy forms a subgame perfect equilibrium. We then show that coalition structures produced by the protocol satisfy several desirable properties: Pareto optimality, dummy player, and pseudo-symmetry. (C) 2009 Elsevier B.V. All rights reserved.
Keywords:
Coalitional games
NTU games
Solution concepts
The core
Bargaining
Algorithms
Complexity
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W