powerRelationGenerator {socialranking} | R Documentation |
Generate power relations
Description
Based on a list of coalitions, create a generator function that returns a new PowerRelation
object with every call.
NULL
is returned once every possible power relation has been generated.
Usage
powerRelationGenerator(coalitions, startWithLinearOrder = FALSE)
Arguments
coalitions |
List of coalition vectors. An empty coalition can be set with |
startWithLinearOrder |
If set to |
Details
Using the partitions
library, partitions::compositions()
is used to create all possible partitions over the set of coalitions.
For every partition, partitions::multinomial()
is used to create all permutations over the order of the coalitions.
Note that the number of power relations (or total preorders) grows incredibly fast.
The Stirling number of second kind S(n,k)
gives us the number of k
partitions over n
elements.
S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n
For example, with 4 coalitions (n = 4) there are 6 ways to split it into k = 3 partitions.
The sum of all partitions of any size is also known as the Bell number (B_n = \sum_{k=0}^n S(n,k)
, see also numbers::bell()
).
Regarding total preorders \mathcal{T}(X)
over a set X
, the Stirling number of second kind can be used to determine the number of all possible total preorders |\mathcal{T}(X)|
.
|\mathcal{T}(X)| = \sum_{k=0}^{|X|} k! * S(|X|, k)
In literature, it is referred to as the ordered Bell number or Fubini number.
In the context of social rankings we may consider total preorders over the set of coalitions 2^N
for a given set of elements or players N
.
Here, the number of coalitions doubles with every new element.
The number of preorders then are:
# of elements | # of coalitions | # of total preorders | 1ms / computation |
0 | 1 | 1 | 1ms |
1 | 2 | 3 | 3ms |
2 | 4 | 75 | 75ms |
3 | 7 (w/o empty set) | 47,293 | 47 seconds |
3 | 8 | 545,835 | 9 minutes |
4 | 15 (w/o empty set) | 230,283,190,977,853 | 7,302 years |
4 | 16 | 5,315,654,681,981,355 | 168,558 years |
Value
A generator function.
Every time this generator function is called, a different PowerRelation
object is returned.
Once all possible power relations have been generated, the generator function returns NULL
.
See Also
Other generator functions:
generateNextPartition()
Examples
coalitions <- createPowerset(c('a','b'), includeEmptySet = FALSE)
# list(c('a','b'), 'a', 'b')
gen <- powerRelationGenerator(coalitions)
while(!is.null(pr <- gen())) {
print(pr)
}
# (ab ~ a ~ b)
# (ab ~ a) > b
# (ab ~ b) > a
# (a ~ b) > ab
# ab > (a ~ b)
# a > (ab ~ b)
# b > (ab ~ a)
# ab > a > b
# ab > b > a
# a > ab > b
# b > ab > a
# a > b > ab
# b > a > ab
# from now on, gen() always returns NULL
gen()
# NULL
# Use generateNextPartition() to skip certain partitions
gen <- powerRelationGenerator(coalitions)
gen <- generateNextPartition(gen)
gen <- generateNextPartition(gen)
gen()