Structured Coalitions in Resource Selection Games

doi:10.1145/1858948.1858952

2010-10-22

PRE

Michal Feldman *

Moshe Tennenholtz

DOI：10.1145/1858948.1858952

原文链接

原文求助

摘要

En 中文

We study stability against coalitional deviations in resource selection games where the coalitions have a certain structure. In particular, the agents are partitioned into coalitions, and only deviations by the prescribed coalitions are considered. This is in contrast to the classical concept of strong equilibrium according to which any subset of the agents may deviate. In resource selection games, each agent selects a resource from a set of resources, and its payoff is an increasing (or nondecreasing) function of the number of agents selecting its resource. While it has been shown that a strong equilibrium always exists in resource selection games, a closer look reveals severe limitations to the applicability of the existence result even in the simplest case of two identical resources with increasing cost functions. First, these games do not possess a super strong equilibrium in which a fruitful deviation benefits at least one deviator without hurting any other deviator. Second, a strong equilibrium may not exist when the game is played repeatedly. We prove that for any given partition, there exists a super strong equilibrium for resource selection games of identical resources with increasing cost functions. In addition, we show similar existence results for a variety of other classes of resource selection games. For the case of repeated games, we characterize partitions that guarantee the existence of a strong equilibrium. Together, our work introduces a natural concept, which turns out to lead to positive and applicable results in one of the basic domains studied in the literature.

Keyword:

Coalitions

partition

resource selection games

strong equilibrium

repeated games