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

The problem of k-tiered coalition formation games (k-TCFGs) has been considered for ranking members of a stochastic, intransitive round robin tournament, with the restriction that the ordering must have exactly k nonempty ranks for some integer k. As with other coalition formation games, an outcome of a 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 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 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 k-TCFGs, and prove that under the subset of 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.