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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Nathan Arnold,
  • Judy Goldsmith

摘要

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.