PAC learning and stabilizing Hedonic Games: towards a unifying approach

• URL: http://arxiv.org/abs/2301.13756v1
• Date: Tue, 31 Jan 2023 16:45:36 GMT
• Title: PAC learning and stabilizing Hedonic Games: towards a unifying approach
• Abstract summary: 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.
• Score: 10.856422132960164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study PAC learnability and PAC stabilizability of Hedonic Games (HGs), i.e., efficiently inferring preferences or core-stable partitions from samples. We first expand the known learnability/stabilizability landscape for some of the most prominent HGs classes, providing results for Friends and Enemies Games, Bottom Responsive, and Anonymous HGs. Then, having a broader view in mind, we attempt to shed light on the structural properties leading to learnability/stabilizability, or lack thereof, for specific HGs classes. Along this path, we focus on the fully expressive Hedonic Coalition Nets representation of 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. First, we show a distribution independent necessary condition for PAC stability. Then, we focus on $\W$-games, where players have individual preferences over other players and evaluate coalitions based on the least preferred member. We prove that these games are PAC stabilizable under the class of bounded distributions, which assign positive probability mass to all coalitions. Finally, we discuss why such a result is not easily extendable to other HGs classes even in this promising scenario. Namely, we establish a purely computational property necessary for achieving PAC stability.

Related papers

• Learning Conditional Averages [52.361762722359366]
  We introduce the problem of learning conditional averages in the PAC framework.<n>Instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood.<n>More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains.
  arXiv  Detail & Related papers  (2026-02-12T13:20:29Z)
• Conditional Performance Guarantee for Large Reasoning Models [33.71268958080582]
  Group PAC (G-PAC) and Clustered PAC (C-PAC) reasoning for unknown groupings are presented.<n>G-PAC and C-PAC successfully achieve group-conditional risk control while maintaining substantial computational savings.
  arXiv  Detail & Related papers  (2026-01-30T10:09:41Z)
• Samplability makes learning easier [10.233615909288188]
  Standard definition of PAC learning requires learners to succeed under all distributions.<n>We show that samplable PAC substantially expands the power of efficient learners.
  arXiv  Detail & Related papers  (2025-12-01T04:48:36Z)
• PAC Apprenticeship Learning with Bayesian Active Inverse Reinforcement Learning [59.93251770120936]
  Inverse reinforcement learning (IRL) offers a promising approach to infer preferences from demonstrations.<n>We introduce PAC-EIG, an information-theoretic acquisition function that directly targets probably-approximately-correct (PAC) guarantees for the learned policy.<n>Our method maximises information gain about the regret of the apprentice policy, efficiently identifying states requiring further demonstration.
  arXiv  Detail & Related papers  (2025-08-05T17:59:56Z)
• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  We study contrastive learning under the PAC learning framework. In this paper, we consider contrastive learning of the fundamental concept of linear representations. We establish guarantees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions.
  arXiv  Detail & Related papers  (2025-02-21T21:51:01Z)
• Stability and List-Replicability for Agnostic Learners [2.061173670995696]
  We prove that classes with infinite Littlestone dimension are not stably PAC learnable, even if we allow the stability parameter to depend on the excess error. We also prove that only finite hypothesis classes are globally stable learnable, even if we restrict the agnostic setting to distributions with small population loss.
  arXiv  Detail & Related papers  (2025-01-09T15:59:15Z)
• Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
  Two-sided matching markets describe a class of problems wherein participants from one side of the market must be matched to those from the other side according to their preferences. We exploit the structure of stable solutions to devise algorithms that improve the likelihood of finding stable solutions.
  arXiv  Detail & Related papers  (2024-10-06T06:47:53Z)
• On the Computability of Robust PAC Learning [9.507869508188266]
  We introduce the problem of robust computable PAC (robust CPAC) learning. We show that learnability in this setup is not implied by the combination of its components. We prove that its finiteness is necessary, but not sufficient for robust CPAC learnability.
  arXiv  Detail & Related papers  (2024-06-14T16:20:04Z)
• Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
  This paper contributes to the study of CPAC learnability by solving three open questions from recent papers. Firstly, we prove that every CPAC learnable class is contained in a class which is properly CPAC learnable with a sample complexity. Secondly, we show that there exists a decidable class of hypothesis which is properly learnable, but only with uncomputably fast growing sample complexity.
  arXiv  Detail & Related papers  (2023-02-06T02:52:36Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• On Higher Adversarial Susceptibility of Contrastive Self-Supervised Learning [104.00264962878956]
  Contrastive self-supervised learning (CSL) has managed to match or surpass the performance of supervised learning in image and video classification. It is still largely unknown if the nature of the representation induced by the two learning paradigms is similar. We identify the uniform distribution of data representation over a unit hypersphere in the CSL representation space as the key contributor to this phenomenon. We devise strategies that are simple, yet effective in improving model robustness with CSL training.
  arXiv  Detail & Related papers  (2022-07-22T03:49:50Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  We develop a framework and algorithms for learning stable market outcomes under uncertainty. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.
  arXiv  Detail & Related papers  (2021-08-19T17:59:28Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
  arXiv  Detail & Related papers  (2021-07-03T23:17:26Z)
• Optimality and Stability in Federated Learning: A Game-theoretic Approach [0.0]
  We motivate and define a notion of optimality given by the average error rates among federating agents (players) First, we show that for some regions of parameter space, all stable arrangements are optimal (Price of Anarchy equal to 1). However, we show this is not true for all settings: there exist examples of stable arrangements with higher cost than optimal (Price of Anarchy greater than 1).
  arXiv  Detail & Related papers  (2021-06-17T15:03:51Z)
• Semi-verified PAC Learning from the Crowd [7.594050968868919]
  We study the problem of crowdsourced PAC learning of threshold functions. We show that under the semi-verified model of Charikar et al., it is possible to PAC learn the underlying hypothesis class with a manageable amount of label queries.
  arXiv  Detail & Related papers  (2021-06-13T20:05:16Z)
• Independent Policy Gradient Methods for Competitive Reinforcement Learning [62.91197073795261]
  We obtain global, non-asymptotic convergence guarantees for independent learning algorithms in competitive reinforcement learning settings with two agents. We show that if both players run policy gradient methods in tandem, their policies will converge to a min-max equilibrium of the game, as long as their learning rates follow a two-timescale rule.
  arXiv  Detail & Related papers  (2021-01-11T23:20:42Z)
• 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)

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.