Coalitional Manipulations and Immunity of the Shapley Value

• URL: http://arxiv.org/abs/2310.20415v1
• Date: Tue, 31 Oct 2023 12:43:31 GMT
• Title: Coalitional Manipulations and Immunity of the Shapley Value
• Abstract summary: We consider manipulations in the context of coalitional games, where a coalition aims to increase the total payoff of its members. An allocation rule is immune to coalitional manipulation if no coalition can benefit from internal reallocation of worth. For efficient allocation rules, reallocation-proofness is equivalent to constrained marginality.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider manipulations in the context of coalitional games, where a coalition aims to increase the total payoff of its members. An allocation rule is immune to coalitional manipulation if no coalition can benefit from internal reallocation of worth on the level of its subcoalitions (reallocation-proofness), and if no coalition benefits from a lower worth while all else remains the same (weak coalitional monotonicity). Replacing additivity in Shapley's original characterization by these requirements yields a new foundation of the Shapley value, i.e., it is the unique efficient and symmetric allocation rule that awards nothing to a null player and is immune to coalitional manipulations. We further find that for efficient allocation rules, reallocation-proofness is equivalent to constrained marginality, a weaker variant of Young's marginality axiom. Our second characterization improves upon Young's characterization by weakening the independence requirement intrinsic to marginality.

Related papers

• Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach [0.23689955632456086]
  Clustered learning benefits from organizing heterogeneous participants into coalitions that train coalition-specific models.<n>We develop a transferable-surplus model separating learning benefit, system cost, participant cost, and monetary transfers.
  arXiv  Detail & Related papers  (2026-07-29T11:29:45Z)
• Counterfactual Shapley Credit Assignment [49.39649767581182]
  Credit Assignment Problem (CAP) is fundamental to developing efficient and explainable Reinforcement Learning (RL) agents.<n>We introduce Counterfactual Shapley Credit Assignment, a novel framework that attributes credit and blame via the Counterfactual Shapley ($$-value)<n>We derive a consistent estimator that computes $$$-values, enabling a new class of policy methods, $$-PPO, combined with Prioritized Trajectory Replay (PTR)
  arXiv  Detail & Related papers  (2026-07-18T23:28:20Z)
• 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)
• Breaking $\ extit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
  Group Cooperative Policy Optimization shifts the training paradigm from rollout competition to team cooperation.<n>GCPO replaces independent rollout scoring with team-level credit assignment.<n>It redistributes the collective team reward to each single rollout according to its average marginal contribution to the team.
  arXiv  Detail & Related papers  (2026-05-12T03:20:24Z)
• Computing Equilibrium beyond Unilateral Deviation [27.786964046329455]
  We study an alternative solution concept that minimizes coalitional deviation incentives, rather than requiring them to vanish.<n> Specifically, we focus on minimizing the average gain of a deviating coalition, and extend the framework to weighted-average and maximum-within-coalition gains.<n>For the average-gain and maximum-gain objectives, we prove a lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound.
  arXiv  Detail & Related papers  (2026-04-30T17:59:07Z)
• Metric Hedonic Games on the Line [4.832821031860376]
  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.
  arXiv  Detail & Related papers  (2026-02-05T17:05:08Z)
• Toward a Sustainable Federated Learning Ecosystem: A Practical Least Core Mechanism for Payoff Allocation [71.86087908416255]
  We introduce a payoff allocation framework based on the least core (LC) concept.<n>Unlike traditional methods, the LC prioritizes the cohesion of the federation by minimizing the maximum dissatisfaction.<n>Case studies in federated intrusion detection demonstrate that our mechanism correctly identifies pivotal contributors and strategic alliances.
  arXiv  Detail & Related papers  (2026-02-03T11:10:50Z)
• Outcome-Grounded Advantage Reshaping for Fine-Grained Credit Assignment in Mathematical Reasoning [60.00161035836637]
  Group Relative Policy Optimization has emerged as a promising critic-free reinforcement learning paradigm for reasoning tasks.<n>We introduce Outcome-grounded Advantage Reshaping (OAR), a fine-grained credit assignment mechanism that redistributes advantages based on how much each token influences the model's final answer.<n>OAR-G achieves comparable gains with negligible computational overhead, both significantly outperforming a strong GRPO baseline.
  arXiv  Detail & Related papers  (2026-01-12T10:48:02Z)
• MAESTRO: Meta-learning Adaptive Estimation of Scalarization Trade-offs for Reward Optimization [56.074760766965085]
  Group-Relative Policy Optimization has emerged as an efficient paradigm for aligning Large Language Models (LLMs)<n>We propose MAESTRO, which treats reward scalarization as a dynamic latent policy, leveraging the model's terminal hidden states as a semantic bottleneck.<n>We formulate this as a contextual bandit problem within a bi-level optimization framework, where a lightweight Conductor network co-evolves with the policy by utilizing group-relative advantages as a meta-reward signal.
  arXiv  Detail & Related papers  (2026-01-12T05:02:48Z)
• $\varepsilon$-fractional Core Stability in Hedonic Games [13.576268908412338]
  Hedonic Games (HGs) are a framework for modeling coalitions of strategic agents guided by their individual preferences. We propose the notion of $varepsilon$-fractional core-stability, where at most an $varepsilon$-fraction of all possible coalitions is allowed to formation core-block. Specifically, we design efficient algorithms returning an $varepsilon$-fractional core-stable partition, with $varepsilon$ exponentially decreasing in the number of agents.
  arXiv  Detail & Related papers  (2023-11-18T15:30:29Z)
• Towards Attributions of Input Variables in a Coalition [22.23671744465488]
  We develop a new attribution method to explain the conflict between individual variables' attributions and their coalition's attribution. First, we find that the Shapley value can be reformulated as the allocation of Harsanyi interactions encoded by the AI model. Second, based the re-alloction of interactions, we extend the Shapley value to the attribution of coalitions.
  arXiv  Detail & Related papers  (2023-09-23T15:48:35Z)
• Trust-Region-Free Policy Optimization for Stochastic Policies [60.52463923712565]
  We show that the trust region constraint over policies can be safely substituted by a trust-region-free constraint without compromising the underlying monotonic improvement guarantee. We call the resulting algorithm Trust-REgion-Free Policy Optimization (TREFree) explicit as it is free of any trust region constraints.
  arXiv  Detail & Related papers  (2023-02-15T23:10:06Z)
• The Role of Baselines in Policy Gradient Optimization [83.42050606055822]
  We show that the emphstate value baseline allows on-policy. emphnatural policy gradient (NPG) to converge to a globally optimal. policy at an $O (1/t) rate gradient. We find that the primary effect of the value baseline is to textbfreduce the aggressiveness of the updates rather than their variance.
  arXiv  Detail & Related papers  (2023-01-16T06:28:00Z)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL) We show that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training.
  arXiv  Detail & Related papers  (2022-01-31T20:39:48Z)
• 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)
• A Unified Framework for Conservative Exploration [115.7063101600773]
  We study bandits and reinforcement learning (RL) subject to a conservative constraint where the agent is asked to perform at least as well as a given baseline policy. We present a unified framework for conservative bandits and RL, in which our core technique is to calculate the necessary and sufficient budget obtained from running the baseline policy.
  arXiv  Detail & Related papers  (2021-06-22T11:52:04Z)
• 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)
• 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)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)

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.