Coalitions on the Fly in Cooperative Games

Yao Zhang, Indrajit Saha, Zhaohong Sun, Makoto Yokoo · 2025

Read Coalitions on the Fly in Cooperative Games by Yao Zhang, Indrajit Saha, Zhaohong Sun, Makoto Yokoo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-11883.txt.

Introduction

Yao Zhang, Indrajit Saha, Zhaohong Sun, and Makoto Yokoo studied coalitions forming one arrival at a time in a 2025 paper. In their joint game, players show up sequentially and must decide on the spot: start a new coalition or join a current one. Then share the value the group creates. Players are greedy, maximizing their own reward from the information visible at arrival. The designer needs a payment rule, fixed in advance, that tempts selfish arrivals into building socially good coalitions anyway.

For monotone, bounded games the authors prove an upper bound on the competitive ratio any no-redistribution policy can achieve. Then give a policy reaching a near-optimal ratio expressed through the smallest and largest marginal contributions. Variants allowing redistribution are treated for limited player counts.

Catalog record

CREATORYao Zhang, Indrajit Saha, Zhaohong Sun, Makoto Yokoo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-11883

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Coalitions on the Fly in Cooperative Games Yao Zhang, Indrajit Saha, Zhaohong Sun, Makoto Yokoo Abstract 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 3 ​ 𝗆𝗂𝗇 𝗆𝖺𝗑 \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 ⁡ { 1 2 , 3 ​ 𝗆𝗂𝗇 𝗆𝖺𝗑 } \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. 1 Introduction Cooperative game theory, a classic area in game theory, considers how to distribute the value created by a coalition of players ( Driessen 2013 ; Shapley 1953 ; Von Neumann and Morgenstern 2007 ) . In real-world applications, two major concerns have been discussed in the literature. The first is that players may not be willing to form a grand coalition, even if every player brings a positive marginal contribution to the others. This can occur because additional players may play symmetric roles without generating enough extra earnings ( Aumann and Dreze 1974 ) . A key concept addressing this issue is the coalition structure , which allows players to form sub-coalitions next to a grand coalition ( Hart and Kurz 1983 ; Ueda et al. 2018 ) . The key challenges then include how to partition the players into a coalition structure and how to distribute the value generated by the coalitions while aiming for higher social welfare and satisfying properties such as stability, i.e., a player will not be attracted to another coalition. The second concern is that, in many scenarios, not all players are able to join the game at the beginning. That is, players may require invitations to join ( Zhang and Zhao 2022 ) , or they may arrive at different times, in an online manner ( Aziz et al. 2025 ; Ge et al. 2024 ) , so that players’ strategic behaviors must also be taken into account. In this paper, we consider scenarios where both concerns arise simultaneously—namely, the formation of coalition structures in an online manner. There are many real-world applications where it is realistic to assume that agents arrive over time and the entire input is not available from the beginning; for example, consider a regional economic plan initiated by the government, which aims to attract investment or launch projects across different markets or industries. In such a setting, people may arrive at different times and can choose to invest in or join an existing project, or to start a new one. Similarly, in the case of a large-scale social or experimental project involving multiple regions, new participants may join an already-formed group or establish a new local group as part of the expansion through recruitment, or people entering social networks. Other possible applications can also be found in ( Flammini et al. 2021 ) . All these scenarios suggest an online cooperative game with coalition structures. As with most cooperative games, we need to design a distribution policy to allocate the value earned by the players. Since players arrive sequentially and unpredictably, such a policy must be implementable in an online manner—this is also where the main challenge lies. The primary objective is to guide players in forming a coalition structure that maximizes social welfare, i.e., the total value created by all coalitions. Regarding players’ behaviors, we assume they have no prior knowledge of the future and must act myopically as greedy agents. More precisely, the key research question is: How to design an online policy that guides sequentially arriving greedy players to form coalitions that achieve near-optimal social welfare? Contributions. Within this setting, our key contributions as follows. • We introduce a model of online cooperative games with coalition structures, which considers how coalition structures are formed and how to guide players to form appropriate coalitions through policy design (Section 3 ). • In the domain of monotone and bounded cooperative games, involving greedy players, we provide upper and lower bounds on the worst-case competitive ratio for social welfare under irrevocable policies (where reallocation is not allowed). The lower bound is derived by allocating marginal contributions exceeding a threshold, which is very close to the proven upper bound (Section 4 ). • We also model online policies that are non-irrevocable. Here, we additionally consider a variant of greedy players and provide both upper and lower bounds of the competitive ratio in each case, as shown in Table 1 . Especially, without additional assumption indicated by (*), it shares the same bounds as above, which suggests that even when decisions are irrevocable, it is still possible to design a policy that achieves near-optimal social welfare, with a provable competitive ratio bound in general cases (Section 5 ). Outline. This paper is organized as follows. Section 2 briefly reviews related literature. Section 3 introduces the model and summarizes the main results. Sections 4 and 5 present the results for irrevocable and non-irrevocable policy designs, respectively. Finally, Section 6 concludes the paper and discusses future research directions. \alpha (UB/LB) V_{1} V_{2} V_{\geq 3} Irr 1/1[Thm 1 ] 1/1[Thm 3 ] \frac{3\mathsf{min}}{\mathsf{max}} [Thm 2 ]/ \min\left\{\frac{1}{2},\frac{3\mathsf{min}}{\mathsf{max}}\right\} [Thm 6 ] Irr + Na 1/1 -/ \frac{\mathsf{min}+\sqrt{\mathsf{min}(\mathsf{min}+4\mathsf{max})}}{2\mathsf{max}} [Thm 5 ] -/ \min\left\{\frac{1}{2},\frac{3\mathsf{min}}{\mathsf{max}}\right\} [Thm 6 ] Na + IR 1/1 - \frac{3\mathsf{min}}{\mathsf{max}} [Thm 7 ]/- Na (Greedy) 1/1 - \frac{3}{n} [Thm 8 ]/ \frac{2}{n} [Thm 9 ] (*) Na (Pessimistic) 1/1 - \frac{3}{n} [Thm 8 ]/ \frac{2}{n} [Thm 9 ] (*) Table 1: Results of Upper Bounds (UB) and Lower Bounds (LB) for worst-case Competitive Ratio in different classes of policies. Different columns indicate three subclasses of bounded monotone value functions according to how the maximum value is bounded. The last row introduces a variant of greedy players, which is called pessimistic. (*) means the bounds have an additional assumption that the number of players n\leq(\mathsf{max/\mathsf{min}})-1 . 2 Related Work 2.1 Cooperative Games with Coalition Structures The idea of a coalition structure is almost as old as traditional cooperative game theory itself ( Aumann and Dreze 1974 ) , and it remains one of the central considerations in the literature on cooperative games under various settings. For example, Chalkiadakis et al. 2010 considers overlapping coalition structures, where a player can belong to multiple coalitions. Kamijo 2009 characterizes a two-step Shapley value that accounts for the relationships between different coalitions. Many studies also investigate what a good coalition structure—one that yields high social welfare—might look like in specific types of

Read the complete text