Approximating the Core via Iterative Coalition Sampling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916117058945024 |
|---|---|
| author | Gemp, Ian Lanctot, Marc Marris, Luke Mao, Yiran Duéñez-Guzmán, Edgar Perrin, Sarah Gyorgy, Andras Elie, Romuald Piliouras, Georgios Kaisers, Michael Hennes, Daniel Bullard, Kalesha Larson, Kate Bachrach, Yoram |
| author_facet | Gemp, Ian Lanctot, Marc Marris, Luke Mao, Yiran Duéñez-Guzmán, Edgar Perrin, Sarah Gyorgy, Andras Elie, Romuald Piliouras, Georgios Kaisers, Michael Hennes, Daniel Bullard, Kalesha Larson, Kate Bachrach, Yoram |
| contents | The core is a central solution concept in cooperative game theory, defined as the set of feasible allocations or payments such that no subset of agents has incentive to break away and form their own subgroup or coalition. However, it has long been known that the core (and approximations, such as the least-core) are hard to compute. This limits our ability to analyze cooperative games in general, and to fully embrace cooperative game theory contributions in domains such as explainable AI (XAI), where the core can complement the Shapley values to identify influential features or instances supporting predictions by black-box models. We propose novel iterative algorithms for computing variants of the core, which avoid the computational bottleneck of many other approaches; namely solving large linear programs. As such, they scale better to very large problems as we demonstrate across different classes of cooperative games, including weighted voting games, induced subgraph games, and marginal contribution networks. We also explore our algorithms in the context of XAI, providing further evidence of the power of the core for such applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03928 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating the Core via Iterative Coalition Sampling Gemp, Ian Lanctot, Marc Marris, Luke Mao, Yiran Duéñez-Guzmán, Edgar Perrin, Sarah Gyorgy, Andras Elie, Romuald Piliouras, Georgios Kaisers, Michael Hennes, Daniel Bullard, Kalesha Larson, Kate Bachrach, Yoram Computer Science and Game Theory Multiagent Systems The core is a central solution concept in cooperative game theory, defined as the set of feasible allocations or payments such that no subset of agents has incentive to break away and form their own subgroup or coalition. However, it has long been known that the core (and approximations, such as the least-core) are hard to compute. This limits our ability to analyze cooperative games in general, and to fully embrace cooperative game theory contributions in domains such as explainable AI (XAI), where the core can complement the Shapley values to identify influential features or instances supporting predictions by black-box models. We propose novel iterative algorithms for computing variants of the core, which avoid the computational bottleneck of many other approaches; namely solving large linear programs. As such, they scale better to very large problems as we demonstrate across different classes of cooperative games, including weighted voting games, induced subgraph games, and marginal contribution networks. We also explore our algorithms in the context of XAI, providing further evidence of the power of the core for such applications. |
| title | Approximating the Core via Iterative Coalition Sampling |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2402.03928 |