Source-linked AI summary
A Generic Approach to Coalition Formation
Krzysztof R. Apt, Andreas Witzel
TL;DR
The paper asks how coalitions form and under what assumptions arbitrary sequences of merges and splits produce unique outcomes. It develops a comparison-relation framework with stable partitions and applies the approach to TU-games, hedonic games, and exchange economy games.
Problem
The paper studies how coalitions form and when arbitrary sequences of merges and splits have unique outcomes.
Method
The paper models coalition formation through merge and split operations governed by comparison relations satisfying irreflexivity, transitivity, and monotonicity.
Results
The paper identifies conditions yielding unique outcomes and establishes equivalences involving the outcome of every merge/split iteration and unique Dp-stable and Dc-stable partitions.
Takeaways & Limitations
The framework and results apply naturally beyond TU-games to hedonic games and exchange economy games.
Takeaways & Limitations
The approach is limited to merges and splits, with transfers and swaps left as possible extensions.
Abstract
from arXiv · showhide
We propose an abstract approach to coalition formation that focuses on simple merge and split rules transforming partitions of a group of players. We identify conditions under which every iteration of these rules yields a unique partition. The main conceptual tool is a specific notion of a stable partition. The results are parametrized by a preference relation between partitions of a group of players and naturally apply to coalitional TU-games, hedonic games and exchange economy games.
1 Introduction
The paper studies how coalitions form through merges and splits, asking when arbitrary sequences of these operations have a unique outcome. It develops an abstract preference-based framework applicable across several coalition-formation settings.
- Approach: Coalitions form through merges and splits whenever the resulting partition is preferred under a comparison relation.The framework focuses on partial preferences between partitions and transforms them using simple rules.
- Approach: The framework seeks assumptions ensuring that arbitrary merge-and-split sequences yield the same partition.Under these conditions, every initial partition can reach a specific preferred partition regardless of rule order.
- Approach: The comparison relation requires only irreflexivity, transitivity, and monotonicity, without a specific coalitional-game model.This parametrization makes the approach independent of any particular game representation.
- Applications: The results apply to TU-games, hedonic games, and exchange economy games.For TU-games, several established orders, including leximin and Nash order, induce relations satisfying the required properties.
- Positioning: The approach is indirectly inspired by abstract reduction systems, which study conditions guaranteeing unique outcomes of rule iterations.The paper notes that its different starting point makes direct comparison with much of the coalition-formation literature difficult.
2 Comparing and transforming collections
The paper defines comparison relations over partitions of the same player set and uses them to specify local merge and split transformations. Irreflexivity and transitivity guarantee termination, while further conditions support unique outcomes.
- Comparing collections: Collections are compared only when they partition the same set of players, with A ▷ B meaning A is preferred to B.Partitions of different player sets are incomparable under the relation.
- Comparison relations: A comparison relation is irreflexive, transitive, and monotonic in two senses concerning disjoint collections.These properties are formalized as conditions (m1) and (m2).
- Transformation rules: Merge and split rules transform a partition when the resulting local collection is preferred under ▷.The rules compare only the coalitions involved in, or produced by, the transformation.
- Unique outcomes: When the stated conditions hold, arbitrary merge-and-split sequences yield the same preferred partition.This motivates the paper’s stable-partition concept.
- Termination: Every iteration terminates because each step strictly improves a relation over finitely many partitions.The proof uses transitivity and irreflexivity together with the finite number of possible partitions.
3 TU-games
For TU-games, the paper induces partition preferences by comparing multisets of coalition values and examines several orders. Utilitarian, Nash, and leximin relations satisfy the required monotonicity properties, whereas other natural orders do not.
- Value-based comparisons: A TU-game is a pair (N, v), and a collection’s value is the multiset of its coalition values.The induced comparison is A ▷ B iff v(A) ▷ v(B).
- Standard orders: The Nash order favors equal distribution because its underlying sum is largest when component values are equal.The paper uses this order among several established TU-game preferences.
- Standard orders: The utilitarian, Nash, and leximin orders are irreflexive, transitive, and monotonic in both senses.Their induced collection relations are therefore valid comparison relations.
- Orders outside the framework: The average order fails monotonicity (m1): a ▷av b and c ▷av d need not imply a ∪ c ▷av b ∪ d.The paper gives multisets {3}, {2,2,2,2}, {1,1,1,1}, and {0} as a counterexample.
- Orders outside the framework: The elitist and egalitarian orders fail monotonicity (m2).The paper exhibits comparisons that hold for singleton multisets but fail after combining values.
4 Individual values
The paper compares coalition preferences based on coalition values with preferences based on individual payoffs. It shows that these approaches generally cannot reproduce one another, except that utilitarian comparisons coincide.
- Individual values: Individual value functions assign each coalition’s value to its members as player-level payoffs.The paper assumes efficiency, meaning the coalition’s value is exactly distributed among its members.
- Individual values: Individual-value comparisons produce multisets of one payoff per player, making the comparison anonymous with respect to player names.For a collection over a player set, the multiset contains |S C| real numbers.
- Relationship between approaches: Utilitarian comparisons based on coalition values and individual values are equivalent for all collections.This is the paper’s positive equivalence result between the two approaches.
- Relationship between approaches: In general, an anonymous individual value function cannot reproduce arbitrary coalition-value preferences, even for anonymous TU-games.The impossibility holds for the Nash order in the stated result.
- Relationship between approaches: Conversely, coalition-value preferences generally cannot reproduce individual-value preferences, even with anonymous functions and Nash or leximin orders.The paper concludes that the two approaches are fundamentally different and coincide only for utilitarian order.
- Individual-payoff orders: The majority order is not transitive, whereas the Pareto order is transitive, irreflexive, and monotonic in both senses.Both relations compare fixed-length payoff sequences.
5 Stable partitions
Stable partitions are defined relative to a defection function and a comparison relation, capturing when deviations are not preferred. Under the partition-based defection function, stability is equivalent to comparison maximality, while collection-based stability may fail to exist.
- Framework: A defection function D assigns each partition collections whose players may leave and regroup, with Dp allowing partitions and Dc allowing collections.The framework compares the regrouping collection with its representation in the original partition's frame.
- Framework: C[P] represents collection C in the frame of partition P by intersecting coalitions with partition blocks and removing empty sets.If C is a partition, C[P] = P; if C consists of partition coalitions, C[P] = C.
- Stable partitions: A partition P is D-stable when C[P] ▷ C for every permitted deviation C whose framed collection differs from C.The inequality excludes deviations that preserve the same partition of the deviating players.
- Stable partitions: A partition is Dp-stable if and only if it is ▷-maximal among partitions of N.Thus, under a semi-linear comparison relation, a Dp-stable partition exists.
- Stable partitions: Dc-stable partitions need not exist even when the comparison relation is semi-linear.For N = {1, 2, 3}, the specified comparisons rule out stability for the singleton partition and for every partition containing a two-player coalition.
6 Stable partitions and merge/split rules
The paper characterizes Dc-stability through compatibility conditions and uses that characterization to connect stable partitions with merge and split dynamics. A Dc-stable partition is closed under these rules and is the unique outcome and unique stable partition under the stated conditions.
- Stable partitions and merge/split rules: The analysis seeks conditions under which every iteration of the merge and split rules yields the same outcome, expressed through Dc-stable partitions.The proof proceeds via lemmas concerning closure and uniqueness.
- Closure and uniqueness: Every Dc-stable partition is closed under applications of the merge and split rules.The proof handles closure under merging and splitting, with the split case shown analogously.
- Characterizing Dc-stability: A coalition is P-compatible when it lies within one block of P; otherwise it is P-incompatible.This distinction underlies the characterization of Dc-stability.
- Characterizing Dc-stability: Lemma 13 characterizes Dc-stability using conditions on disjoint coalitions within partition blocks and on P-incompatible coalitions.Figure 2 illustrates the compatible coalitions A and B and the incompatible coalition T used in the lemma.
- Closure and uniqueness: If P is Dc-stable and P′ is closed under merge and split applications, then P′ = P.If a block is absent from P′, either a merge or a split remains applicable, contradicting closure.
- Main theorem: A Dc-stable partition P is the outcome of every merge/split iteration, and it is the unique Dp-stable and unique Dc-stable partition.Termination of every iteration combines with closure and uniqueness to establish these conclusions.
7 Applications
The abstract merge-and-split results are applied to coalitional TU-games, hedonic games, and exchange economy games. In each application, suitable preference relations and constructions yield a partition that is the outcome of every iteration of the rules.
- Applications: The applications cover coalitional TU-games, hedonic games, and exchange economy games, while the obtained results themselves do not require a game model.The framework is parametrized by comparison relations between partitions.
- Coalitional TU-games: Semi-unions of strictly superadditive TU-games make a chosen partition Dc-stable, so every merge-and-split iteration has that partition as its outcome.The semi-union reduces payoffs for P-incompatible coalitions while preserving them for other coalitions.
- Hedonic games: In hedonic games, comparing partitions by players’ coalition preferences makes a partition Dc-stable and therefore the outcome of every merge-and-split iteration.The comparison requires every player to weakly prefer the coalition assigned in one partition, with at least one strict preference.
- Exchange economy games: In the exchange economy construction, each player receives one good for each friend in the target partition and prefers bundles with more goods of their own type.The resulting comparison relation makes the target partition Dc-stable, so Theorem 15 gives it as the outcome of every iteration.
8 Conclusions
The paper presents coalition formation through preference-improving merges and splits, and identifies conditions guaranteeing a unique outcome and stable partition. The approach applies beyond TU-games to hedonic and exchange economy games, while transfers and swaps remain possible extensions.
- Merges and splits occur when they improve a comparison relation on partitions of the involved players.The relation is required to satisfy irreflexivity, transitivity, and monotonicity.
- Irreflexivity, transitivity, and monotonicity are sufficient properties for the generic comparison relation used by the approach.The framework does not depend on a specific coalitional-game model.
- Natural conditions ensure that every iteration of merges and splits yields a unique outcome, motivating the notion of a stable partition.
- The approach and results apply to coalitional TU-games, hedonic games, and exchange economy games.
- Extending the framework to transfers or swaps would broaden the transformations allowed beyond merges and splits.Transfers move part of one coalition to another, while swaps exchange subsets of two coalitions.