Stability and Efficiency in Hedonic Project Games

1 Introduction

It is the beginning of a new semester in a university research department. The head of the department introduces a set of m new research projects, each associated with its own funding and rewards, and invites n researchers, each of whom can join exactly one project. As you enter the meeting room, you see that several researchers have already chosen some projects. You would like to choose a project that maximizes your own share of the reward while also considering the colleagues involved: you may prefer to collaborate with close friends or perhaps reconnect with colleagues you have not worked with recently. This scenario captures a fundamental tension absent from most existing models: agents care simultaneously about what they work on and with whom they work. Your decision depends not just on the project's reward, but on how that reward is shared and whether your teammates enhance or diminish your experience. What should you choose? And when everyone reasons similarly, what outcomes emerge, and are they efficient?

In many multi-agent environments, agents face a dual and fundamentally conflicting incentive structure. On the one hand, they compete over objective, divisible resources (funding, rewards, or values), whose value is diluted by congestion and rival participation [Valizadeh and Telikani, 2026; Valizadeh et al., 2025a]. On the other hand, they cooperate within coalitions whose composition directly affects individual satisfaction, productivity, or compatibility through subjective preferences over teammates. Existing models typically capture only one side of this tension. The congestion games [Rosenthal, 1973], project games [Bil`o et al., 2023], market sharing games [Goemans et al., 2004] model competition over rewards, abstracting away from who one collaborates with and implicitly treating teammates as interchangeable. Hedonic games [Dreze and Greenberg, 1980; Bogomolnaia and Jackson, 2002], in contrast, model preferences over coalition composition but ignore the presence of external, rivalrous rewards tied to specific tasks or projects. Group activity selection problems [Darmann et al., 2012] enable agents to choose both groups and activities; however, activities are typically labeled without tangible payoffs. As a result, neither framework adequately represents environments in which agents must simultaneously decide what to work on and with whom, balancing the benefits of collaboration against the costs of competition for limited resources.

We introduce Hedonic Project Games (HPGs), a framework that integrates subjective coalition preferences with objective, divisible project rewards. Each agent selects exactly one project; the resulting coalition determines both the agent's share of the project reward and the subjective value they derive from their teammates. Formally, an agent's utility is the product of their preference for the coalition and their equal share of the project's reward. This multiplicative structure creates trade-offs that neither hedonic games nor project games capture alone: joining a high-reward project may be unappealing if it means undesirable colleagues or diluted rewards; a lower-reward project may be preferable with a compatible team; an empty project guarantees full reward but sacrifices collaboration benefits.

A central solution concept in both hedonic and projectbased coalition formation is Nash stability, which requires that no agent can benefit by unilaterally deviating. However, Nash stability evaluates deviations solely from the deviating agent's perspective, ignoring the incentives of agents directly affected by entry or exit. In our setting, where coalition composition and reward division are tightly coupled, this limitation leads to outcomes that are individually stable yet fragile at the coalition level. To address this, we introduce two refinements of Nash stability: Joining Stability, which accounts for the consent of agents in the target coalition, and Leaving Stability, which considers the impact of departure on the remaining coalition.

Stable outcomes may not exist under arbitrary preferences, as conflicting incentives may induce improvement cycles. We therefore identify two natural and expressive preference classes under which stability is guaranteed: monotonically decreasing preferences with coalition size, and per-capita preferences, where utility depends on average coalition value. For these classes, we establish existence results for Nash, joining, and leaving stable outcomes. We further analyze the efficiency of stable outcomes using the Price of Anarchy and Price of Stability, showing how preference structure fundamentally shapes equilibrium efficiency. Finally, we validate our theoretical findings through experiments on synthetic instances and real-world crowdsourcing data, demonstrating that the interaction between coalition preferences and reward dilution is both theoretically and empirically consequential.

2 RelatedWork

Hedonic games have been extensively studied [Banerjee et al., 2001; Cechl´arov´a and Romero-Medina, 2001; Bogomolnaia and Jackson, 2002], with a comprehensive survey provided by Aziz et al. [Aziz and Savani, 2016]. Several subclasses capture different preference structures, including Additively Separable Hedonic Games (ASHGs) [Bogomolnaia and Jackson, 2002], Fractional Hedonic Games (FHGs) [Aziz et al., 2019], and Hedonic Coalition Nets [Elkind and Wooldridge, 2009]. Work on effective representations [Cechl´arov´a and Romero-Medina, 2001; Ballester, 2004; Elkind and Wooldridge, 2009; Aziz et al., 2019], stable outcome existence [Aziz and Brandl, 2012; Bil`o et al., 2018; Bullinger and Romen, 2024], and algorithmic aspects [Brandt et al., 2021] is extensive. In ASHGs, pure Nash equilibria exist under symmetric preferences but can be highly inefficient, with computation being PLS-complete. FHGs [Bil`o et al., 2018] guarantee Nash stability under restricted weights but have an unbounded price of anarchy. However, classical hedonic games ignore external factors such as task rewards, and even expressive variants assume agents only care about group composition.

Group Activity Selection Problems (GASPs) [Darmann et al., 2012] generalize hedonic games by letting agents choose both a group and an activity. For o-GASP with strict preferences, deciding the existence of a Nash stable assignment is NP-complete [Darmann, 2015], with parameterized complexity studied in [Lee and Williams, 2017]. However, activities are usually labels without explicit payoffs. Project Games [Bil`o et al., 2023], a class of monotone valid utility games [Vetta, 2002; Augustine et al., 2015; Goemans et al., 2004; Marden and Roughgarden, 2010; Marden and Wierman, 2013], model agents choosing projects with fixed weight contributions. They connect to load balancing [V¨ocking, 2007], congestion games [Rosenthal, 1973], and hedonic games [Dreze and Greenberg, 1980; Aziz and Savani, 2016]. These games admit pure Nash equilibria and have price of anarchy at most 2 [Goemans et al., 2004], but assume agents are indifferent to teammates.

The most closely related model is AS-GGASP [Bil`o et al., 2019], but it differs fundamentally in utility structure. ASGGASP assumes additive separability between coalition preferences and activity values, whereas hedonic project games use multiplicative utilities coupling coalition composition with divisible rewards. This captures interactions additive models cannot express: preferred collaborators matter only when sufficient reward remains, and high-reward projects become less attractive when shared among unsuitable coalitions. Unlike AS-GGASP's fixed activity utilities, hedonic project games explicitly model competition over divisible rewards. Each agent's utility is its normalized coalition preference multiplied by an equal share of the project reward, creating an endogenous trade-off between coalition attractiveness and reward dilution. Normalization preserves comparability without changing the multiplicative, size-dependent structure. Consequently, utilities in hedonic project games cannot be decomposed into additive agent-agent and agent-project components.

3 Definitions and Notation

We consider a finite set of agents N = {1, 2, . . . , n}, and a finite set of projects M = {j1, j2, . . . , jm}, where each agent i ∈ N can perform any project j ∈ M. Each project j ∈ M has an associated positive reward defined by the reward function r : M → R+, where r(j) represents the reward for project j. Each agent i ∈ N must select exactly one of the m projects. We denote the project chosen by agent i as their strategy, si ∈ M. A strategy profile (also referred to as an outcome throughout the remainder of this paper) is a vector s = (s1, . . . , sn) ∈ S, where the strategy space is S = M n .

Let Ni = {C ⊆ N : i ∈ C} denote the set of possible coalitions that each player i ∈ N belongs to. A hedonic project game is formally defined as follows:

Definition 1. A hedonic project game is specified by G = ⟨N, M, r, S, (pi)i∈N , (ui)i∈N ⟩, where:

• N = {1, 2, . . . , n} is the set of n players.
• M = {j1, j2, . . . , jm} is a finite set of m projects.
• r : M →R+ is a reward function.
• S = M n denotes the strategy space, where M is the strategy space for each player i.
• pi : Ni → [0, 1] denotes player i's preference function 1 , where ∑C∈Ni pi(C) = 1.
• ui : S ↦→R+ denotes the utility function for each player i ∈ N.

Given a strategy profile s ∈ S, the coalition for project j ∈ M is defined as Cj(s) = {i ∈ N : si = j}, which is the set of players that select project j under s, and we write |Cj(s)| for its size. The reward r(j) of each project j ∈ M is divisible and is shared equally among all players in Cj(s).

Given a strategy profile s ∈ S, the utility of each player i ∈ N is defined as follows:

where pi(Csi (s)) is player i's preference for the coalition to which she belongs, r(si) is the reward of the chosen project si, and |Csi (s)| is the number of players selecting project si.

3.1 Connections to ExistingModels

We briefly show that hedonic project games generalize several well-studied models under natural restrictions on rewards and preferences.

• Identical Project Rewards: All projects yield the same reward, normalized to 1, i.e., ∀j ∈ M, r(j) = r. Rewards are generic (heterogeneous) when this does not hold.
• Identical Preferences: Each agent assigns equal value to all coalitions they belong to (indifferent among coalitions), i.e., ∀i ∈ N, ∀C,C ′ ∈ Ni, pi(C) = pi(C ′ ).
• Additively Separable Preferences: Let wi : N → [0, 1] be the valuation function of an agent i assigning a weight wi(ℓ) ∈ [0, 1] being in the same coalition as i. The preferences of players in hedonic project games are additivity separable, i.e, the preference of each agent i for every coalition C ∈ Ni is pi(C) = ∑ℓ∈C wi(ℓ), assume wi(i) = 0.

Hedonic project games with identical preferences reduced to singleton congestion games [Rosenthal, 1973] and their variants such as symmetric project games with identical agents [Bil`o et al., 2023], market-sharing games [Goemans et al., 2004]. Load-balancing games with identical machines [V¨ocking, 2007] correspond to hedonic project games with identical preferences and rewards. Hedonic project games with additively separable preferences and identical project rewards reduce to fractional hedonic games with nonnegative preferences [Aziz et al., 2019; Bil`o et al., 2019].

3.2 Stability Notions

The classical stability notion in hedonic games is Nash stability (NS), named after the Nash equilibrium [Aziz and Savani, 2016]. It guarantees that no agent has an incentive to unilaterally change their coalition, regardless of the consent of others.

In our setting, a deviation occurs when a player i changes her strategy from the current project si under the strategy profile s to a distinct project j ̸= si. In hedonic project games, a strategy profile s is Nash stable if, for all players i ∈ N and all j ∈M, it holds

1 Normalization ensures comparability across coalitions while preserving the full expressiveness of agents' preference orderings.

where (j, s-i) denotes the profile obtained from s, after player i deviates from si to j. The set of all Nash stable outcomes for the game G is denoted by NS(G).

The limitation of Nash stability is that it considers only the deviator's utility, which can be overly restrictive in cooperative settings. To address this, we introduce two refinements of Nash stability that explicitly model coalition-level consent constraints.

Definition 2 (Joining Stability (JS)). A strategy profile s is joining stable if it is Nash stable, and for all i ∈ N, j ∈ M, and ℓ ∈ Cj(s),

where Cj(s) denotes the set of players who selected the project j under strategy profile s. The set of all joining stable outcomes for the game G is denoted by JS(G).

Definition 3 (Leaving Stability (LS)). A strategy profile s is leaving stable if for all i ∈ N, ℓ ∈ Csi (s), and j ∈ M,

where Csi (s) denotes the set of players who selected the same project as player i under strategy profile s. The set of all leaving stable outcomes for the game G is denoted by LS(G).

Our notions of joining and leaving stability strengthen Nash stability by imposing stricter conditions on how deviations impact the involved coalitions. In contrast, Individual Stability (IS) and Contractual Nash Stability (CNS) only partially account for affected members' preferences, allowing deviations that can still produce fragile outcomes. IS blocks a deviation only if someone in the target coalition is worse off, which may trap agents in suboptimal coalitions. CNS adds consent requirements but still does not guarantee stability for all affected members.

However, joining stability ensures that no unilateral deviation benefits the deviator, and additionally that no member of the target coalition would benefit from the deviator joining. Similarly, leaving stability ensures that no unilateral deviation benefits the deviator and that no member of the current coalition would benefit from the deviator leaving. Overall, joining stability and leaving stability are stronger than Nash stability, while IS and CNS are weaker. These stricter conditions ensure that coalitions have no incentive to actively reshape their membership, making joining stability and leaving stability stronger refinements of Nash stability than IS or CNS.

The logical hierarchy among these stability concepts is illustrated in Figure 1. Arrows indicate implication relationships; for example, either joining stability or leaving stability implies Nash stability.

3.3 Social Welfare and EfficiencyMeasures

Utilitarian social welfare (commonly referred to simply as social welfare) represents the collective well-being of all participants (players) in a game, typically measured by aggregating individual utilities or payoffs. Given a strategy profile s ∈ S, the social welfare is defined by

A social optimum of a game G is a strategy profile s⋆ = argmaxs∈S SW(s) that maximizes the social welfare. We denote by OPT(G) = SW(s⋆ ) the corresponding value.

Given a game instance, the Price of Anarchy (PoA) [Koutsoupias and Papadimitriou, 1999] is defined as the ratio of the worst case objective function value of a stable outcome to that of an optimal one. Analogously, the Price of Stability (PoS) [Anshelevich et al., 2008] captures the best-case ratio between the social optimum and the welfare at a stable outcome.

Definition 4. Fix a game G, and α ∈ {NS, JS, LS}. Let α(G) denote the set of α-stable outcomes for G. For any outcome s, let SW(s) be its social welfare and OPT(G) the maximum welfare. The price of anarchy and the price of stability under α, are

In both cases, if SW(s) = 0 for some s ∈ α(G), the corresponding ratio is defined as ∞. We consider the PoA and PoS to be undefined if no stable outcome exists with respect to any of the stability notions.

Let G be a class of hedonic project games, and α ∈ {NS, JS, LS}. Define PoAα(G) = supG∈G PoAα(G) and PoSα(G) = supG∈G PoSα(G). By definition, the following bounds hold:

To this end, we now focus on several natural subclasses of preferences that have been widely studied in the literature on hedonic games, and examine their implications within the context of the hedonic project game setting.

3.4 Structured Preferences

Instead of allowing arbitrary preferences that give rise to instability and inefficiency, we focus on structured preferences where systematic rules guide agents' choices: (i) monotonic decreasing preferences for coalition size, and (ii) per-capita preferences.

• (i). Monotonic Decreasing Preferences: The preferences of players in hedonic project games are monotonic decreasing with respect to coalition size, when for all i ∈ N, and C, C ′ ∈ Ni, holds:

Preferences are agent-specific monotonic decreasing if for each agent i ∈ N, there exists a function fi : N → [0, 1] with fi(k) > fi(k + 1) for all k ≥ 1, such that for all coalitions C ∈ Ni, pi(C) = fi(|C|); if fi = f for all i, they are universal.

• (ii). Per-Capita Preferences: In a hedonic project game, for each player i ∈ N and each coalition C ∈ Ni, the percapita preference of player i in coalition C is defined as

Player i is said to have per-capita (monotonic) nondecreasing (respectively, non-increasing) preferences if for any two coalitions C, C ′ ∈ Ni with C ′ ⊂ C, it holds thatˆ pi(C) ≥ ˆ pi(C ′ ) (respectively, ˆ pi(C) ≤ ˆ pi(C ′ ))

Preferences are called per-capita strictly decreasing (respectively, strictly increasing) if the above inequality is strict for all such pairs C ′ ⊂ C. Per-capita monotonicity only constrains preferences over nested coalitions; no assumptions are made for incomparable coalitions.

Monotonic decreasing preferences (in coalition size) capture a strict form of size aversion: agents always prefer smaller coalitions, and any increase in size weakly decreases utility, independent of who joins or how productive the coalition becomes. In contrast, per-capita preferences evaluate a coalition based on the average benefit per member. Under this view, adding a new agent may increase or decrease utility depending on whether that agent raises or lowers the coalition's average payoff.

Intuitively, monotonic decreasing preferences reflect congestion or crowding effects driven purely by group size, while per-capita preferences capture efficiency considerations where growth is beneficial only if the new member improves average performance. For example, in interdisciplinary research teams, a biologist joining computer scientists may significantly improve the project's effectiveness, increasing the average benefit rather than merely adding another member.

4 Existence and Efficiency of Stable Outcomes

In this section, we analyze the existence, and efficiency of stable outcomes in hedonic project games based on Nash stability and its coalition-consent refinements, joining and leaving stability under structured preference.

4.1 General Existence and Efficiency

In hedonic project games, a Nash stable outcome does not necessarily exist under unrestricted preferences (see Example 1. in the appendix 2 . Moreover, even when an Nash stable outcome is guaranteed to exist, the corresponding PoA can still be unbounded (see Example 2 in the appendix).

We show that the inefficiency of Nash stable outcomes (if they exist) remains controlled in hedonic project games. For any game G, let rmax = maxj∈M r(j) and rmin =

2 The appendix is provided in this link.

minj∈M r(j), denote the largest and smallest project rewards, respectively. We say that for a game G, rewards are ρbounded if the ratio rmax rmin ≤ ρ expresses the degree of reward disparity, where ρ is a constant. Preferences are δ-bounded if pi(C) ≥ δ for all i ∈ N, and C ∈ Ni. The following theorem establishes a constant-factor upper bound on the PoA in terms of ρ and δ.

Theorem 1. Let G ∈ G be a hedonic project game that admits at least one Nash stable outcome. If rewards are ρbounded, and preferences are δ-bounded, then we get

Proof. Let s be an arbitrary Nash-stable outcome of G, and let s⋆ be a strategy profile maximizing social welfare, with value OPT(G).

We first derive an upper bound on OPT(G). For any outcome s and any project j ∈ M with coalition Cj(s), the contribution of j to social welfare is

Since preferences are normalized, pi(C) ≤ 1 for all i and all C ∈ Ni, implying∑

Hence, the welfare contribution of project j is at most r(j).

By ρ-bounded we have rmax ≤ ρ · rmin. As at most min(n, m) projects can be non-empty, we obtain

We now lower-bound the social welfare SW(s).

Case 1: There exists an empty project j. For any agent i ∈ N, Nash stability implies

Summing over all agents yields

Case 2: No project is empty (i.e., all m projects are used). Note that this is only possible if m ≤ n, as there are only n agents. For each project j ∈ M,

By δ-boundedness, pi(Cj(s)) ≥ δ for all i ∈ Cj(s), implying that the term in parentheses is at least δ. Thus,

In Case 1, by combining (5) and (6), we obtain

In Case 2, since m ≤ n, by combining (5) and (8), we obtain

Since s was arbitrary, the bound holds for all Nash-stable outcomes. Moreover, δ-bounded preferences and positive rewards ensure SW(s) > 0.

4.2 Existence and Efficiency under Structured Preferences

Non-existence of stable outcomes arises from preferenceinduced deviation cycles that prevent convergence to equilibrium. We therefore focus on structured preference classes that guarantee equilibrium existence.

Additively Separable Preferences

A hedonic project game with additively separable preferences and identical project rewards reduces to a fractional hedonic game with non-negative weights. Existing results show that in additively separable hedonic games with non-negative preferences, the grand coalition is trivially Nash stable, since no agent can improve by deviating to a singleton coalition (e.g., [Olsen, 2009; Aziz and Savani, 2016; Bil`o et al., 2018; Valizadeh et al., 2025b]). Observation 1 extends this result to hedonic project games: even with project-specific rewards, the grand coalition remains stable and is both joining and leaving stable.

Observation 1. Let G ∈ G be a hedonic project game with additively separable preferences. If all players select the same project under a strategy profile s, then s is a Nash, joining and leaving stable outcome.

While the existence of a Nash, joining and leaving stable outcome is guaranteed for hedonic project games with additively separable preferences, the PoA for this subclass of preferences can be arbitrarily large.

Theorem 2. Let G be a class of hedonic project games with additively separable preferences. Then PoANS(G) is unbounded.

Monotonic Decreasing Preferences

Under universally monotonic decreasing preferences, every hedonic project game admits an exact potential function and therefore converges to a Nash-stable outcome. 3 In contrast, under agent-specific monotonic decreasing preferences, a potential function may not exist, but a Nash-stable outcome is still guaranteed. These games are player-specific congestion games with decreasing payoffs and satisfy the Finite Improvement Property (FIP), implying existence via Milchtaich [Milchtaich, 1996].

For general monotonic decreasing preferences in coalition size, Nash and joining stability coincide, while leaving stability may fail to exist (see Example 3 in the appendix). When project rewards are identical, equilibrium coalitions are sizebalanced, and every Nash-stable outcome is socially optimal.

3 Such games are a subclass of congestion games [Rosenthal, 1973].

Observation 2. Given a game instance G ∈ G , if preferences are monotonic decreasing (w.r.t. coalition size), then NS(G) = JS(G).

In hedonic project games, when the project rewards are identical and the agents' preferences decrease monotonically with coalition size, Nash stability ensures a strong balance across coalition sizes. The following lemma formalizes this property, demonstrating that at equilibrium, no coalition can be significantly larger than others.

Lemma 1. Let G ∈ G be a hedonic project game with monotonic decreasing preferences. If project rewards are identical and s is a Nash stable or joining stable outcome of G, then the sizes of the coalitions induced by s differ by at most one.

We say that monotonic decreasing preferences are concave, if the function fi : N→ [0, 1], satisfies

where pi(C) = fi(|C|) for every agent i ∈ N and coalition C ∈ Ni.

Theorem 3. Let G ∈ G be a hedonic project game with universal concave monotonic decreasing preferences. If project rewards are identical, then PoSNS(G) = PoSJS(G) = 1.

Per-Capita Preferences

Under per-capita non-decreasing preferences, trivially socially optimal allocations are Nash stable outcomes.

Observation 3. Let G ∈ G be a hedonic project game with per-capita non-decreasing preferences. Let j ⋆ ∈ argmaxj∈M r(j), and let s⋆ be the strategy profile in which all agents select project j ⋆ . Then s⋆ is a Nash stable outcome and an optimal allocation.

While leaving and joining stability are generally refinements of Nash stability, the following result shows that under per-capita non-decreasing preferences, these two notions are coincide.

Theorem 4. Let G ∈ G be a game instance with per-capita non-decreasing preferences. Then the sets of Nash and leaving stable outcomes coincide, i.e.,

Proof. We show that NS(G) ⊆ LS(G), as the reverse inclusion LS(G) ⊆ NS(G) holds by definition.

Let s be an arbitrary Nash stable outcome. Fix an agent i ∈ N and consider a deviation from project si to some project j ∈M.

If the deviation is strictly unprofitable for agent i, i.e., ui(s) > ui(j, s-i), then the leaving stability condition is trivially satisfied. Hence, it suffices to consider the case where agent i is indifferent:

Case 1: If |Csi (s)| = 1, then agent i forms a singleton coalition at project si, and Csi (s)\{i} = ∅. In this case, there are no other agents in i's original coalition whose utility could be affected by i's departure. The leaving stability condition requires that for all ℓ ∈ Csi (s), we have uℓ(s) ≥ uℓ(j, s-i).

Since Csi (s) = {i} and agent i is indifferent (or the deviation is unprofitable), the LS condition is trivially satisfied for all ℓ ̸= i and directly for ℓ = i.

Case 2: If |Csi (s)| ≥ 2, let ℓ ∈ Csi (s) \ {i} be any agent remaining in project si after i leaves. Their utilities before and after the deviation are

and

respectively.

The leaving stability requires uℓ(s) ≥ uℓ(j, s-i), which simplifies to:

after canceling r(si) > 0. This is precisely

This inequality holds by the assumption that preferences are per-capita non-decreasing.

Since the argument applies to every agent i and every indifferent deviation, s satisfies the leaving stability condition and hence NS(G) ⊆ LS(G). Thus,

Corollary 1. Let G ∈ G be a hedonic project game. If preferences are per-capita non-decreasing, then

While leaving stability is guaranteed to exist in the hedonic project game with non-decreasing preferences and coincide with Nash stability, Nash stability does not imply joining stability (see Example 4 in the appendix).

Under per-capita non-increasing preferences, each project can be viewed as a resource whose payoff to an agent depends only on the number of agents selecting it and is weakly decreasing in congestion. Consequently, hedonic project games with per-capita non-increasing preferences form a class of player-specific congestion games with decreasing payoff functions, which are known to satisfy the finite improvement property [Milchtaich, 1996].

Theorem 5. Let G ∈ G be a game instance with per-capita non-increasing preferences. Then

The following result establishes that per-capita strictly decreasing preferences preclude leaving stability for any nontrivial coalition structure.

Observation 4. For hedonic project games with per-capita strictly decreasing preferences, no outcome containing a coalition of size at least two can be leaving stable.

Corollary 2. Under per-capita strictly decreasing preferences, the only possible leaving stable outcomes are those where every coalition is a singleton. Consequently, if n > m, no leaving stable outcome exists.

5 Experimental Evaluation

We conduct an experimental evaluation to validate the theoretical results using both real-world and synthetic datasets 4 . For a real-world dataset, we have used a publicly available dataset from gMission, a research-oriented and open-source crowdsourcing platform [Chen et al., 2014], which comprises 1200 tasks collected from real-world crowdsourcing activities, each characterized by publish time, geographic location, and associated rewards [Tong et al., 2019]. We analyze 1,500 instances drawn from 10 gMission datasets. We infer agents' preferences from gMission by defining them as a decreasing function of distance between agents, with closer agents interpreted as having stronger collaborative affinity.

Synthetic instances follow a multi-scale design: smallscale (n ∼ U(2, 7), m ∼ U(2, 10)) to validate exact methods; medium-scale (n ∼ U(8, 15), m ∼ U(11, 20)) for scalability and approximation analysis; and large-scale (n ∼ U(16, 25), m ∼ U(21, 30)) to assess computational limits. Project rewards follow three models: uniform U(5, 100); Gaussian N(52.5, λ2 ) with λ chosen so that 99.7% of values lie in [5, 100] and clipped accordingly; and exponential with mean 50, shifted and clipped to [5, 100]. For each reward model, we generate 100 independent instances, yielding 300 synthetic games.

For each player i, preferences are normalized so that ∑C∋i pi(C) = 1. Identical preferences assign equal value to all coalitions. Additively separable preferences use a symmetric weight matrix wi(j) with wi(j) ∼ U[0.1, 1], defining pi(C) = ∑j∈C\{i} wi(j). Monotonic decreasing and per-capita preferences are size-based, pi(C) = fi(|C|), derived from a base function g(k) enforcing the required monotonicity (harmonic for monotonic decreasing, quadratic for per-capita non-decreasing, and constant for per-capita nonincreasing), and normalized using the exact number of coalitions of each size. All randomness uses a fixed seed.

5.1 Results and Analysis

Figure 2 shows clear separation in PoA across preference classes. Identical preferences exhibit low inefficiency (mean 1.09, max 1.45), with mass concentrated near 1, consistent with the bound PoSNS(G) ≤ 2 for singleton congestion games. Per-capita non-decreasing preferences perform best (mean 1.03, median 1.00), with most instances achieving optimal welfare. Monotonic decreasing preferences yield the highest inefficiency (mean 1.55, max 3.32) and largest variance, reflecting fragmentation induced by aversion to large coalitions. Per-capita non-increasing preferences show intermediate inefficiency (mean 1.42, max 2.06) with a roughly symmetric distribution.

Figure 3 reveals that reward heterogeneity significantly impacts equilibrium efficiency: the exponential distribution exhibits the highest PoA variance due to star projects that attract crowding, while uniform and Gaussian distributions yield tighter, more moderate PoA/PoS values as their homogeneous rewards reduce coordination sensitivity.

4 The code is provided in this link.

6 Conclusion

We introduced and analyzed Hedonic Project Games, a strategic framework that captures the joint dependence of agents' outcomes on both coalition composition and project rewards. The results show that when coalition preferences and reward sharing are tightly coupled, stability and efficiency are driven mainly by how agents evaluate coalitions rather than by reward magnitude. Stability increases when agents account for how their participation affects others, even indirectly. Preference structures that scale with coalition size reduce incentives for disruptive deviations, while unrestricted preferences enable gains from reward dilution without internalizing its broader effects. This suggests that inefficiency in collaborative settings is caused more by misaligned preference scaling than by competition over rewards alone.

This work also points to several future directions, including heterogeneous reward-sharing schemes, relaxing the singleproject assumption, and studying learning dynamics in repeated hedonic project games with limited feedback. From an algorithmic perspective, the complexity of finding stable outcomes under more general preference classes remains open. More broadly, hedonic project games provide a flexible model for collaborative systems where agents jointly choose both tasks and partners, supporting the design and analysis of modern multi-agent platforms.

Acknowledgements

This work was supported by the Commonwealth through an Australian Government Research Training Program Scholarship [DOI: https://doi.org/10.82133/C42F-K220].