Price of Pareto Optimality in Hedonic Games
Authors: Edith Elkind, Angelo Fanelli, Michele Flammini
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we argue that Pareto optimality can be seen as a notion of stability, and introduce the concept of Price of Pareto Optimality: this is an analogue of the Price of Anarchy, where the maximum is computed over the class of Pareto optimal outcomes, i.e., outcomes that do not permit a deviation by the grand coalition that makes all players weakly better off and some players strictly better off. As a case study, we focus on hedonic games, and provide lower and upper bounds of the Price of Pareto Optimality in three classes of hedonic games: additively separable hedonic games, fractional hedonic games, and modified fractional hedonic games; for fractional hedonic games on trees our bounds are tight. |
| Researcher Affiliation | Academia | Edith Elkind Oxford University, UK. elkind@cs.ox.ac.uk Angelo Fanelli CNRS (UMR-6211), France. angelo.fanelli@unicaen.fr Michele Flammini DISIM University of L Aquila & Gran Sasso Science Institute, Italy. michele.flammini@univaq.it |
| Pseudocode | No | The paper is theoretical and focuses on mathematical proofs and definitions; it does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not involve empirical studies with datasets, therefore no training dataset information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical studies with datasets, therefore no validation dataset split information is provided. |
| Hardware Specification | No | This is a theoretical paper and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not involve empirical work that would list software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not involve empirical experiments requiring details such as hyperparameters or training settings. |