Online Learning of Partitions in Additively Separable Hedonic Games

Saar Cohen, Noa AgmonIJCAI 2024

Abstract

This paper introduces the first online learning framework for coalition formation in hedonic games, addressing scenarios where agents arrive dynamically and preferences evolve over time. While achieving low static regret for discrete partitions is proven to be computationally hard, the authors demonstrate that a fractional relaxation combined with a novel randomized rounding scheme can achieve optimal dynamic regret. By bridging game theory and online convex optimization, the research provides a polynomial-time algorithm for minimizing social cost in additively separable games, even under adversarial preference changes.

Introduction

In social and economic systems, agents frequently organize into coalitions—such as students forming study groups, companies entering research consortiums, or users joining community networks. Hedonic games provide a formal framework for these scenarios, where an agent's utility is derived exclusively from the identity of the other members in their coalition.

Traditionally, hedonic games have been studied in offline, static environments where all agents and their preferences are known a priori. However, real-world applications are characterized by volatility: agents arrive and depart, preferences evolve through experience, and external factors may change the desirability of certain interactions. This paper addresses these challenges by proposing a framework for the Online Learning of Partitions, where a learner must group agents at each time step before their current preferences are revealed, aiming to minimize the cumulative social cost (dissatisfaction) over time.

Problem Formulation and Hardness

The authors focus on additively separable hedonic games, where the disutility an agent feels in a coalition is the sum of their individual preferences toward every other member. The goal is to minimize the total social cost across $T$ time steps.

A significant contribution of this work is identifying the Hardness Paradox. The authors prove that achieving "no-static regret"—performing as well as the single best fixed partition in hindsight—is NP-hard and even hard to approximate under the Exponential Time Hypothesis (ETH). This hardness stems from the combinatorial nature of partitioning, which relates to the Densest $k$-Subgraph problem. Interestingly, the authors show that this computational barrier for static regret does not necessarily prevent the achievement of low dynamic regret when using the right algorithmic approach.

Methodology

To bypass the exponential complexity of the discrete partition space, the authors employ a multi-step algorithmic strategy:

1. Fractional Relaxation

The problem is first transformed from a discrete combinatorial task into a convex optimization task. By allowing agents to be "fractionally" assigned to multiple coalitions, the learner can navigate a continuous space where gradients are well-defined.

2. Primal-Dual Online Gradient Descent (OGD)

The authors develop a learner based on Online Gradient Descent. Using a primal-dual formulation of the fractional social cost, the algorithm efficiently calculates subgradients. These mathematical pointers guide the algorithm on how to update fractional partitions to minimize future costs based on past observations.

3. Randomized Rounding

To translate fractional assignments back into real-world discrete groups, the paper introduces a randomized rounding mechanism. Each agent is assigned to a specific coalition with a probability equal to their fractional assignment. To analyze the performance of this rounding, the authors introduce a new metric called the interaction term ($I^T$), which quantifies the fluctuation of agent interactions over time and helps bound the regret of the discrete partition.

Key Results

The paper establishes several benchmark results for online coalition formation:

  • Fractional Performance: The OGD-based learner achieves a minimax optimal static regret bound of $O(m \cdot W \sqrt{T \log n})$, where $m$ is the maximum number of agents and $W$ is the maximum disutility.
  • Integral Performance: When the randomized rounding scheme is applied, the learner achieves an optimal dynamic regret bound of $I^T + O(S^*_T)$. This indicates that the learner performs nearly as well as an oracle that knows the best partition for every time step, limited only by the inherent noise of the rounding process and the volatility of the optimal solutions ($S^*_T$).
  • Computational Efficiency: Unlike traditional methods that might require searching an exponential space of partitions, this framework runs in polynomial time, making it feasible for larger agent populations.

Limitations and Future Work

While this framework represents a significant step forward, several avenues for future research remain:

  1. Beyond Additive Separability: The current model assumes utilities are strictly additive. Future work could explore complex synergies or "threshold" effects where the value of a group is more than the sum of its parts.
  2. Bandit Feedback: The paper assumes "full information" (all preferences are revealed after a partition is made). In many practical settings, a learner might only receive "bandit feedback," learning only the preferences of agents within their assigned coalitions.
  3. Stability and Fairness: The current objective is the minimization of total social cost (efficiency). Integrating concepts of game-theoretic stability (ensuring no agent has an incentive to leave) or fairness remains an open challenge in the online setting.

Conclusion

By combining online convex optimization with randomized rounding, this research provides a robust theoretical foundation for dynamic coalition formation. It demonstrates that even when optimal static solutions are computationally unreachable, effective online learning is possible, offering a path toward more adaptive and efficient social and economic organization.

Summary updated

BibTeX
@inproceedings{cohen2024online,
  author = {Saar Cohen and Noa Agmon},
  title = {{Online Learning of Partitions in Additively Separable Hedonic Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure