Author name cluster

Anja Rey

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

JAIR Journal 2022 Journal Article

Altruistic Hedonic Games

Anna Maria Kerkmann
Nhan-Tam Nguyen
Anja Rey
Lisa Rey
Jörg Rothe
Lena Schend
Alessandra Wiechers

Hedonic games are coalition formation games in which players have preferences over the coalitions they can join. For a long time, all models of representing hedonic games were based upon selfish players only. Among the known ways of representing hedonic games compactly, we focus on friend-oriented hedonic games and propose a novel model for them that takes into account not only the players’ own preferences but also their friends’ preferences. Depending on the order in which players look at their own or their friends’ preferences, we distinguish three degrees of altruism: selfish-first, equal-treatment, and altruistic-treatment preferences. We study both the axiomatic properties of these games and the computational complexity of problems related to various common stability concepts.

PDF Details DOI

JAAMAS Journal 2021 Journal Article

Testing stability prop erties in graphical hedonic games

Hendrik Fichtenberger
Anja Rey

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 \(\epsilon\) -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.

Details DOI

JAIR Journal 2020 Journal Article

Hedonic Games with Ordinal Preferences and Thresholds

Anna Maria Kerkmann
Jérôme Lang
Anja Rey
Jörg Rothe
Hilmar Schadrack
Lena Schend

We propose a new representation setting for hedonic games, where each agent partitions the set of other agents into friends, enemies, and neutral agents, with friends and enemies being ranked. Under the assumption that preferences are monotonic (respectively, antimonotonic) with respect to the addition of friends (respectively, enemies), we propose a bipolar extension of the responsive extension principle, and use this principle to derive the (partial) preferences of agents over coalitions. Then, for a number of solution concepts, we characterize partitions that necessarily or possibly satisfy them, and we study the related problems in terms of their complexity.

PDF Details DOI

AAMAS Conference 2019 Conference Paper

Testing Individual-Based Stability Properties in Graphical Hedonic Games

Hendrik Fichtenberger
Amer Krivošija
Anja Rey

In hedonic games, players form coalitions based on individual preferences over the group of players they belong to. Several concepts to describe the stability of coalition structures in a game have been proposed and analysed. 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 ϵ-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, and (contractual) individual stability. Furthermore, we show that while there is always a Nash-stable coalition (which also implies individually stable coalitions), the existence of a perfect coalition can be tested. All our testers have one-sided error and time complexity that is independent of the input size.

PDF

IJCAI Conference 2018 Conference Paper

A Property Testing Framework for the Theoretical Expressivity of Graph Kernels

Nils M. Kriege
Christopher Morris
Anja Rey
Christian Sohler

Graph kernels are applied heavily for the classification of structured data. However, their expressivity is assessed almost exclusively from experimental studies and there is no theoretical justification why one kernel is in general preferable over another. We introduce a theoretical framework for investigating the expressive power of graph kernels, which is inspired by concepts from the area of property testing. We introduce the notion of distinguishability of a graph property by a graph kernel. For several established graph kernels we show that they cannot distinguish essential graph properties. In order to overcome this, we consider a kernel based on k-disc frequencies. We show that this efficiently computable kernel can distinguish fundamental graph properties. Finally, we obtain learning guarantees for nearest neighbor classifiers in our framework.

PDF Details

AAMAS Conference 2016 Conference Paper

Altruistic Hedonic Games

Nhan-Tam Nguyen
Anja Rey
Lisa Rey
Jörg Rothe
Lena Schend

Hedonic games are coalition formation games in which players have preferences over the coalitions they can join. All models of representing hedonic games studied so far are based upon selfish players only. Among the known ways of representing hedonic games compactly, we focus on friend-oriented hedonic games and propose a novel model for them that takes into account not only a player’s own preferences but also her friends’ preferences under three degrees of altruism. We study both the axiomatic properties of these games and the computational complexity of problems related to various stability concepts.

PDF

MFCS Conference 2016 Conference Paper

Structural Control in Weighted Voting Games

Anja Rey
Jörg Rothe

Inspired by the study of control scenarios in elections and complementing manipulation and bribery settings in cooperative games with transferable utility, we introduce the notion of structural control in weighted voting games. We model two types of influence, adding players to and deleting players from a game, with goals such as increasing a given player's Shapley-Shubik or probabilistic Penrose-Banzhaf index in relation to the original game. We study the computational complexity of the problems of whether such structural changes can achieve the desired effect.

Details

AAMAS Conference 2016 Conference Paper

Structural Control in Weighted Voting Games (Extended Abstract)

Anja Rey
Jörg Rothe

Inspired by the study of control scenarios in elections and complementing manipulation and bribery settings in cooperative games with transferable utility, we introduce the notion of structural control in weighted voting games. We model two types of influence, adding players to and deleting players from a game, with goals such as increasing a given player’s Shapley–Shubik power index in relation to the original game. We study the complexity of the problems of whether such structural changes can achieve the desired effect.

PDF

ECAI Conference 2012 Conference Paper

Probabilistic Path-Disruption Games

Anja Rey
Jörg Rothe

Path-disruption games, recently introduced by Bachrach and Porat [1], are coalitional games played on graphs where one or multiple adversaries each seek to reach a given target vertex from a given source vertex and a coalition of agents seeks to prevent that from happening by blocking every path from the source to the target, for each adversary. We expand their model by allowing uncertainty about the targets. In probabilistic path-disruption games, we assign to each vertex the probability that an adversary wants to reach it. We study the complexity of various problems related to such games.

Details

ECAI Conference 2010 Conference Paper

Complexity of Merging and Splitting for the Probabilistic Banzhaf Power Index in Weighted Voting Games

Anja Rey
Jörg Rothe

The Banzhaf power index is a prominent measure of a player's influence for coalition formation in weighted voting games, an important class of simple coalitional games that are fully expressive but compactly representable. For the normalized Banzhaf index, Aziz and Paterson [1] show that it is NP-hard to decide whether merging any coalition of players is beneficial, and that in unanimity games, merging is always disadvantageous, whereas splitting is always advantageous. We show that for the probabilistic Banzhaf index (which is considered more natural than the normalized Banzhaf index), the merging problem is in P for coalitions of size two, and is NP-hard for coalitions of size at least three. We also prove a corresponding result for the splitting problem. In unanimity games and for the probabilistic Banzhaf index (in strong contrast with the results for the normalized Banzhaf index), we show that splitting is always disadvantageous or neutral, whereas merging is neutral for size-two coalitions, yet advantageous for coalitions of size at least three.

Details