Universität zu Köln

Fichtenberger, Hendrik and Rey, Anja ORCID: 0000-0001-7387-6853 (2021). Testing stability properties in graphical hedonic games. Auton. Agents Multi-Agent Syst., 35 (2). DORDRECHT: SPRINGER. ISSN 1573-7454

Full text not available from this repository.

Abstract

In hedonic games, players form coalitions based on individual preferences over the group of players they could belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed in the literature. However, prior research focuses on algorithms with time complexity that is at least linear in the input size. In the light of very large games that arise from, e.g., social networks and advertising, we initiate the study of sublinear time property testing algorithms for existence and verification problems under several notions of coalition stability in a model of hedonic games represented by graphs with bounded degree. In graph property testing, one shall decide whether a given input has a property (e.g., a game admits a stable coalition structure) or is far from it, i.e., one has to modify at least an c-fraction of the input (e.g., the game's preferences) to make it have the property. In particular, we consider verification of perfection, individual rationality, Nash stability, (contractual) individual stability, and core stability. While there is always a Nash-stable coalition structure (which also implies individually stable coalitions), we show that the existence of a perfect coalition structure is not tautological but can be tested. All our testers have one-sided error and time complexity that is independent of the input size.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Fichtenberger, Hendrik UNSPECIFIED UNSPECIFIED UNSPECIFIED Rey, Anja UNSPECIFIED orcid.org/0000-0001-7387-6853 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-574970
DOI:	10.1007/s10458-021-09505-x
Journal or Publication Title:	Auton. Agents Multi-Agent Syst.
Volume:	35
Number:	2
Date:	2021
Publisher:	SPRINGER
Place of Publication:	DORDRECHT
ISSN:	1573-7454
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language CORE STABILITY Multiple languages Automation & Control Systems; Computer Science, Artificial Intelligence Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/57497