## Introduction

A common problem in numerical simulation research with shared intentions where an interaction network, *g* *(N,E)* is specified, is to identify connected sub-graphs *S ⊆ N* of size *k*. It is these connected sub-graphs S which may jointly update their actions under the assumption of the sharing of intentions.

The complexity of enumerating feasible coalitions of size *k* depends strongly on the topology of the network.

For example, if *g* is the complete graph, then there are {*|N|* choose *k*} such coalitions, which for the networks of say *|N|* = 256 and coalitions of size *k* equal to 4 or 8, gives rise to over 174 million and over 4E14 ways of forming *S* respectively.

On the other hand, for a 2−regular ring network, there are only *|N|* feasible coalitions of size *k*, since the topology constrains the composition of *S* to *|N|* consecutive index sets, each with a different starting vertex.

However, in most cases, even a small amount of density at the local level complicates the picture dramatically. For this reason, the modeller has a choice of whether to pre-build a library of coalitions for a given *g* and coalition size *k* or construct coalitions as needed at run-time. We demonstrate the latter method below.

## A simple coalition formation algorithm

As in shared intentions and social norms we enumerate a simple coalition formation algorithm. An important property of such an algorithm is that, given a randomly selected vertex, *i*, coalition size *k,* and graph *g*, the algorithm f: {i,k,g} → *S_i* should produce with equal probability any sub-graph *S* of all possible connected sub-graphs which include *i,* *S_i*. The algorithm below satisfies this condition.

__Step 1__: Let the resultant sub-graph be vertex set *s **⊆ S**. *Choose a starting vertex, *i ∈ **N*. Initialise *s = {i}*. In Fig. 1, vertex * a* has been selected. So, set

*s = {*. If

**a**}*|s| = k*, stop and return

*s*, else continue.

__Step 2__: Construct an adjacency vertex set to *s, a **⊆ N\s* comprising the set of adjacent vertices to members of *a*, which are not already in *s*. In Fig. 2 four such vertices have been identified, so set *a = { b,c,i,h}*.

__Step 3__: Choose a single vertex from a, to grow s by one. In Fig. 3, vertex * i* has been chosen, so

*s = {*. If

**a**,**i**}*|s| = k*, stop and return

*s*, else continue, by re-constructing

*a*(Step 2), here

*a = {*

**b**,**c**,**h**,**u**,**t**}.__Step 4__: Repeat Step 3 until stop. In Fig. 4 we follow one more iteration to build a *k = 3* size connected sub-graph, *s = { a,i,h}* (and

*a = {*

**c**,**b**,**u**,**t**,r,s}).