Coalitions on the Fly in Cooperative Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912484960501760 |
|---|---|
| author | Zhang, Yao Saha, Indrajit Sun, Zhaohong Yokoo, Makoto |
| author_facet | Zhang, Yao Saha, Indrajit Sun, Zhaohong Yokoo, Makoto |
| contents | In this work, we examine a sequential setting of a cooperative game in which players arrive dynamically to form coalitions and complete tasks either together or individually, depending on the value created. Upon arrival, a new player as a decision maker faces two options: forming a new coalition or joining an existing one. We assume that players are greedy, i.e., they aim to maximize their rewards based on the information available at their arrival. The objective is to design an online value distribution policy that incentivizes players to form a coalition structure that maximizes social welfare. We focus on monotone and bounded cooperative games. Our main result establishes an upper bound of $\frac{3\mathsf{min}}{\mathsf{max}}$ on the competitive ratio for any irrevocable policy (i.e., one without redistribution), and proposes a policy that achieves a near-optimal competitive ratio of $\min\left\{\frac{1}{2}, \frac{3\mathsf{min}}{\mathsf{max}}\right\}$, where $\mathsf{min}$ and $\mathsf{max}$ denote the smallest and largest marginal contribution of any sub-coalition of players respectively. Finally, we also consider non-irrevocable policies, with alternative bounds only when the number of players is limited. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_11883 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coalitions on the Fly in Cooperative Games Zhang, Yao Saha, Indrajit Sun, Zhaohong Yokoo, Makoto Computer Science and Game Theory In this work, we examine a sequential setting of a cooperative game in which players arrive dynamically to form coalitions and complete tasks either together or individually, depending on the value created. Upon arrival, a new player as a decision maker faces two options: forming a new coalition or joining an existing one. We assume that players are greedy, i.e., they aim to maximize their rewards based on the information available at their arrival. The objective is to design an online value distribution policy that incentivizes players to form a coalition structure that maximizes social welfare. We focus on monotone and bounded cooperative games. Our main result establishes an upper bound of $\frac{3\mathsf{min}}{\mathsf{max}}$ on the competitive ratio for any irrevocable policy (i.e., one without redistribution), and proposes a policy that achieves a near-optimal competitive ratio of $\min\left\{\frac{1}{2}, \frac{3\mathsf{min}}{\mathsf{max}}\right\}$, where $\mathsf{min}$ and $\mathsf{max}$ denote the smallest and largest marginal contribution of any sub-coalition of players respectively. Finally, we also consider non-irrevocable policies, with alternative bounds only when the number of players is limited. |
| title | Coalitions on the Fly in Cooperative Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.11883 |