Metric Hedonic Games on the Line

• URL: http://arxiv.org/abs/2602.05888v1
• Date: Thu, 05 Feb 2026 17:05:08 GMT
• Title: Metric Hedonic Games on the Line
• Abstract summary: We study a novel succinct variant related to modified fractional hedonic games.<n>In particular, we investigate natural variants where an agent's cost is defined by distance thresholds.<n>We find that stable coalition structures always exist but that their properties and quality can vary widely.
• Score: 4.832821031860376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hedonic games are fundamental models for investigating the formation of coalitions among a set of strategic agents, where every agent has a certain utility for every possible coalition of agents it can be part of. To avoid the intractability of defining exponentially many utilities for all possible coalitions, many variants with succinct representations of the agents' utility functions have been devised and analyzed, e.g., modified fractional hedonic games by Monaco et al. [JAAMAS 2020]. We extend this by studying a novel succinct variant that is related to modified fractional hedonic games. In our model, each agent has a fixed type-value and an agent's cost for some given coalition is based on the differences between its value and those of the other members of its coalition. This allows to model natural situations like athletes forming training groups with similar performance levels or voters that partition themselves along a political spectrum. In particular, we investigate natural variants where an agent's cost is defined by distance thresholds, or by the maximum or average value difference to the other agents in its coalition. For these settings, we study the existence of stable coalition structures, their properties, and their quality in terms of the price of anarchy and the price of stability. Further, we investigate the impact of limiting the maximum number of coalitions. Despite the simple setting with metric distances on a line, we uncover a rich landscape of models, partially with counter-intuitive behavior. Also, our focus on both swap stability and jump stability allows us to study the influence of fixing the number and the size of the coalitions. Overall, we find that stable coalition structures always exist but that their properties and quality can vary widely.

Related papers

• Exit-and-Join Dynamics and Equilibrium in Continuum Cooperative Games [20.036142577511455]
  We develop a continuum theory of exit-and-join coalition dynamics in nonatomic cooperative games.<n>We derive mean-field dynamics from decentralized switching rules and show that payoff-difference switching recovers replicator dynamics.<n>The proposed theory unifies cooperative value allocation, noncooperative coalition mobility, mean-field dynamics, evolutionary game theory, and population games.
  arXiv  Detail & Related papers  (2026-06-27T09:17:07Z)
• Exit-and-Join Dynamics for Decentralized Coalition Formation [20.036142577511455]
  We study coalition formation as a decentralized dynamical process driven by unilateral exit-and-join decisions.<n>Agents evaluate local moves using the Aumann-Dreze value, so payoffs are computed within the agent's current coalition.<n>A terminal partition is precisely a coalition structure with no admissible, individually profitable exit-and-join deviation.
  arXiv  Detail & Related papers  (2026-06-18T01:19:31Z)
• Escaping the Diversity Trap in Robotic Manipulation via Anchor-Centric Adaptation [50.23374353859762]
  "Maximizing coverage" by collecting diverse, single-shot demonstrations can be self-defeating due to non-vanishing estimation noise.<n>We formalize this phenomenon as a Coverage--Density Trade-off.<n>We propose Anchor-Centric Adaptation (ACA), a two-stage framework that first stabilizes a policy skeleton through repeated demonstrations at core anchors, then expands coverage to high-risk boundaries via teacher-forced error mining and constrained residual updates.
  arXiv  Detail & Related papers  (2026-05-08T07:35:24Z)
• Competitive Algorithms for Multi-Agent Ski-Rental Problems [35.95355517827071]
  This paper introduces a novel multi-agent ski-rental problem that generalizes the classical ski-rental dilemma to a group setting.<n>In our model, each agent can either rent at a fixed daily cost, or purchase a pass at an individual cost, with an additional third option of a discounted group pass available to all.<n>We consider scenarios in which agents' active days differ, leading to dynamic states as agents drop out of the decision process.
  arXiv  Detail & Related papers  (2025-07-21T15:36:34Z)
• On the Convergence of Bounded Agents [80.67035535522777]
  A bounded agent has converged when the minimal number of states needed to describe the agent's future behavior cannot decrease. The second view says that a bounded agent has converged just when the agent's performance only changes if the agent's internal state changes.
  arXiv  Detail & Related papers  (2023-07-20T17:27:29Z)
• Strategic Resource Selection with Homophilic Agents [48.83208975886834]
  We propose Resource Selection Games with heterogeneous agents that strive for joint resource usage with similar agents. Our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. We show that this type of bounded rationality yields favorable game-theoretic properties.
  arXiv  Detail & Related papers  (2023-05-01T14:14:58Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Single-Peaked Jump Schelling Games [12.940151684804958]
  We study Jump Schelling Games with agents having a single-peaked utility function. We show that improving response cycles exist independently of the position of the peak in the utility function. We also show that computing a beneficial state with high integration is NP-complete.
  arXiv  Detail & Related papers  (2023-02-23T15:46:26Z)
• Finding General Equilibria in Many-Agent Economic Simulations Using Deep Reinforcement Learning [72.23843557783533]
  We show that deep reinforcement learning can discover stable solutions that are epsilon-Nash equilibria for a meta-game over agent types. Our approach is more flexible and does not need unrealistic assumptions, e.g., market clearing. We demonstrate our approach in real-business-cycle models, a representative family of DGE models, with 100 worker-consumers, 10 firms, and a government who taxes and redistributes.
  arXiv  Detail & Related papers  (2022-01-03T17:00:17Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  We show that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules.
  arXiv  Detail & Related papers  (2021-09-30T11:09:31Z)
• Gradient play in stochastic games: stationary points, convergence, and sample complexity [6.97785632069611]
  We study the performance of the gradient play algorithm for games (SGs) We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting. For a subclass of SGs called Markov potential games, we design a sample-based reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2021-06-01T03:03:45Z)
• Dealing with Non-Stationarity in Multi-Agent Reinforcement Learning via Trust Region Decomposition [52.06086375833474]
  Non-stationarity is one thorny issue in multi-agent reinforcement learning. We introduce a $delta$-stationarity measurement to explicitly model the stationarity of a policy sequence. We propose a trust region decomposition network based on message passing to estimate the joint policy divergence.
  arXiv  Detail & Related papers  (2021-02-21T14:46:50Z)
• Model Free Reinforcement Learning Algorithm for Stationary Mean field Equilibrium for Multiple Types of Agents [43.21120427632336]
  We consider a multi-agent strategic interaction over an infinite horizon where agents can be of multiple types. Each agent has a private state; the state evolves depending on the distribution of the state of the agents of different types and the action of the agent. We show how such kind of interaction can model the cyber attacks among defenders and adversaries.
  arXiv  Detail & Related papers  (2020-12-31T00:12:46Z)
• On Singleton Congestion Games with Resilience Against Collusion [0.0]
  We study the subclass of singleton congestion games with identical and increasing cost functions. Our main contribution is a novel approach for proving the existence of equilibrium outcomes that are resilient to weakly improving deviations.
  arXiv  Detail & Related papers  (2020-11-03T15:35:09Z)
• Contextual and Possibilistic Reasoning for Coalition Formation [0.9790236766474201]
  This article addresses the question of how to find and evaluate coalitions among agents in multiagent systems. We first compute the solution space for the formation of coalitions using a contextual reasoning approach. Second, we model agents as contexts in Multi-Context Systems (MCS), and dependence relations among agents seeking to achieve their goals, as bridge rules. Third, we systematically compute all potential coalitions using algorithms for MCS equilibria, and given a set of functional and non-functional requirements, we propose ways to select the best solutions.
  arXiv  Detail & Related papers  (2020-06-19T11:59:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.