Source-linked AI summary
Cooperative Games with Overlapping Coalitions
Georgios Chalkiadakis, Edith Elkind, Evangelos Markakis, Maria Polukarov, Nicholas Robert Jennings
TL;DR
Task-oriented cooperation can require agents to divide resources among overlapping coalitions, a case conventional disjoint structures do not capture. The paper introduces OCF games and several core notions; under stated conditions it characterizes the c-core and shows its outcomes maximize social welfare.
Problem
Conventional coalition formation assumes either the grand coalition or disjoint coalitions, although task settings may require agents to divide resources among several coalitions.
Source: §1 · p. 2Method
The paper models overlapping coalition formation and develops three core notions that differ in the deviations agents may make.
Source: §1 · pp. 2–3Results
Under broad assumptions, c-core outcomes maximize social welfare, and convex OCF games have a non-empty c-core under mild assumptions.
Source: §1 · p. 3Takeaways & Limitations
The c-core characterization and generalized balancedness identify stable outcomes and coalition structures that can support them.
Source: §1 · p. 3, §6 · p. 17The construction procedure from the convexity proof is not polynomial-time in general, since its optimization questions are NP-hard for arbitrary convex games.
Source: §7 · p. 20
Abstract
from arXiv · showhide
In the usual models of cooperative game theory, the outcome of a coalition formation process is either the grand coalition or a coalition structure that consists of disjoint coalitions. However, in many domains where coalitions are associated with tasks, an agent may be involved in executing more than one task, and thus may distribute his resources among several coalitions. To tackle such scenarios, we introduce a model for cooperative games with overlapping coalitions--or overlapping coalition formation (OCF) games. We then explore the issue of stability in this setting. In particular, we introduce a notion of the core, which generalizes the corresponding notion in the traditional (non-overlapping) scenario. Then, under some quite general conditions, we characterize the elements of the core, and show that any element of the core maximizes the social welfare. We also introduce a concept of balancedness for overlapping coalitional games, and use it to characterize coalition structures that can be extended to elements of the core. Finally, we generalize the notion of convexity to our setting, and show that under some natural assumptions convex games have a non-empty core. Moreover, we introduce two alternative notions of stability in OCF that allow a wider range of deviations, and explore the relationships among the corresponding definitions of the core, as well as the classic (non-overlapping) core and the Aubin core. We illustrate the general properties of the three cores, and also study them from a computational perspective, thus obtaining additional insights into their fundamental structure.
1. Introduction
Task-based settings may require agents to divide resources among overlapping coalitions, which disjoint coalition structures cannot represent. The paper models such participation and studies core stability, including alternative deviation rules and computational questions.
1. Introduction
- Agents may split resources among task coalitions, so contributions can be fractional and coalition structures can overlap.The paper cites applications including multirobot coordination, computational grids, and sensor networks.Source: §1 · p. 2
- The model allows arbitrary transfers within coalitions but not across coalitions, and does not assume superadditivity or inevitable grand-coalition formation.It also represents coalitional task execution explicitly, facilitating possible extensions to uncertainty.Source: §1 · p. 2
- Three OCF-core notions vary according to which deviations are permitted and whether partial contributors retain payoff expectations from coalitions they do not fully abandon.A construction-project example illustrates how partial withdrawal can affect task completion and other partners' responses.Source: §1 · pp. 2–3
- Under broad assumptions, the c-core is characterized, every c-core outcome maximizes social welfare, and convex OCF games have a non-empty c-core under mild assumptions.The paper also generalizes balancedness to characterize coalition structures that admit c-core payoff allocations.Source: §1 · p. 3
- The paper relates the three OCF-cores to one another and the classic core, and distinguishes its model and core concepts from fuzzy coalitional games.It also begins computational analysis by introducing succinct threshold task games and studying core membership and non-emptiness complexity.Source: §1 · pp. 3–4
2. Preliminaries
The preliminaries set out conventional coalition structures, payoff allocations, and core stability. They also motivate retaining coalition structures rather than assuming the grand coalition.
2. Preliminaries
- A coalition structure in a non-overlapping setting is a partition of the agents, and an outcome pairs such a structure with an imputation.An imputation is efficient across the structure's coalitions and satisfies individual rationality.Source: §2 · p. 4
- The core consists of feasible outcomes that no subgroup of agents is motivated to leave for a deviation.The core is a strong stability notion and may be empty.Source: §2 · p. 4
- The paper does not assume superadditivity, because realistic or institutional constraints can make the grand coalition harmful, impossible, or less attractive than a coalition structure.Aumann & Dreze (1974) also explain how bargaining preferences and communication or legal constraints can lead coalition structures to arise.Source: §2 · p. 5
3. Related Work
Prior work covers fuzzy participation, overlapping-formation heuristics, and related value or equilibrium concepts, but leaves gaps addressed by this paper's game-theoretic treatment of overlap and stability.
3. Related Work
- Fuzzy games allow varying participation levels and define the Aubin core, but do not address formation of coalition structures.The paper later contrasts OCF games with fuzzy games because task execution is implicit in the latter's characteristic function.Source: §3 · p. 5
- Shehory and Kraus (1996) and Dang et al. (2006) study overlapping-formation heuristics, but do not address, respectively, stability or payoff allocation in a game-theoretic framework.Dang et al. (2006) consider surveillance multi-sensor networks.Source: §3 · p. 5
- Conconi and Perroni (2001) model overlapping international policy agreements and an equilibrium concept, but use a non-cooperative setting without continuous resources.Source: §3 · pp. 5–6
- Albizuri et al. (2006) characterize an extension of Owen's value to overlapping formation, without modeling resources distributed across coalitions.Source: §3 · p. 6
- Work on non-overlapping coalition structures studies resource allocation and stability, but does not extend these settings to overlapping coalitions.Examples include the bounded rational core of Sandholm and Lesser (1997) and stability notions for abstract games by Apt & Radzik (2006) and Apt & Witzel (2009).Source: §3 · p. 6
4. Our Model
The model represents each partial coalition by agents' resource contributions and permits overlapping coalition structures. It defines feasible agreements and payoffs while constraining resource use and payoff distribution.
4. Our Model
- An agent has one normalized resource unit to distribute among coalitions; contributions are fractions, and the model can extend to multiple resource types.For conciseness, the paper presents the single-resource case.Source: §4 · p. 6
- A partial coalition is a vector of agents' contribution fractions, with zero contribution marking non-membership; its value is assigned by the game function.The model assumes monotonicity for its stability discussion.Source: §4 · pp. 6–7
- A coalition structure is a finite list of partial coalitions whose members lie in the specified agent set and whose total contribution per agent is at most one.The list may contain identical partial coalitions, and agents need not allocate all their resources.Source: §4 · p. 7
- The value of a coalition structure aggregates the values of its partial coalitions, and v*(S) is the supremum value members of S can obtain by forming a structure.There may be infinitely many coalition structures, so enumeration cannot in general find a welfare maximum, which may not be attained.Source: §4 · p. 7
- An imputation distributes each partial coalition's payoff among its participants and requires each agent's total payoff to meet individual rationality based on v*(S).Cross-coalition transfers to outsiders are not allowed.Source: §4 · p. 8
- A feasible agreement pairs a coalition structure with an imputation, and the model defines each agent's payoff as the sum received across its coalitions.Source: §4 · p. 8
5. The Core with Overlapping Coalitions
The section develops three core notions for overlapping coalition formation, where partial withdrawals make it unclear whether deviators retain payoffs from coalitions with non-deviators. Threshold task games illustrate how resource splitting can improve attainable welfare.
5.1 Threshold Task Games
- Threshold task games model agents pooling a shared resource to complete tasks that pay their full utility when the team reaches a task-specific threshold.They serve as a running example for overlapping core stability; agents may split their weights across tasks.Source: §5 · p. 8, §5.1 · p. 9
- 2 versus 1: maximum social welfare is 2 in the overlapping example and 1 without overlap, because one agent can split weight across two coalitions.The example uses three agents of weight 2 and a task requiring weight 3.Source: §5.1 · pp. 9–10
- Allowing weight-splitting in any threshold task game yields maximum social welfare at least as high as without overlap, and the increase can be arbitrarily large.The passage illustrates the unbounded increase with one agent of weight w and a task with threshold and utility both equal to 1.Source: §5.1 · p. 10
5.2 Three Definitions of the Core
- Overlapping deviations can leave an agent contributing to some coalitions while abandoning or reducing contributions to others, complicating which existing payoffs remain available.The three core definitions differ in how they treat payoffs from partial coalitions involving non-deviators.Source: §5 · p. 8, §5.2 · p. 10
- The conservative core treats deviators as forming coalitions only among themselves, with no expected payoff from coalitions involving non-deviators.It models a pessimistic response in which withdrawing from one coalition may lead to losing collaboration in other coalitions as well.Source: §5.2 · pp. 10–11
- The refined core lets deviators retain payoffs from matched coalitions where their contributions remain unchanged, but withdraws those payoffs when they alter contributions.The deviators choose the matching between old and new partial coalitions that is most favorable to them.Source: §5.2 · p. 12
- The optimistic core lets deviators claim leftover payoff when a coalition with non-deviators switches tasks and still covers their original payoff.This assumes non-deviators care about their payoff rather than objecting to the task switch.Source: §5.2 · p. 13
6. Core Characterization
The section characterizes conservative-core outcomes through coalition-level payoff conditions and identifies when a fixed coalition structure can support a core allocation. These results imply social-welfare maximization by core outcomes under stated regularity conditions.
6. Core Characterization
- U-finiteness permits restricting relevant coalition structures to at most U partial coalitions, a bound that can reflect practical limits on collaboration complexity.Alternatively, the set of allowed outcomes or deviations can itself be restricted to structures with at most U partial coalitions.Source: §6 · pp. 14–15
- An outcome is in the c-core exactly when every agent subset receives total payoff at least as large as the maximum value that subset can achieve.The characterization assumes the value function is monotone, continuous, bounded, and the game is U-finite.Source: §6 · pp. 14–15
- The characterization proof uses a payoff-transfer graph: reachable agents from an overpaid agent cannot include an underpaid agent in the selected minimum-loss outcome.The reachable group can then form coalitions among themselves and improve every member's payoff.Source: §6 · p. 16
- Every outcome in the c-core maximizes social welfare.This follows by applying the subset-payoff characterization to the grand coalition.Source: §6 · pp. 15, 17
- The generalized balancedness criterion addresses whether a given coalition structure can be extended to an outcome in the core.It generalizes the classic question of when the grand coalition admits a core payoff allocation.Source: §6 · p. 17
- A coalition structure admits a c-core payoff allocation if and only if the game is balanced with respect to that structure.This equivalence assumes monotonicity, continuity, boundedness, and U-finiteness.Source: §6 · p. 17
- The balancedness expression is less simple than in the traditional superadditive setting because the core-allocation linear program requires more constraints.Source: §6 · p. 18
7. Convex OCF-Games Have a Non-Empty Core
The section generalizes convexity to OCF games as a feasible-agreement property and proves it sufficient for c-core non-emptiness under stated regularity assumptions. Its constructive proof adds agents sequentially while protecting earlier agents, but requires optimization that is NP-hard for arbitrary convex games.
7. Convex OCF-Games Have a Non-Empty Core
- OCF convexity requires that when R can join S without making S worse off, it can also join larger T while keeping T no worse off and R at least as well off.Unlike classical value-based convexity, this condition concerns feasible agreements and individual payoffs in a setting without full transferability.Source: §7 · pp. 18–19
- Convex OCF-games with continuous, bounded, monotone, U-finite value functions have a non-empty c-core.The paper presents convexity as a sufficient condition for c-core non-emptiness.Source: §7 · p. 19
- The proof constructs agreements in rounds, each time maximizing the incoming agent’s payoff subject to keeping earlier agents at least as well off.The assumptions on the value function ensure that the required maxima exist.Source: §7 · p. 19
- Inductively, each constructed agreement is in the core of its restricted game: excluded entrants contradict earlier stability, while deviations including the entrant contradict payoff maximization or convexity.The proof uses convexity when a blocking coalition includes the entrant and only some earlier agents.Source: §7 · pp. 19–20
- For arbitrary convex games, the construction is not polynomial-time because it requires a series of NP-hard optimization questions.The paper identifies finding classes of convex games with polynomial-time versions of these optimization problems as future work.Source: §7 · p. 20
8. Properties of the Three Cores
This section examines how the three OCF cores relate in their included outcomes and nonemptiness, and how they compare with non-overlapping and fuzzy-game cores. It also considers these relationships in threshold task games, including how standard and alternative fuzzy cores relate to OCF stability.
8. Properties of the Three Cores
- Every outcome in a TTG’s c-core maximizes social welfare.Theorem 5 extends this welfare result to the r-core and o-core under the paper’s stated technical conditions, but continuity means those conditions do not directly cover TTGs.Source: §8 · pp. 20–21
- For every OCF-game, o-core(G) ⊆ r-core(G) ⊆ c-core(G), and both inclusions can be strict.The paper gives outcomes in c-core but not r-core, and in r-core but not o-core.Source: §8 · p. 21
- Core nonemptiness can differ across these notions: some OCF-game has a nonempty c-core but empty r-core, while another has a nonempty r-core but empty o-core.These examples show the cores are not equivalent as game-level stability criteria, not merely different for individual outcomes.Source: §8 · pp. 22–23
8.1 Comparison with the Non-Overlapping Core
- A TTG can have an empty non-overlapping core but a nonempty o-core, or an empty c-core but a nonempty non-overlapping core.The paper attributes the first possibility to extra feasible overlapping outcomes and the reverse possibility to overlapping games allowing wider deviations.Source: §8.1 · pp. 24–25
8.2 Comparison with Fuzzy Games
- Unlike OCF outcomes, which specify a possibly overlapping coalition structure and payoffs, fuzzy games allow only the grand coalition; the Aubin core tests deviations to a partial fuzzy coalition, not a coalition structure.Coalition-structure formation is not addressed in the fuzzy-games framework.Source: §8.2 · p. 25
- A constructed fuzzy game can assign each partial coalition the best value achievable by splitting it into a coalition structure, corresponding to a social-welfare-maximizing OCF outcome for TTGs.The correspondence also holds for general OCF-games when the set of coalition-structure values attainable by the grand coalition is compact.Source: §8.2 · pp. 25–26
- Fuzzy representations hide which tasks produce a payoff and cannot represent suboptimal partial coalition structures, limiting analysis of coalition-formation processes.In TTGs, computing a partial coalition’s value is straightforward in OCF but hard in the fuzzy framework, where this is intertwined with optimization.Source: §8.2 · p. 26
- The standard fuzzy core can be empty even when a game is stable in practice because deviators assume the grand coalition retains scaled-down payoffs after they leave.In threshold task games, the remaining resources may be insufficient to complete any task, so the deviators may receive no payoff from the grand coalition.Source: §8.2 · p. 26
- A threshold task game can have a nonempty o-core while its corresponding fuzzy game has an empty fuzzy core.The standard fuzzy core can be overly optimistic about what remains of the grand coalition after a deviation, even when the OCF outcome is stable.Source: §8.2 · p. 26
- For threshold task games, an outcome is in the f-core exactly when its corresponding OCF outcome is in the c-core.This equivalence also holds for OCF games whose characteristic functions satisfy natural regularity conditions; in threshold task games, deviating coalition profit can be distributed arbitrarily among its members.Source: §8.2 · p. 27
- The fuzzy-game outcome description does not reveal which partial coalitions players belong to, so analogous r-core and o-core definitions are unclear.Without that membership information, one cannot determine which tasks a deviation affects.Source: §8.2 · p. 27
- Threshold task games illustrate natural settings where OCF games provide a more realistic and nuanced model than fuzzy games.Source: §8.2 · p. 27
9. Computational Aspects of Stability in Threshold Task Games
The section compares stability-checking complexity in threshold task games with and without overlapping coalitions. In the overlapping setting, the c-core admits polynomial-time algorithms under unary encoding, while checking stability in the r-core and o-core remains strongly hard.
9. Computational Aspects of Stability in Threshold Task Games
- The complexity analysis assumes game weights, thresholds, and task utilities are integers encoded in binary unless stated otherwise.The section also studies unary encoding, where parameters are at most polynomial in the number of players.Source: §9 · p. 28, §9.2 · p. 30
9.1 Games with Non-Overlapping Coalitions
- For non-overlapping TTGs with binary parameters, deciding whether the core is empty is coNP-hard, and checking outcome membership is coNP-complete, even with one task type of utility 1.With unary weights, outcome membership and stabilization of a given coalition structure are polynomial-time solvable.Source: §9.1 · p. 28
- In non-overlapping TTGs, binary-encoded parameters make core emptiness coNP-hard and outcome membership coNP-complete, even for one task type with utility 1.The unary-weight algorithms run in time polynomial in total weight and the payoff representation size.Source: §9.1 · p. 28
9.2 Games with Overlapping Coalitions
- With binary parameters, checking a given overlapping outcome is coNP-complete for the c-, r-, and o-cores, and strongly coNP-complete for the r- and o-cores.In the unary setting, checking c-core membership and testing whether the c-core is non-empty are polynomial-time solvable.Source: §9.2 · pp. 29, 30, 32
- With binary inputs, c-core membership is coNP-complete by reduction from UNBOUNDED KNAPSACK.The reduction makes a single player’s profitable deviation correspond to a knapsack solution meeting the target value.Source: §9.2 · p. 29
- For unary-encoded TTGs, a dynamic program checks c-core membership by comparing each coalition weight’s least current payoff with its maximum achievable task profit.A c-profitable deviation exists when the maximum task profit exceeds the least payoff for some weight.Source: §9.2 · p. 30
- The complexity results separate c-core checking from r-core and o-core checking because the latter deviations require choices about which existing coalitions to abandon.For o-core deviations, players may also reduce rather than fully withdraw their contributions.Source: §9.2 · pp. 30–31
- The c-core non-emptiness test selects a social-welfare-maximizing task set, constructs a coalition structure, and tests stabilization with a linear program.The linear program has exponentially many constraints but a polynomial-time separation oracle.Source: §9.2 · p. 32
10. Conclusions, Extensions, and Future Work
The paper concludes that overlapping coalitions support resource allocation across tasks, with core outcomes maximizing social welfare under the stated conditions. It also extends the framework to actions, multiple or discrete resources, and identifies computational and modeling questions for future work.
10. Conclusions, Extensions, and Future Work
- Under the paper’s conditions, every core outcome maximizes social welfare, and a coalition structure can be stabilized exactly when the game is balanced.The paper also shows that convex games have a non-empty core.Source: §10 · p. 33
10.1 Extensions
- Coalitions can be extended to choose actions, with their values depending on both members’ resource contributions and the selected action.The paper states that its definitions and results generalize to this setting.Source: §10.1 · p. 33
- The framework’s results also hold with multiple resource types, and the paper studies discrete contribution levels drawn from finite sets.In the discrete setting, the number of possible coalition structures is finite, and the definitions and theorems carry through with minor proof changes.Source: §10.1 · pp. 33–34
10.2 Future Work
- The paper identifies open problems in characterizing alternative cores, studying core non-emptiness, and finding practical processes for large overlapping configuration spaces.It also proposes studying infinite coalition structures and links between core outcomes and bargaining equilibria.Source: §10.2 · p. 34
- For arbitrary convex games, constructing a c-core element still requires solving optimization questions that are NP-hard.The paper identifies finding convex-game classes that permit polynomial-time construction as a future direction.Source: §10.2 · p. 34
Appendix A. Algorithmic Aspects of Social Welfare Maximization in TTGs
The appendix contrasts social-welfare maximization in non-overlapping and overlapping threshold task games. Overlapping optimization reduces to an unbounded-knapsack problem, while the stated decision problem is tractable for unary inputs or at most two task types.
Appendix A. Algorithmic Aspects of Social Welfare Maximization in TTGs
- For non-overlapping TTGs, deciding whether an outcome reaches a target social welfare is NP-complete, even with one task type and unary parameters.The result follows by reduction from 3-PARTITION.Source: Appendix A · p. 35
- Overlapping welfare maximization reduces to unbounded knapsack using the agents’ total weight; that problem is polynomial-time solvable for unary inputs or at most two items.Source: Appendix A · p. 36
- For overlapping TTGs, deciding whether an outcome reaches a target social welfare is NP-complete, but polynomial-time solvable with unary parameters or at most two task types.Source: Appendix A · p. 36