Core Stability and Nash Stability in k-Tiered Coalition Formation Games

Abstract

The problem of $\boldsymbol{k}$-tiered coalition formation games ($\boldsymbol{k}$-TCFGs) has been considered for ranking members of a stochastic, intransitive round robin tournament, with the restriction that the ordering must have exactly $\boldsymbol{k}$ nonempty ranks for some integer $\boldsymbol{k}$. As with other coalition formation games, an outcome of a $\boldsymbol{k}$-TCFG may be evaluated for its stability, using the notions of Nash stability or core stability. An outcome is Nash stable if no one agent can move to a more preferable position, either by forming its own coalition or joining an existing one. An outcome is core stable if no set of agents can form a new coalition such that all agents in the set benefit. Previous research on $\boldsymbol{k}$-TCFGs has focused on preferences derived from matchups, and has indicated that, under these matchup-oriented preferences, core stable outcomes may be significantly easier to find than Nash stable outcomes. However, the extent of this trend has not been explored. Here, we prove that for a key subset of $\boldsymbol{k}$-TCFGs with matchup-oriented preferences, there is always at least one core stable partition. We include an illustration of the difference between Nash stabilizability and core stabilizability on an example game. We introduce a preference notation that can be used to represent any preference framework for $\boldsymbol{k}$-TCFGs, and prove that under the subset of $\boldsymbol{k}$-TCFGs which this notation can represent within polynomial space, the problem of determining if a game has a Nash stable list is NP-complete.