Fairness and Stability in Allocation-Induced Hedonic Games

1 Introduction

Game-theoretic concepts such as fairness and stability are receiving growing attention in the design of intelligent, cooperative systems. In domains ranging from multi-agent coordination to explainable AI (XAI), systems are expected to allocate value fairly while ensuring that agents have no incentive to deviate from their assigned coalitions. In cooperative game theory, fairness is often formalized via axiomatically characterized allocation rules such as the Shapley value, while stability is captured by solution concepts like the core or stable partitions in hedonic coalition formation games. These concepts, though historically distinct, now intersect in modern AI settings, particularly in multi-agent systems (MAS), where allocation mechanisms must satisfy both equity and strategic robustness.

Hedonic coalition formation games provide a foundational framework for modeling group formation and are widely applied in MAS [Chevaleyre et al., 2006; Aziz et al., 2013; Aziz and Savani, 2016; Jang et al., 2018; Caskurlu and Eser, 2025]. In these games, agents evaluate coalitions solely based on their members, independently of how others are grouped, a property termed hedonic preferences [Dr`eze and Greenberg, 1980]. Formal foundations were developed in [Farrell and Scotchmer, 1988; Banerjee et al., 2001; Bogomolnaia and Jackson, 2002]; for surveys, see [Hajdukov´a, 2006; Sung and Dimitrov, 2007; Aziz and Savani, 2016]. This framework is particularly suitable for studying how allocation rules induce coalition preferences.

We study a structured class of hedonic games in which agents derive preferences over coalitions from payoffs assigned by a fixed allocation rule applied to an underlying transferable utility (TU) game. In such settings, allocation rules play a structural role by shaping agents' incentives to deviate or form coalitions, and stability emerges endogenously from the induced preferences.

We focus on FX-FE strong Nash stability [Karakaya, 2011] (FX = free exit, FE = free entry; also referred to as strong Nash stability (SNS) of [Aziz and Brandl, 2012]), a stability concept requiring that no group of agents can jointly deviate-by moving to existing coalitions, to the empty set, or by freely reassigning themselves in any arrangement (including splitting into subgroups that join different coalitions or the empty set)-to strictly improve their payoffs under free-exit and free-entry membership rights, without needing permission from any agent.

Our contributions are threefold. First, we bridge the XAI literature-particularly SHAP as an allocation-based explanation method-and the MAS literature on coalition stability via a unified framework of allocation-induced hedonic games. Second, we prove that efficient allocation rules ensuring core membership (defined formally in Section 1.2) for the grand coalition induce FX-FE strongly Nash stable partitions, even if subcoalition allocations lie outside their cores. Third, we show that when Shapley lies outside the core, stability may fail, revealing a sensitive fairness-stability interaction.

These results suggest that fairness and stability are neither inherently conflicting nor automatically aligned; rather, their relationship depends on how fairness notions interact with the underlying game structure and induced coalition dynamics. This leads to the central question of the paper: If fairness is not aligned with stability, should we still want it when designing multi-agent systems? Our results suggest that the answer naturally depends on whether fairness is embedded via allocation rules that preserve coalition-level incentives.

1.1 Cooperative Games with Transferable Utility (TU Games)

Let N = {1, 2, . . . , n} be a finite set of players with n ≥ 2. Any non-empty subset S ⊆ N is called a coalition. A transferable utility game (or TU game) is a pair (N, v), where v : 2N → R is a characteristic function that assigns a realvalued worth v(S) to each coalition S, with the standard assumption that v(∅) = 0. The value v(S) represents the total utility the members of coalition S can achieve by cooperating [Moulin, 1988; Moulin, 2003].

For any coalition S ⊆ N, the subgame on S is the pair (S, vS ), where vS : 2S → R is defined by vS (T) = v(T) for all T ⊆ S. Note that for S = N, (N, vN ) ≡ (N, v).

A payoff vector for a coalition S ⊆ N is a vector xS ∈ R|S| assigning a payoff to each player i ∈ S. A coalition T ⊆ N is said to block a payoff vector xN ∈ Rn if its members can obtain a better outcome on their own, i.e., if v(T ) > ∑i∈T (xN )i .

Definition 1 (Core of a Game). The core is a solution concept applicable to any TU game [Gillies, 1953]. It identifies the set of payoff vectors that are both efficient and stable against blocking by any subcoalition. Formally, the core of a TU game (S, vS ), denoted by C(S, vS ), is the set:

The first condition states that the full value of coalition S is to be distributed, which is known as efficiency. The second condition ensures that no subcoalition can profitably secede and is known as coalition rationality or stability. The core of a game or any of its subgames may be empty.

1.2 Allocation Rules and Core Selection

While the core defines a set of stable allocations, an allocation rule (or value) provides a more decisive solution by selecting a single payoff vector for any given game. Formally, an allocation rule is a function Φ that maps a game (S, vS ) to a payoff vector Φ(S, vS ) ∈ R|S| .

An allocation rule Φ(S, vS ) is efficient if ∑i∈S Φi(S, vS ) = v(S) for all (S, vS ). Efficiency is a standard property required of most prominent allocation rules in the literature.

A key question is how a rule relates to the core. This relationship can be characterized by a strong, universal property or a weaker, local one.

Definition 2 (Core-Selective Rule). An allocation rule Φ is core-selective if, for any game (S, vS ) with a non-empty core, the assigned payoff vector is an element of the core. That is:

Being core-selective is a powerful, global property, as it must hold for all games. Many prominent rules, like the Shapley value, are not core-selective. This motivates a weaker, localized notion.

Definition 3 (Core Membership). An allocation rule Φ provides a core-member for a specific game (S, vS ) if its allocation for that game is an element of the core:

The Shapley value, for example, is not core-selective in general, but it does provide a core-member in every convex game (S, vS ).

This distinction is critical. This highlights the difference between a rule being core-selective (holding across all games) and providing a core-member (for a single game). Our analysis relies on this weaker, game-specific property, and for brevity, we say that an allocation "lies in the core" of a specific game.

1.3 The Shapley Value and Convex Games

A central focus of our analysis is the Shapley value [Shapley, 1953], a prominent allocation rule uniquely characterized by four axioms: efficiency, symmetry, additivity and the null player property. It distributes the total worth of a coalition based on each player's average marginal contribution. Formally, for each player i ∈ S:

Despite its strong fairness properties, the Shapley value is not core-selective, but it does provide a core-member for each convex game (S, vS ).

Definition 4 (Convex TU Game). A TU game (S, vS ) is convex if it exhibits increasing marginal returns, meaning a player's incentive to join a coalition grows as the coalition itself grows. An equivalent condition, known as supermodularity, requires that for any two coalitions M,N ⊆ S: v(M) + v(N) ≤ v(M ∪ N) + v(M ∩ N).

A seminal result by [Shapley, 1971] connects these concepts, establishing that the Shapley value of a convex game always lies in the core. This, in turn, proves that convexity is a sufficient condition for a TU game to have a non-empty core.

Subsequently, the notion of convexity was generalized to average convexity by [Inarra and Usategui, 1993]. While we omit the technical details here, average convexity provides a weaker condition than convexity that still ensures the Shapley value is a core-member, thereby characterizing a broader class of games for which the core-membership property still holds.

1.4 Hedonic Games and Stability

The final component of our framework is the hedonic game, which models how agents form coalitions based on their own preferences. In a hedonic game, agents are concerned only with the members of their own coalition and do not consider how other agents form groups.

Formally, a hedonic coalition formation game (or simply a hedonic game) is a pair (N,⪰), where N is a finite set of players and ⪰= (⪰i)i∈N is a profile of preferences. For each player i ∈ N, the preference relation ⪰i is a complete and transitive ordering over Σi = {S ⊆ N | i ∈ S}, the set of all coalitions that contain the player i. As usual, for each player i, strict preferences are denoted by ≻i and indifference by ∼i, both derived from the weak preference relation ⪰i. Formally, for each player i, the strict preference relation ≻i is defined by x ≻i y if and only if x ⪰i y and not y ⪰i x, while indifference ∼i holds when x ⪰i y and y ⪰i x.

A central objective in hedonic games is to identify stable partitions. The stability of a partition is evaluated based on its resilience to deviations. While many such stability concepts exist, we focus on three foundational and related notions: Nash stability, core stability, and the more general FXFE strong Nash stability.

Individual Deviations and Nash Stability

The most basic deviation is a movement by a single player. When a player i leaves her current coalition π(i) and joins another existing coalition H ∈ (π ∪ {∅}) (or forms a new coalition by herself by joining the empty set), she induces a new partition π′ . We say that π′ is reachable from π via player i, denoted π i-→ π′ . A player i ∈ N Nash blocks a partition π if there exists a coalition H ∈ (π ∪ {∅}) such that H ∪ {i} ≻i π(i).

Definition 5 ((FX-FE) Nash Stability). A partition π is FXFE Nash stable if there does not exist a player who Nash blocks it. This corresponds to the standard definition of Nash stability in the literature, where a player can freely exit her coalition and freely enter another without asking permission.

Group Deviations and Stronger Stability Concepts

More powerful stability notions allow coordinated deviations by groups of players. A classical example is core stability, which permits a group to deviate only by jointly forming a new stand-alone coalition, i.e., each agent in the group leaves their current coalition and then they form a single new coalition among themselves.

Definition 6 (Core Stability). A partition π is core stable if there does not exist a coalition T ⊆ N such that for all i ∈ T , T ≻i π(i). If such a coalition T exists, then we say that T blocks π.

Although core stability is a powerful concept, it imposes a restriction: any blocking group must form a new standalone coalition and is not permitted to join existing ones or exchange their current coalitions. Our work instead focuses on a more general and demanding stability notion introduced by [Karakaya, 2011].

To formalize this, we define a movement by a group H ⊆ N, which generalizes the notion of a single-player movement.

A partition π′ (π′ ̸= π) is reachable from π by movements of the players in H, denoted by π H -→ π′ , if, for all i, j ∈ (N \ H) with i ̸= j, π(i) = π(j) ⇔ π′ (i) = π′ (j). That is, (π H -→ π′ ) if each player not in H (a non-deviating agent) stays grouped with all their previous partners who are also non-deviators, while the players in H are free to leave their current coalitions and freely reorganize in any way they want. Based on this, we define our central group stability concept.

Definition 7 (FX-FE Strong Nash Stability). A partition π is FX-FE strongly Nash stable if there does not exist a pair (π′ , H), where π′ ̸= π and ∅ ̸= H ⊆ N, such that:

• (i) π H -→ π′ (π′ is reachable from π by movements of H), and
• (ii) for all i ∈ H, π′ (i) ≻i π(i) (all agents in the deviating coalition H be strictly better off.)

If such a pair (π′ ,H) exists, then we say that H FX-FE strongly Nash blocks π.

This stability concept is particularly strong, which we refer to as FX-FE strong Nash stability. It is equivalent to the strong Nash equilibrium of a non-cooperative game induced by the hedonic game. Moreover, any FX-FE strongly Nash stable partition is both core and Nash stable. However, a partition that is either core or Nash stable may not be FX-FE strongly Nash stable (see Example 1).

1.5 Model: Allocation-Induced Hedonic Games

We consider a setting that connects transferable utility (TU) games with hedonic games by deriving each player's preferences over coalitions not abstractly, but endogenously from a fixed allocation rule. Specifically, we focus on a class of hedonic games in which each player's preferences over coalitions are induced by the payoff they would receive from applying an allocation rule to the relevant subgame.

Given a TU game (N, v) and an allocation rule Φ, player i ∈ N compares any two coalitions S, S′ ∈ Σi based on the payoff they would receive from Φ in each corresponding subgame (similar to [Maga˜na and Carreras, 2018]).

Formally, a TU game (N, v) and an allocation rule Φ induce a preference profile ⪰(v,Φ) as follows: for each player i ∈ N and any two coalitions S, S′ ∈ Σi:

For simplicity, we henceforth write ⪰i to denote the induced preference relation. All previously introduced stability concepts-namely, Nash stability, core stability, and FX-FE strong Nash stability-are also well-defined within the context of the allocation-induced hedonic games.

Example 1. (A motivating example) The following example can be interpreted as a heterogeneous multi-agent system in which agents differ in capabilities or roles, with two pairs of agents sharing similar characteristics. Such structures arise naturally in team formation and collaborative multiagent systems where partnerships differ in productivity. Consider the following 4-player TU game with N = {1, 2, 3, 4}: v({1, 3}) = 8, v({1, 4}) = 10, v({2, 3}) = 14, v({2, 4}) = 12, and v(S) = 0 otherwise.

To determine the induced hedonic game via Shapley value and analyze its stability, we compute Shapley values of each player at each possible subgame to drive preferences. Shapley values for all non-singleton, non-trivial subgames are shown in Table 1.

These payoffs induce the following preference orderings:

With the preference profile above:

• (i) π1 = {{1, 3}, {2, 4}} is FX-FE Nash stable, but neither FX-FE strongly Nash stable nor core stable: No single agent can move to an existing coalition or to a singleton and strictly improve, so FX-FE Nash stability holds. However, it fails FX-FE strong Nash and core stability since players 2 and 3 both strictly prefer to form {2, 3}.
• (ii) π2 = {{2, 3}, {1, 4}} is FX-FE strongly Nash stable, hence also FX-FE Nash and core stable: Except player 4, every other player prefers their top coalitions. Player 4 may prefer to form {2, 4}, but player 2 strictly prefers her current coalition to {2, 4}, thus refuses. Since no deviating coalition is unanimously preferred by its members, π2 is FX-FE strongly Nash stable, and thus FX-FE Nash and core stable.
• (iii) Every other partition fails FX-FE Nash stability, and therefore also fails core stability and FX-FE strong Nash stability, as FX-FE Nash stability is weaker than both: In any other partition, at least one lone player has a strictly preferred existing coalition and can deviate unilaterally, violating FX-FE Nash stability and consequently also the stronger notions.

2 Guaranteed Stability from Core-membership

We emphasize the precise requirements placed on the allocation rule Φ. Our main condition requires that the allocation for the grand game, Φ(N, v) lies in the core C(N, v). However, for any proper subgame (S, vS ), we do not require the corresponding allocation Φ(S, vS ) to lie in the subgame's core C(S, vS ). We only impose the standard condition of efficiency on all subgames. This distinction is key, as it shows that hedonic stability can be achieved even if the allocation rule does not provide core-membership within smaller, deviating coalitions. The following theorem identifies conditions under which allocation-induced fairness notions are compatible with FX-FE strong Nash stability induced by allocationbased preferences.

Theorem 1. Let Φ be an allocation rule that is efficient on all subgames of a game (N, v) and be a core-member for (N, v). In the induced hedonic game (N, ⪰) derived from (N, v) and Φ, the partition consisting of the grand coalition, π = {N}, is an FX-FE strongly Nash stable partition.

Proof. We prove by contradiction. Assume that under the conditions of the theorem, the grand coalition π = {N} is not an FX-FE strongly Nash stable partition in the induced hedonic game (N, ⪰).

By the definition of FX-FE strong Nash stability, this assumption implies that there exists a deviating coalition H ⊊ N and a partition π′ (π′ ̸= π) such that π H -→ π′ and for all i ∈ H, π′ (i) ≻i π(i). The only possible movements for H in π = {N} are for agents in H to leave N and form their own coalition H, or possibly form a partition among themselves-which includes the former case as well-, i.e., π′ = {H1,H2, . . .Hk,N \H} where {H1,H2, . . . ,Hk} is a partition of H for some k ≥ 1. Thus, by definition, for each j ∈ {1, . . . , k} and for each i ∈ Hj ,

For each j ∈ {1, . . . , k}, summing this inequality over all players i within a single subcoalition Hj , we get:

By the hypothesis of the theorem, the allocation rule Φ is efficient on all subgames. Applying this to the subgame (Hj, vHj ), the left-hand side of (2) simplifies to:

Furthermore, we have that Φ(N, v) lies in the core C(N, v). By the definition of the core, this allocation must satisfy the coalitional rationality constraint for all coalitions, including any Hj :

Now, substituting (3) into (2) yields:

This result directly contradicts the core condition in (4).

Therefore, the initial assumption must be false. No such deviating coalition H can exist. Thus, π = {N} is an FX-FE strongly Nash stable partition.

Notably, core membership is required only for the grand coalition. Since FX-FE strong Nash stability is stronger than both Nash stability and core stability, our result also implies these weaker stability notions. 1 Theorem 1 confirms that core-membership criteria can translate into FX-FE strong Nash stability under our model.

By Theorem 1, we obtain the following corollaries. These results collectively show that the grand coalition partition, which is often considered to form from the perspective of cooperative game theory, also exhibits strong stability properties when evaluated through the lens of hedonic games derived from a fixed allocation rule.

Corollary 1. Let Φ be an efficient core-selective allocation rule. Then for any TU game (N, v) with a non-empty core, π = {N} is an FX-FE strongly Nash stable partition in the hedonic game induced by (N, v) and Φ.

This result implies that any core-selective rule ensures strong stability of the grand coalition whenever the core is non-empty. Examples include the nucleolus [Schmeidler, 1969] and the per-capita nucleolus [Grotte, 1970; Moulin, 1988], both inducing FX-FE strongly Nash stable outcomes.

Corollary 2. Let (N, v) be a TU game. If the Shapley value of (N, v) lies in the core of v, then in the hedonic game induced by (N, v) and the Shapley value, π = {N} is an FXFE strongly Nash stable partition.

The Shapley value ensures stability whenever it lies in the core, as in average convex games [Inarra and Usategui, 1993]. Since it always lies in the core of convex games, we also have:

Corollary 3. If (N, v) is a convex game, then in the hedonic game induced by (N, v) and the Shapley value, π = {N} is an FX-FE strongly Nash stable partition.

3 The Shapley Value and the Nuance of Stability

The preceding results establish a sufficient condition for stability: in particular, when the Shapley value lies in the core, the grand coalition is guaranteed to be FX-FE strongly Nash stable. We now examine cases where this condition fails, either because the Shapley value is outside the core or because the core is empty. As this section demonstrates, the stability guarantee breaks down and the outcome becomes highly sensitive to the specific structure of the game.

We first consider the case where the core is non-empty but the Shapley value lies outside it. As the next result shows, stability need not be lost.

1 Our result also applies to strictly strong Nash stability (SSNS) as defined by [Aziz and Brandl, 2012], which allows group deviations even if some agents are indifferent. Since our contradiction arises from a violation of core constraints by any subcoalition containing at least one strictly better-off agent, it also rules out such weakly blocking deviations. Furthermore, any partition that is stable under FX-FE cannot be blocked under weaker membership rights, including FX-AE (free exit-approved entry), AX-FE (approved exit-free entry), and AX-AE (approved exit-approved entry), as defined by [Karakaya, 2011]. Hence, our result extends to these variants of strong Nash stability notions as well.

Theorem 2. There exists a TU game (N, v) such that:

• (i) The core C(N, v) is non-empty.
• (ii) The Shapley value Sh(N, v) is not a core-member for (N, v) .
• (iii) The hedonic game induced by (N, v) and the Shapley value has an FX-FE strongly Nash stable partition.

Proof. We prove this constructively with the classic 3-player glove game. Let N = {1, 2, 3}, where players 1 and 2 each has a right-hand glove and player 3 has a left-hand glove. A coalition achieves a worth of 1 if it contains a pair of gloves, and 0 otherwise. The characteristic function is therefore: v({1, 3}) = v({2, 3}) = v(N) = 1, and v(S) = 0 for all other coalitions S.

The core is non-empty, C(N, v) = {(0, 0, 1)}. The Shapley value for the grand game is Sh(N, v) = ( 1 6 , 16 , 23 ) which is clearly not a core-member. For subgame S = {1, 3} or S = {2, 3}, Sh(S, vS ) = ( 1 2 , 12 ).

These payoffs induce the following preference orderings:

We now test the stability of the grand coalition: For a coalition T to deviate, all its members must strictly prefer T to N. However, while player 1 would prefer to form {1, 3}, player 3 would not. Similarly, while player 2 would prefer to form {2, 3}, player 3 would again refuse. Since no deviating coalition is unanimously preferred by its members, {{1, 2, 3}} is an FX-FE strongly Nash stable partition.

This result is crucial: it shows that the core-membership condition is sufficient for stability, but not necessary. However, the existence of such a game does not imply a general guarantee. The following complementary result demonstrates that, in a similar setting, the opposite outcome is also possible.

Theorem 3. There exists a TU game (N, v) such that:

• (i) The core C(N, v) is non-empty.
• (ii) The Shapley value Sh(N, v) is not a core-member for (N, v).
• (iii) The hedonic game induced by (N, v) and the Shapley value does not have any FX-FE strongly Nash stable partition.

Proof. For this, we use an example adapted from [Maga˜na and Carreras, 2018]. 2 Consider: v({i}) = 0, v({1, 3}) = v({2, 3}) = 1, and v({1, 2}) = v({1, 2, 3}) = 6.

• (i) The core is non-empty; e.g., (3, 3, 0) ∈ C(N, v).
• (ii) The Shapley value, Sh(N, v) = ( 17 6 , 17 6 , 26 ), is not in the core, because player 3's allocation is positive, whereas any core allocation requires x1 +x2 = v({1, 2}) = 6, implying x3 = 0.

2 The hedonic stability notion of [Maga˜na and Carreras, 2018] differs from ours; in this example, the partition {{1, 2}, {3}} is regarded as stable under their framework.

(iii) To analyze the induced hedonic game and its stability, we compute Shapley values for all non-singleton subgames to derive preferences, as shown in Table 2. These payoffs induce

the following preference orderings:

An analysis of these preferences shows that no partition is stable: The coalition {1, 2} is the top choice for both players 1 and 2, meaning any stable partition must contain it. This leaves only π′ = {{1, 2}, {3}}. However, π′ is itself unstable, since coalition {3} would be better off by joining {1, 2}. Thus, there is no FX-FE strongly Nash stable partition.

Together, Theorems 2 and 3 establish a fundamental indeterminacy: when the Shapley value is not a core-member for (N, v), stability is possible but not assured. To complete our analysis, we now examine the most extreme case of instability in the underlying TU game: when the core is empty.

Theorem 4. There exists a TU game (N, v) such that:

• (i) The core C(N, v) is empty.
• (ii) The hedonic game induced by (N, v) and the Shapley value has an FX-FE strongly Nash stable partition.

Proof. Consider the following 3-player game:

• (i) Core: The core C(N, v) is empty. For instance, the balanced coalition collection B = {{1, 2}, {3}} with weights δ{1,2} = 1, δ{3} = 1 violates the Bondareva-Shapley [Bondareva, 1962; Shapley, 1967] condition, as x1 + x2 + x3 ≥ δ{1,2}v({1, 2}) + δ{3}v({3}) = 5 > α = v(N).

(ii) Hedonic Game and Stability:

This induces the following preferences:

We now test the stability of the grand coalition: For a coalition T to deviate, all its members must strictly prefer T to N. However, while player 2 would prefer to form {1, 2}, player 1 would not. Similarly, while player 3 would prefer to form {1, 3}, player 1 would again refuse. Since no deviating coalition is unanimously preferred by its members, {{1, 2, 3}} is an FX-FE strongly Nash stable partition.

Remark 1. The stability outcome of this game is highly sensitive to the value of α. In all cases where α < 5, the core of the underlying TU game is empty. In particular:

• (i) When α = 4, the induced preferences differ from those in Theorem 4, yet {{1, 2, 3}} remains to be an FX-FE strongly Nash stable partition.
• (ii) When 1 < α < 4, the preferences differ from both case (i) and Theorem 4. In this range, the only FX-FE strongly Nash stable partitions are {{1, 2}, {3}} and {{1, 3}, {2}}.
• (iii) When α < 1, the induced preferences again differ from all previous cases. Nevertheless, the only FX-FE strongly Nash stable partitions are again {{1, 2}, {3}} and {{1, 3}, {2}}.

Such diverse outcomes in an empty-core setting demonstrate that Shapley's fairness insights can produce unexpectedly varied stability patterns, even when the core provides no solutions. However, as before, this possibility is not a certainty.

Theorem 5. There exists a TU game (N, v) such that:

• (i) The core C(N, v) is empty.
• (ii) The hedonic game induced by (N, v) and the Shapley value does not have any FX-FE strongly Nash stable partition.

Proof. For this final case, we use the following 3-player TU game from [Aumann and Dr`eze, 1974], which has an empty core. The game is defined by: v({i}) = 0 for all i ∈ N, v({1, 2}) = v({1, 3}) = v({2, 3}) = 8, and v(N) = 9.

The Shapley value for the grand coalition is (3, 3, 3), while for any two-player subgame, it is (4, 4). This induces the following preferences:

From these preferences, it is clear that no partition can be stable. Any partition with a lone player (i.e. any {{i, j}, {k}} or {{1}, {2}, {3}}) is unstable because that player would rather join another. The grand coalition is also unstable because any pair of players would rather leave to form their own, more valuable coalition. Thus, no FX-FE strongly Nash stable partition exists.

The findings in this section reveal a clear dichotomy. Figure 1 provides a brief summary of the section, illustrating the conditions under which stable partitions are guaranteed, merely possible, or may not exist at all.

4 RelatedWork

Our research contributes to a growing body of work at the intersection of cooperative game theory and explainable or trustworthy AI. The Shapley value plays a central role in this discourse, serving as both a normative standard for fair resource allocation in MAS [Heuillet et al., 2022; Gray et al., 2023; Li et al., 2024] and a foundation for interpretability via SHAP [Lundberg and Lee, 2017; Nizri et al., 2022; Salih et al., 2025]. While a large body of recent literature has explored the axiomatic foundations and computational challenges of approximating the Shapley value [Zhou et al., 2023; Li et al., 2024], its downstream effects on agent behavior and system stability remain a critical, underexplored area.

Our approach is partially motivated by recent critiques of the Shapley value in AI contexts. For instance, [Li et al., 2024] highlight the model sensitivity of Shapley, i.e., small perturbations in data or models can induce significant instability in computed values. Similarly, [Yan and Procaccia, 2021] propose replacing Shapley with alternative solution concepts to better align fairness with stability. Acknowledging the value of these critiques while taking a complementary direction, we retain the Shapley rule and investigate the conditions under which it continues to support stability. This leads to a different type of contribution, namely not by discarding Shapley's fairness principle, but by understanding its structural limits and the precise conditions under which it ensures strategic robustness. In doing so, we develop a framework that bridges core stability (in TU games) and hedonic coalition stability.

This positions our work firmly within the literature on coalition formation in MAS, and more specifically, within the theory of hedonic games [Burani and Zwicker, 2003; Aziz and Brandl, 2012; Suksompong, 2015; C¸ as¸kurlu et al., 2023], which are extensively studied in artificial intelligence settings, including MAS and swarm robotics [Aziz et al., 2013; Lang et al., 2015; Bil`o et al., 2018; Jang et al., 2018; Czarnecki and Dutta, 2021], as well as more generalized models [Darmann et al., 2012; Darmann et al., 2018]. These works often assume externally defined agent preferences or impose structural restrictions on the domain. In contrast, our contribution is to study how the choice of allocation rule itself-specifically, the Shapley value-can endogenously induce preferences and thereby shape coalition stability.

5 Conclusion

We established a formal bridge between two fundamental stability paradigms: the centralized, cooperative stability guaranteed by the core, and the decentralized, non-cooperative stability of FX-FE strong Nash partitions in the hedonic games they induce. Our findings show that while coremembership of an efficient allocation is a sufficient condition for stability, its absence-a common case for the Shapley value-leads to a structural indeterminacy that the induced hedonic game may or may not have an FX-FE strongly stable partition. These results highlight a fundamental trade-off, or limitation in multi-agent systems: fairness guarantees alone do not ensure strategic robustness across diverse domains and applications. The choice of an allocation rule is not merely a normative decision but a critical design parameter that directly shapes the structure of agents' strategic interactions.

6 Outlook and Open Questions

Our findings open several avenues for future research at the intersection of cooperative game theory and AI. Below are a few illustrative open questions.

• Beyond Sufficient Conditions: Core-membership is a sufficient condition for FX-FE strong Nash stability, but establishing necessary conditions or a sharper characterization remains an open problem.
• Dynamic Stability: Following work in evolving coalition structures [Bullinger and Romen, 2024; Boehmer et al., 2025; Fanelli et al., 2025], whether agents under non-core Shapley allocations converge to stable outcomes or cycle remains open. Our Theorems 2-5 show both possibilities exist, rather than guaranteeing convergence.
• Computational Tractability: Determining whether a specific TU game induces a stable hedonic game under Shapley-induced preferences appears to be computationally hard. Following [Peters, 2016], identifying tractable subclasses or effective approximation heuristics remains crucial for practical deployment.
• Constrained Systems: Inspired by [Deligkas et al., 2025], a future direction is extending our results to constrained systems (networked/spatial) where agents only form coalitions within their local neighborhood.

We hope these directions stimulate further exploration into the essential interplay of fairness and stability in the design of autonomous, cooperative AI systems.

Acknowledgments

The author thanks Mehmet Karakaya and Bu˘gra C¸ as¸kurlu for helpful discussions on hedonic games.