On Singleton Congestion Games with Resilience Against Collusion

• URL: http://arxiv.org/abs/2011.01791v1
• Date: Tue, 3 Nov 2020 15:35:09 GMT
• Title: On Singleton Congestion Games with Resilience Against Collusion
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the subclass of singleton congestion games with identical and increasing cost functions, i.e., each agent tries to utilize from the least crowded resource in her accessible subset of resources. Our main contribution is a novel approach for proving the existence of equilibrium outcomes that are resilient to weakly improving deviations: $(i)$ by singletons (Nash equilibria), $(ii)$ by the grand coalition (Pareto efficiency), and $(iii)$ by coalitions with respect to an a priori given partition coalition structure (partition equilibria). To the best of our knowledge, this is the strongest existence guarantee in the literature of congestion games that is resilient to weakly improving deviations by coalitions.

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)
• 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)
• 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)
• From Debate to Equilibrium: Belief-Driven Multi-Agent LLM Reasoning via Bayesian Nash Equilibrium [52.28048367430481]
  Multi-agent frameworks can boost the reasoning power of large language models (LLMs), but they typically incur heavy computational costs and lack convergence guarantees.<n>We recast multi-LLM coordination as an incomplete-information game and seek a Bayesian Nash equilibrium (BNE)<n>We introduce Efficient Coordination via Nash Equilibrium (ECON), a hierarchical reinforcement-learning paradigm that marries distributed reasoning with centralized final output.
  arXiv  Detail & Related papers  (2025-06-09T23:49:14Z)
• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  We prove lower bounds for computing a near-optimal $T$-sparse CCE. In particular, we show that the inapproximability of maximum clique precludes attaining any non-trivial sparsity in time.
  arXiv  Detail & Related papers  (2024-11-04T00:34:56Z)
• Compressed Federated Reinforcement Learning with a Generative Model [11.074080383657453]
  Reinforcement learning has recently gained unprecedented popularity, yet it still grapples with sample inefficiency. Addressing this challenge, federated reinforcement learning (FedRL) has emerged, wherein agents collaboratively learn a single policy by aggregating local estimations. We propose CompFedRL, a communication-efficient FedRL approach incorporating both textitperiodic aggregation and (direct/error-feedback) compression mechanisms.
  arXiv  Detail & Related papers  (2024-03-26T15:36:47Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  Non-concave games introduce significant game-theoretic and optimization challenges. We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria. We also show that Online Gradient Descent can efficiently approximate $Phi$-equilibria in non-trivial regimes.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• Reducing Optimism Bias in Incomplete Cooperative Games [0.0]
  We present a framework aimed at optimizing the sequence for revealing coalition values in cooperative games. Our contributions are threefold: (i) we study the individual players' optimistic completions of games with missing coalition values along with the arising gap, and investigate its analytical characteristics that facilitate more efficient optimization; (ii) we develop methods to minimize this gap over classes of games with a known prior by disclosing values of additional coalitions in both offline and online fashion; and (iii) we empirically demonstrate the algorithms' performance in practical scenarios.
  arXiv  Detail & Related papers  (2024-02-02T21:58:26Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Coalitional Manipulations and Immunity of the Shapley Value [0.0]
  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.
  arXiv  Detail & Related papers  (2023-10-31T12:43:31Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• PAC learning and stabilizing Hedonic Games: towards a unifying approach [10.856422132960164]
  We study PAC learnability and PAC stabilizability of Hedonic Games (HGs) We identify two sets of conditions that lead to efficient learnability, and which encompass all of the known positive learnability results. On the side of stability, we reveal that, while the freedom of choosing an ad hoc adversarial distribution is the most obvious hurdle to achieving PAC stability, it is not the only one.
  arXiv  Detail & Related papers  (2023-01-31T16:45:36Z)
• Safe Subgame Resolving for Extensive Form Correlated Equilibrium [47.155175336085364]
  Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to better social welfare. We apply textitsubgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an textitonline manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play.
  arXiv  Detail & Related papers  (2022-12-29T14:20:48Z)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  We study the (in)efficiency of any equilibrium players might agree to play. We obtain guarantees that refine existing bounds on the Price of Anarchy. Although the obtained guarantees concern open-loop trajectories, we observe efficient equilibria even when agents employ closed-loop policies.
  arXiv  Detail & Related papers  (2022-10-24T09:32:40Z)
• Multi-Leader Congestion Games with an Adversary [0.5914780964919123]
  We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources. We show that pure Nash equilibria may fail to exist and therefore, we consider approximate equilibria instead. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible $alpha$ among all $alpha$-approximate equilibria of the given instance.
  arXiv  Detail & Related papers  (2021-12-14T14:47:43Z)
• Munchausen Reinforcement Learning [50.396037940989146]
  bootstrapping is a core mechanism in Reinforcement Learning (RL) We show that slightly modifying Deep Q-Network (DQN) in that way provides an agent that is competitive with distributional methods on Atari games. We provide strong theoretical insights on what happens under the hood -- implicit Kullback-Leibler regularization and increase of the action-gap.
  arXiv  Detail & Related papers  (2020-07-28T18:30:23Z)

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.