Constructing a Coalition Library

As in “Emergence of Shared Intentions is Coupled to the Advance of Cumulative Culture” (Angus & Newton, 2015) we enumerate an algorithm which, given g, k, and a binary |N|-length vector, type where the ith entry of type implies whether agent i is SI type (‘1’) or N type (‘0’), will return all possible coalitions of size 2..k in a useful data structure.

The algorithm proceeds in a similar way to the formation of a single coalition, however, moving sequentially from coalitions of size 2, to coalitions of size 3, and so on, up to coalitions of size k, using the (k-1)th coalition set as the seed set at each iteration.

library1Consider the over-lapping triangles graph, g depicted in Fig. 1. Here, only vertices {a,b,c,d,f,g,n,t,u} are SI type (able to share intentions), with the rest being N type (not able to share intentions).

library2Since N type agents cannot form coalitions larger than singletons, nor can they facilitate coalitions among SI types, they (together with their adjacent edges) can be removed from the graph (Fig. 2).

library3Next, the smallest non-singleton coalitions of size k=2 can be formed immediately by collecting any adjacent vertex-pair (Fig. 3).

library4For coalitions of size k>2, an iterative process is conducted whereby all coalitions of size k-1 are used as seeds, with single vertices adjacent to a member of an existing seed coalition used to form a larger coalition. In the case of Fig. 4, the {b,d} k=2 coalition seed is considered, leading to the formation of two new k=3 coalitions, {a,b,d} and {a,c,d}.

Note, coalitions of size k>2 can be reached by the algorithm by the growth from distinct seeds, however, only a single replicate of such a coalition would be stored in the library.

Implementation

The above algorithm is implemented in Matlab®  in the routine “GetAllCoalitions_k.m” which can be downloaded as part of the accompanying codes to Angus & Newton (2015).