PAC Learning and Stabilizing Hedonic Games: Towards a Unifying Approach.
Authors: Simone Fioravanti, Michele Flammini, Bojana Kodric, Giovanna Varricchio
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Simone Fioravanti1, Michele Flammini1, 4, Bojana Kodric2, 1, Giovanna Varricchio3 1 Gran Sasso Science Institute (GSSI), L Aquila, Italy 2 Ca Foscari University of Venice, Venice, Italy 3 Goethe-Universit at, Frankfurt am Main, Germany 4 University of Calabria, Rende, Italy |
| Pseudocode | Yes | Algorithm 1: Stabilizing Bottom Responsive HGs |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments using specific datasets. The 'samples' mentioned refer to theoretical constructs within the PAC learning framework, not concrete datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with dataset splits. It discusses theoretical 'samples' but not practical data partitioning for empirical evaluation. |
| Hardware Specification | No | The paper is theoretical and does not describe any empirical experiments that would require specific hardware for execution. |
| Software Dependencies | No | The paper is theoretical and does not report on implemented systems or empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experimental setup details, hyperparameters, or training configurations. |