1 Introduction

In the literature of cooperative games, the notion of power index [1–3] has been widely studied to analyze the “influence” of individuals taking into account their ability to force a decision within groups or coalitions. In practical situations, however, the information concerning the strength of coalitions is hardly quantifiable. So, any attempt to numerically represent the influence of groups and individuals clashes with the complex and multi-attribute nature of the problem and it seems more realistic to represent collective decision-making mechanisms using an ordinal coalitional framework based on two main ingredients: a binary relation over groups or coalitions and a ranking over the individuals.

The main objective of the package socialranking is to provide answers for the general problem of how to compare the elements of a finite set \(N\) given a ranking over the elements of its power-set (the set of all possible subsets of \(N\)). To do this, the package socialranking implements a portfolio of solutions from the recent literature on social rankings [4–11].

1.1 Quick start

A power relation (i.e, a ranking over subsets of a finite set \(N\); see the Section on PowerRelation objects for a formal definition) can be constructed using the functions PowerRelation() or as.PowerRelation().

library(socialranking)
PowerRelation(list(list(c(1,2)), list(1, c()), list(2)))
## 12 > (1 ~ {}) > 2
as.PowerRelation("12 > 1 ~ {} > 2")
## 12 > (1 ~ {}) > 2
as.PowerRelation("ab > a ~ {} > b")
## ab > (a ~ {}) > b
as.PowerRelation(list(c(1,2), 1, c(), 2))
## 12 > 1 > {} > 2
as.PowerRelation(list(c(1,2), 1, c(), 2), comparators = c(">", "~", ">"))
## 12 > (1 ~ {}) > 2

Functions used to analyze a given PowerRelation object can be grouped into three main categories:

  • Comparison functions, only comparing two elements;
  • Score functions, calculating the scores for each element;
  • Ranking functions, creating SocialRanking objects.

Comparison and score functions are often used to evaluate a social ranking solution (see section on PowerRelation objects for a formal definition). Listed below are some of the most prominent functions and solutions introduced in the aforementioned papers.

Comparison functions Score functions Ranking functions
dominates()
cumulativelyDominates() cumulativeScores()
cpMajorityComparison()
cpMajorityComparisonScore() 		copelandScores()
kramerSimpsonScores() 		copelandRanking()
kramerSimpsonRanking()
lexcelScores() lexcelRanking()
dualLexcelRanking()
L1Scores()
L2Scores()
LPScores()
LPSScores() 		L1Ranking()
L2Ranking()
LPRanking()
LPSRanking()
ordinalBanzhafScores() ordinalBanzhafRanking()

These functions may be called as follows.

pr <- as.PowerRelation("ab > abc ~ ac ~ bc > a ~ c > {} > b")

# a dominates b, but b does not dominate a
c(dominates(pr, "a", "b"),
  dominates(pr, "b", "a"))
## [1]  TRUE FALSE
# calculate cumulative scores
scores <- cumulativeScores(pr)
# show score of element a
scores$a
## [1] 1 3 4 4 4
# performing a bunch of rankings
lexcelRanking(pr)
## a > b > c
L1Ranking(pr)
## a > b > c
dualLexcelRanking(pr)
## a > c > b
copelandRanking(pr)
## a > b ~ c
kramerSimpsonRanking(pr)
## a > b ~ c
ordinalBanzhafRanking(pr)
## a > c > b

Lastly, an incidence matrix for all given coalitions can be constructed using powerRelationMatrix(pr) or as.relation(pr) from the relations package [12]. The incidence matrix may be displayed using relations::relation_incidence().

rel <- relations::as.relation(pr)
rel
## A binary relation of size 8 x 8.
relations::relation_incidence(rel)
## Incidences:
##     ab ​abc ​​ac ​​​bc ​​​​a ​​​​​c ​​​​​​{} ​​​​​​​b
## ab   1   1  1  1 1 1  1 1
## ​abc  0   1  1  1 1 1  1 1
## ​​ac   0   1  1  1 1 1  1 1
## ​​​bc   0   1  1  1 1 1  1 1
## ​​​​a    0   0  0  0 1 1  1 1
## ​​​​​c    0   0  0  0 1 1  1 1
## ​​​​​​{}   0   0  0  0 0 0  1 1
## ​​​​​​​b    0   0  0  0 0 0  0 1

2 PowerRelation objects

We first introduce some basic definitions on binary relations. Let \(X\) be a set. A set \(R \subseteq X \times X\) is said a binary relation on \(X\). For two elements \(x, y \in X\), \(xRy\) refers to their relation, more formally it means that \((x,y) \in R\). A binary relation \((x,y) \in R\) is said to be

  • reflexive, if for each \(x \in X, xRx\),
  • transitive, if for each \(x, y, z \in X, xRy\) and \(yRz \Rightarrow xRz\),
  • total, if for each \(x,y \in X, x \neq y \Rightarrow xRy\) or \(yRx\),
  • symmetric, if for each \(x,y \in X,xRy \Leftrightarrow yRx\),
  • asymmetric, if for each \(x,y \in X,(x,y) \in R \Rightarrow (y,x) \notin R\), and
  • antisymmetric, if for each \(x,y \in X,xRy \cap yRx \Rightarrow x=y\).

A preorder is defined as a reflexive and transitive relation. If it is total, it is called a total preorder. Additionally if it is antisymmetric, it is called a linear order.

Let \(N = \{1, 2, \dots, n\}\) be a finite set of elements, sometimes also called players. For some \(p \in \{1, \ldots, 2^n\}\), let \(\mathcal{P} = \{S_1, S_2, \dots, S_{p}\}\) be a set of coalitions such that \(S_i \subseteq N\) for all \(i \in \{1, \ldots, p\}\). Thus \(\mathcal{P} \subseteq 2^N\), where \(2^N\) denotes the power set of \(N\), the set of all subsets or coalitions of \(N\).

\(\mathcal{T}(N)\) denotes the set of all total preorders on \(N\), \(\mathcal{T}(\mathcal{P})\) the set of all total preorders on \(\mathcal{P}\). A single total preorder \(\succsim \in \mathcal{T}(\mathcal{P})\) is said a power relation.

In a given power relation \(\succsim \in \mathcal{T}(\mathcal{P})\) on \(\mathcal{P} \subseteq 2^N\), its symmetric part is denoted by \(\sim\) (i.e., \(S \sim T\) if \(S \succsim T\) and \(T \succsim S\)), whereas its asymmetric part is denoted by \(\succ\) (i.e., \(S \succ T\) if \(S \succsim T\) and not \(T \succsim S\)). In other terms, for \(S \sim T\) we say that \(S\) is indifferent to \(T\), whereas for \(S \succ T\) we say that \(S\) is strictly better than \(T\).

Lastly, for a given power relation in the form of \(S_1 \succsim S_2 \succsim \ldots \succsim S_m\), coalitions that are indifferent to one another can be grouped into equivalence classes \(\sum_i\) such that we get the quotient order \(\sum_1 \succ \sum_2 \succ \ldots \succ \sum_m\).

Let \(N=\{1,2\}\) be two players with its corresponding power set \(2^N = \{\{1,2\}, \{1\}, \{2\}, \emptyset\}\). The following power relation is given:

\[ \begin{array}{rrrr} \succsim \ =\ \{(\{1,2\},\{1,2\}), & (\{1,2\},\{2\}), & (\{1,2\},\emptyset), & (\{1,2\},\{1\}),\hphantom{\}}\\ & (\{2\}, \{2\}), & (\{2\}, \emptyset), & \hphantom{1,}(\{2\}, \{1\}),\hphantom{\}}\\ & (\emptyset, \emptyset), & (\emptyset, \{2\}), & (\emptyset, \{1\}),\hphantom{\}}\\ & & & (\{1\}, \{1\})\hphantom{,}\} \end{array} \]

This power relation can be rewritten in a consecutive order as: \(\{1,2\} \succ \{2\} \sim \emptyset \succ \{1\}\). Its quotient order is formed by three equivalence classes \(\sum_1 = \{\{1,2\}\}, \sum_2 = \{\{2\}, \emptyset\},\) and \(\sum_3 = \{\{1\}\}\); so the quotient order of \(\succsim\) is such that \(\{\{1,2\}\} \succ \{\{2\}, \emptyset\} \succ \{\{1\}\}\).

Note that the way the set \(\succsim\) is presented in the example is somewhat deliberate to better visualize occurring symmetries and asymmetries. This also lets us neatly represent a power relation in the form of an incidence matrix.

2.1 Creating PowerRelation objects

A power relation in the socialranking package is defined to be reflexive, transitive and total. In designing the package it was deemed logical to have the coalitions specified in a consecutive order, as seen in Example 1. Each coalition in that order is split either by a ">" (left side strictly better) or a "~" (two coalitions indifferent to one another). The following code chunk shows the power relation from Example 1 and how a correlating PowerRelation object can be constructed.

library(socialranking)
pr <- PowerRelation(list(
  list(c(1,2)),
  list(2, c()),
  list(1)
))
pr
## 12 > (2 ~ {}) > 1
class(pr)
## [1] "PowerRelation"      "SingleCharElements"

Notice how coalitions such as \(\{1,2\}\) are written as 12 to improve readability. Similarly, passing a string to the function as.PowerRelation() saves some typing on the user’s end by interpreting each character of a coalition as a separate element. Note that spaces in that function are ignored.

as.PowerRelation("12 > 2~{} > 1")
## 12 > (2 ~ {}) > 1

The compact notation is only done in PowerRelation objects where every element is one digit or one character long. If this is not the case, curly braces and commas are added where needed.

prLong <- PowerRelation(list(
  list(c("Alice", "Bob")), 
  list("Bob", c()),
  list("Alice")
))
prLong
## {Alice, Bob} > ({Bob} ~ {}) > {Alice}
class(prLong)
## [1] "PowerRelation"

Some may have spotted a "SingleCharElements" class missing in class(prLong) that has been there in class(pr). "SingleCharElements" influences how coalitions are printed. If it is removed from class(pr), the output will include the same curly braces and commas displayed in prLong.

class(pr) <- class(pr)[-which(class(pr) == "SingleCharElements")]
pr
## {1, 2} > ({2} ~ {}) > {1}

Internally a PowerRelation is a list with four attributes.

Attribute Description Value in pr
elements Sorted vector of elements c(1,2)
eqs List containing lists, each
containing coalitions in the
same equivalence class 		list(list(c(1,2)),
list(c(2), c()),
list(c(1)))
coalitionLookup Function to determine a coalition's
equivalence class index 		function(coalition)
elementLookup Function to determine, which coalitions
an element takes part in 		function(element)

While coalitions are formally defined as sets, meaning the order doesn’t matter and each element is unique, the package tries to stay flexible. As such, coalitions will only be sorted during initialization, but duplicate elements will not be removed.

prAtts <- PowerRelation(list(
  list(c(2,2,1,1,2)),
  list(c(2,1), c())
))
## Warning in createLookupTables(equivalenceClasses): Found 1 coalition that contain elements more than once.
##     - 1, 2 in the coalition {1, 1, 2, 2, 2}
prAtts
## 11222 > (12 ~ {})
prAtts$elements
## [1] 1 2
prAtts$coalitionLookup(c(1,2))
## [1] 2
prAtts$coalitionLookup(c(2,1))
## [1] 2
prAtts$coalitionLookup(c(2,1,2,1,2))
## [1] 1
prAtts$elementLookup(2)
## [[1]]
## [1] 1 1
## 
## [[2]]
## [1] 1 1
## 
## [[3]]
## [1] 1 1
## 
## [[4]]
## [1] 2 1

2.2 Manipulating PowerRelation objects

It is strongly discouraged to directly manipulate PowerRelation objects, as its attributes are so tightly coupled. This would require updates in multiple places. Instead, it is advisable to simply create new PowerRelation objects.

To permutate the order of equivalence classes, it is possible to take the equivalence classes in $eqs and use a vector of indexes to move them around.

pr <- as.PowerRelation("12 > (1 ~ {}) > 2")
PowerRelation(pr$eqs[c(2, 3, 1)])
## (1 ~ {}) > 2 > 12
PowerRelation(rev(pr$eqs))
## 2 > (1 ~ {}) > 12

For permutating individual coalitions, using as.PowerRelation.list() may be more convenient since it doesn’t require nested list indexing.

coalitions <- unlist(pr$eqs, recursive = FALSE)
compares <- c(">", "~", ">")
as.PowerRelation(coalitions[c(2,1,3,4)], comparators = compares)
## 1 > (12 ~ {}) > 2
# notice that the length of comparators does not need to match
# length(coalitions)-1
as.PowerRelation(rev(coalitions), comparators = c("~", ">"))
## (2 ~ {}) > (1 ~ 12)
# not setting the comparators parameter turns it into a linear order
as.PowerRelation(coalitions)
## 12 > 1 > {} > 2

2.2.1 appendMissingCoalitions()

Let \(\succsim \in \mathcal{T}(\mathcal{P})\). We may have not included all possible coalitions, such that \(\mathcal{P} \subset 2^N, \mathcal{P} \neq 2^N\).

appendMissingCoalitions() appends all the missing coalitions \(2^N - \mathcal{P}\) as a single equivalence class to the end of the power relation.

pr <- PowerRelation(list(
  list(c("AT", "DE"), "FR"),
  list("DE"),
  list(c("AT", "FR"), "AT")
))
pr
## ({AT, DE} ~ {FR}) > {DE} > ({AT, FR} ~ {AT})
# since we have 3 elements, the super set 2^N should include 8 coalitions
appendMissingCoalitions(pr)
## ({AT, DE} ~ {FR}) > {DE} > ({AT, FR} ~ {AT}) > ({AT, DE, FR} ~ {DE, FR} ~ {})

2.2.2 makePowerRelationMonotonic()

A power relation \(\succsim \in \mathcal{T}(\mathcal{P})\) is monotonic if

\[ S \succsim T \quad \Rightarrow \quad T \subset S \]

for all \(S, T \subseteq N\). In other terms, given a monotonic power relation, for any coalition, all its subsets cannot be ranked higher.

makePowerRelationMonotonic() turns a potentially non-monotonic power relation into a monotonic one by moving and (optionally) adding all missing coalitions in \(2^N - \mathcal{P}\) to the corresponding equivalence classes.

pr <- as.PowerRelation("a > b > c ~ ac > abc")
makePowerRelationMonotonic(pr)
## (abc ~ ab ~ ac ~ a) > (bc ~ b) > c
makePowerRelationMonotonic(pr, addMissingCoalitions = FALSE)
## (abc ~ ac ~ a) > b > c
# notice how an empty coalition in some equivalence class
# causes all remaining coalitions to be moved there
makePowerRelationMonotonic(as.PowerRelation("ab > c > {} > abc > a > b"))
## (abc ~ ab) > (ac ~ bc ~ c) > (a ~ b ~ {})

2.3 Creating power sets

As the number of elements \(n\) increases, the number of possible coalitions increases to \(|2^N| = 2^n\). createPowerset() is a convenient function that not only creates a power set \(2^N\) which can be used to call PowerRelation or as.PowerRelation(), but also formats the function call in such a way that makes it easy to rearrange the ordering of the coalitions. RStudio offers shortcuts such as Alt+Up or Alt+Down (Option+Up or Option+Down on MacOS) to move one or multiple lines of code up or down (see fig. below).

createPowerset(
  c("a", "b", "c"),
  result = "print"
)
## as.PowerRelation("
##   abc
##   > ab
##   > ac
##   > bc
##   > a
##   > b
##   > c
##   > {}
## ")
Using Alt+Up or Alt+Down to move one or more lines of code
Using Alt+Up or Alt+Down to move one or more lines of code

By default, createPowerset() returns the power set in the form of a list. This list can be passed directly to as.PowerRelation() to create a linear order.

ps <- createPowerset(1:2, includeEmptySet = FALSE)
ps
## [[1]]
## [1] 1 2
## 
## [[2]]
## [1] 1
## 
## [[3]]
## [1] 2
as.PowerRelation(ps)
## 12 > 1 > 2
# equivalent
PowerRelation(list(ps))
## (12 ~ 1 ~ 2)
as.PowerRelation(createPowerset(letters[1:4]))
## abcd > abc > abd > acd > bcd > ab > ac > ad > bc > bd > cd > a > b > c > d > {}

2.4 Generating PowerRelation objects

For the ease of experimentation, it is possible to have power relations created automatically given a list of coalitions. Either,

  • create random power relations using generateRandomPowerRelation(), or
  • generate a sequence of all possible power relations with powerRelationGenerator().

For the former, one may also specify if the generated power relation should be a linear order (as in, there are no ~ but only strict > relations) and whether or not the power relation should be monotonic (as in, \(\{1\} \succ \{1,2\}\) is not monotonic because \(\{1\} \subset \{1,2\}\)).

set.seed(1)
coalitions <- createPowerset(1:3)
generateRandomPowerRelation(coalitions)
## 13 > (2 ~ 12) > {} > (1 ~ 123) > 23 > 3
generateRandomPowerRelation(coalitions)
## ({} ~ 1 ~ 2 ~ 12 ~ 123) > 3 > 13 > 23
generateRandomPowerRelation(coalitions, linearOrder = TRUE)
## 12 > 2 > 123 > 23 > 13 > 3 > {} > 1
generateRandomPowerRelation(coalitions, monotonic = TRUE)
## (123 ~ 23 ~ 12 ~ 13 ~ 1) > (2 ~ 3 ~ {})
generateRandomPowerRelation(coalitions, linearOrder = TRUE, monotonic = TRUE)
## 123 > 23 > 12 > 2 > 13 > 1 > 3 > {}

For looping through all possible power relations, powerRelationGenerator() returns a generator function that, when called repeatedly, returns one unique PowerRelation object after the other. If all permutations have been exhausted, NULL is returned.

coalitions <- list(c(1,2), 1, 2)
gen <- powerRelationGenerator(coalitions)
while(!is.null(pr <- gen())) {
  print(pr)
}
## (12 ~ 1 ~ 2)
## (12 ~ 1) > 2
## (12 ~ 2) > 1
## (1 ~ 2) > 12
## 12 > (1 ~ 2)
## 1 > (12 ~ 2)
## 2 > (12 ~ 1)
## 12 > 1 > 2
## 12 > 2 > 1
## 1 > 12 > 2
## 2 > 12 > 1
## 1 > 2 > 12
## 2 > 1 > 12

Permutations over power relations can be split into two parts:

  1. generating partitions, or, generating differently sized equivalence classes, and
  2. moving coalitions between these partitions.

In the code example above, we started with a single partition of size three, wherein all coalitions are considered equally preferable. By the end, we have reached the maximum number of partitions, where each coalition is put inside an equivalence class of size 1.

The partition generation can be reversed, such that we first receive linear power relations.

gen <- powerRelationGenerator(coalitions, startWithLinearOrder = TRUE)
while(!is.null(pr <- gen())) {
  print(pr)
}
## 12 > 1 > 2
## 12 > 2 > 1
## 1 > 12 > 2
## 2 > 12 > 1
## 1 > 2 > 12
## 2 > 1 > 12
## 12 > (1 ~ 2)
## 1 > (12 ~ 2)
## 2 > (12 ~ 1)
## (12 ~ 1) > 2
## (12 ~ 2) > 1
## (1 ~ 2) > 12
## (12 ~ 1 ~ 2)

Notice that the “moving coalitions” part was not reversed, only the order the partitions come in.

Similarly, we are also able to skip the current partition.

gen <- powerRelationGenerator(coalitions)
# partition 3

gen <- generateNextPartition(gen)
# partition 2+1

gen <- generateNextPartition(gen)
# partition 1+2
gen()
## 12 > (1 ~ 2)

Note: the number of possible power relations grows tremendously fast as the number of coalitions rises. To get to that number, first consider how many ways \(n\) coalitions can be split into \(k\) partitions, also known as the Stirling number of second kind,

\[ S(n,k) = \frac{1}{k!}\ \sum_{j=0}^k (-1)^j \binom{k}{j}(k-j)^n. \]

The number of all possible partitions given \(n\) coalitions is known as the Bell number (see also numbers::bell()),

\[ B_n = \sum_{j=0}^k S(n,k). \]

Given a set of coalitions \(\mathcal{P} \in 2^N\), the number of total preorders in \(\mathcal{T}(\mathcal{P})\) is

\[ |\mathcal{T}(\mathcal{P})| = \sum_{k=0}^{|\mathcal{P}|} k!\ *\ S(|\mathcal{P}|, k) \]

# of coalitions # of partitions # of total preorders
1 1 1
2 2 3
3 5 13
4 15 75
5 52 541
6 203 4.683
7 877 47.293
8 4.140 545.835
9 21.147 7.087.261
10 115.975 102.247.563
11 678.570 1.622.632.573
12 4.213.597 28.091.567.595
13 27.644.437 526.858.348.381
14 190.899.322 10.641.342.970.441
(\(2^4-1\)) 15 1.382.958.545 230.283.190.977.959
16 10.480.142.147 5.315.654.681.940.580

3 SocialRanking Objects

The main goal of the socialranking package is to rank elements based on a given power ranking. More formally we try to map \(R: \mathcal{T}(\mathcal{P}) \rightarrow \mathcal{T}(N)\), associating to each power relation \(\succsim \in \mathcal{T}(\mathcal{P})\) a total preorder \(R(\succsim)\) (or \(R^\succsim\)) over the elements of \(N\).

In this context \(i R^\succsim j\) tells us that, given a power relation \(\succsim\) and applying a social ranking solution \(R(\succsim)\), \(i\) is ranked higher than or equal to \(j\). From here on out, > and ~ also denote the asymmetric and the symmetric part of a social ranking, respectively, \(i\) > \(j\) indicating that \(i\) is strictly better than \(j\), whereas in \(i\) ~ \(j\), \(i\) is indifferent to \(j\).

In literature, \(i I^\succsim j\) and \(i P^\succsim j\) are often used to denote the symmetric and asymmetric part, respectively. \(i I^\succsim j\) therefore means that \(i R^\succsim j\) and \(j R^\succsim i\), whereas \(i P^\succsim j\) implies that \(i R^\succsim j\) but not \(j R^\succsim j\).

In section 3.1 we show how a general SocialRanking object can be constructed using the doRanking function. In the following sections, we will introduce the notion of dominance[4], cumulative dominance[13] and CP-Majority comparison[6] that lets us compare two elements before diving into the social ranking solutions of the Ordinal Banzhaf Index[5], Copeland-like and Kramer-Simpson-like methods[10], and lastly the Lexicographical Excellence Solution[9] (Lexcel) and the Dual Lexicographical Excellence solution[14] (Dual Lexcel).

Let \(\{a,b\} \succ (\{a,c\} \sim \{b,c\}) \succ (\{a\} \sim \{c\}) > (\{a,b,c\} \sim \emptyset) \succ \{b\}\) be a power ranking. Using the following social ranking solutions, we get:

  • a > b > c for lexcelRanking, L1Ranking and L2Ranking
  • a > c > b for dualLexcelRanking, ordinalBanzhafRanking and LPSRanking
  • a > b ~ c for copelandRanking and kramerSimpsonRanking
  • a ~ c > b for ordinalBanzhafRanking and LPRanking

3.1 Creating SocialRanking objects

A SocialRanking object represents a total preorder in \(\mathcal{T}(N)\) over the elements of \(N\). Internally they are saved as a list of vectors, each containing players that are indifferent to one another. This is somewhat similar to the equivalenceClasses attribute in PowerRelation objects.

The function doRanking offers a generic way of creating SocialRanking objects. Given a sortable vector or list of scores it determines the power relation between all players, where the names of the elements are determined from the names() attribute of scores. Hence, a PowerRelation object is not necessary to create a SocialRanking object.

# we define some arbitrary score vector where "a" scores highest.
# "b" and "c" both score 1, thus they are indifferent.
scores <- c(a = 100, b = 1, c = 1)
doRanking(scores)
## a > b ~ c
# we can also tell doRanking to punish higher scores
doRanking(scores, decreasing = FALSE)
## b ~ c > a

When working with types that cannot be sorted (i.e., lists), a function can be passed to the compare parameter that allows comparisons between arbitrary elements. This function must take two parameters (i.e., a and b) and return a numeric value based on the comparison:

  • compare(a,b) > 0: a scores higher than b,
  • compare(a,b) < 0: a scores lower than b,
  • compare(a,b) == 0: a and b are equivalent.
scores <- list(a = c(3, 3, 3), b = c(2, 3, 2), c = c(7, 0, 2))
doRanking(scores, compare = function(a, b) sum(a) - sum(b))
## a ~ c > b
# a and c are considered to be indifferent, because their sums are the same

doRanking(scores, compare = function(a,b) sum(a) - sum(b), decreasing = FALSE)
## b > a ~ c

3.2 Comparison Functions

Comparison functions only compare two elements in a given power relation. They do not offer a social ranking solution. However in cases such as CP-Majority comparison, those comparison functions may be used to construct a social ranking solution in some particular cases.

3.2.1 Dominance

(Dominance [4]) Given a power relation \(\succsim \in \mathcal{T}(\mathcal{P})\) and two elements \(i,j \in N\), \(i\) dominates \(j\) in \(\succsim\) if \(S \cup \{i\} \succsim S \cup \{j\}\) for each \(S \in 2^{N\setminus \{i,j\}}\). \(i\) also strictly dominates \(j\) if there exists \(S \in 2^{N\setminus \{i,j\}}\) such that \(S \cup \{i\} \succ S \cup \{j\}\).

The implication is that for every coalition \(i\) and \(j\) can join, \(i\) has at least the same positive impact as \(j\).

The function dominates(pr, e1, e2) only returns a logical value TRUE if e1 dominates e2, else FALSE. Note that e1 not dominating e2 does not indicate that e2 dominates e1, nor does it imply that e1 is indifferent to e2.

pr <- as.PowerRelation("3 > 1 > 2 > 12 > 13 > 23")

# 1 clearly dominates 2
dominates(pr, 1, 2)
## [1] TRUE
dominates(pr, 2, 1)
## [1] FALSE
# 3 does not dominate 1, nor does 1 dominate 3, because
# {}u3 > {}u1, but 2u1 > 2u3
dominates(pr, 1, 3)
## [1] FALSE
dominates(pr, 3, 1)
## [1] FALSE
# an element i dominates itself, but it does not strictly dominate itself
# because there is no Sui > Sui
dominates(pr, 1, 1)
## [1] TRUE
dominates(pr, 1, 1, strictly = TRUE)
## [1] FALSE

For any \(S \in 2^{N \setminus \{i,j\}}\), we can only compare \(S \cup \{i\} \succsim S \cup \{j\}\) if both \(S \cup \{i\}\) and \(S \cup \{j\}\) take part in the power relation.

Additionally, for \(S = \emptyset\), we also want to compare \(\{i\} \succsim \{j\}\). In some situations however a comparison between singletons is not desired. For this reason the parameter includeEmptySet can be set to FALSE such that \(\emptyset \cup \{i\} \succsim \emptyset \cup \{j\}\) is not considered in the CP-Majority comparison.

pr <- as.PowerRelation("ac > bc ~ b > a ~ abc > ab")

# FALSE because ac > bc, whereas b > a
dominates(pr, "a", "b")
## [1] FALSE
# TRUE because ac > bc, ignoring b > a comparison
dominates(pr, "a", "b", includeEmptySet = FALSE)
## [1] TRUE

3.2.2 Cumulative Dominance

When comparing two players \(i,j \in N\), instead of looking at particular coalitions \(S \in 2^{N \setminus \{i,j\}}\) they can join, we look at how many stronger coalitions they can form at each point. This property was originally introduced in [13] as a regular dominance axiom.

For a given power relation \(\succsim \in \mathcal{T}(\mathcal{P})\) and its corresponding quotient order \(\sum_1 \succ \dots \succ \sum_m\), the power of a player \(i\) is given by a vector \(\textrm{Score}_\textrm{Cumul}(i) \in \mathbb{N}^m\) where we cumulatively sum the amount of times \(i\) appears in \(\sum_k\) for each index \(k\).

(Cumulative Dominance Score) Given a power relation \(\succsim \in \mathcal{T}(\mathcal{P})\) and its quotient order \(\sum_1 \succ \dots \succ \sum_m\), the cumulative score vector \(\textrm{Score}_\textrm{Cumul}(i) \in \mathbb{N}^m\) of an element \(i \in N\) is given by:

\[\begin{equation} \textrm{Score}_\textrm{Cumul}(i) = \Big( \sum_{t=1}^k |\{S \in \textstyle \sum_t : i \in S\}|\Big)_{k \in \{1, \dots, m\}} \end{equation}\]

(Cumulative Dominance) Given two elements \(i,j \in N\), \(i\) cumulatively dominates \(j\) in \(\succsim\), if \(\textrm{Score}_\textrm{Cumul}(i)_k \geq \textrm{Score}_\textrm{Cumul}(j)_k\) for each \(k \in \{1, \dots, m\}\). \(i\) also strictly cumulatively dominates \(j\) if there exists a \(k\) such that \(\textrm{Score}_\textrm{Cumul}(i)_k > \textrm{Score}_\textrm{Cumul}(j)_k\).

For a given PowerRelation object pr and two elements e1 and e2, cumulativeScores(pr) returns the vectors described in definition 2 for each element, cumulativelyDominates(pr, e1, e2) returns TRUE or FALSE based on definition 3.

pr <- as.PowerRelation("ab > (ac ~ bc) > (a ~ c) > {} > b")
cumulativeScores(pr)
## $a
## [1] 1 2 3 3 3
## 
## $b
## [1] 1 2 2 2 3
## 
## $c
## [1] 0 2 3 3 3
## 
## attr(,"class")
## [1] "CumulativeScores"
# for each index k, $a[k] >= $b[k]
cumulativelyDominates(pr, "a", "b")
## [1] TRUE
# $a[3] > $b[3], therefore a also strictly dominates b
cumulativelyDominates(pr, "a", "b", strictly = TRUE)
## [1] TRUE
# $b[1] > $c[1], but $c[3] > $b[3]
# therefore neither b nor c dominate each other
cumulativelyDominates(pr, "b", "c")
## [1] FALSE
cumulativelyDominates(pr, "c", "b")
## [1] FALSE

Similar to the dominance property from our previous section, two elements not dominating one or the other does not indicate that they are indifferent.

3.2.3 CP-Majority comparison

The Ceteris Paribus Majority (CP-Majority) relation is a somewhat relaxed version of the dominance property. Instead of checking if \(S \cup \{i\} \succsim S \cup \{j\}\) for all \(S \in 2^{N \setminus \{i,j\}}\), the CP-Majority relation \(iR^\succsim_\textrm{CP}j\) holds if the number of times \(S \cup \{i\} \succsim S \cup \{j\}\) is greater than or equal to the number of times \(S \cup \{j\} \succsim S \cup \{i\}\).

(CP-Majority [6]) Let \(\succsim \in \mathcal{T}(\mathcal{P})\). The Ceteris Paribus majority relation is the binary relation \(R^\succsim_\textrm{CP} \subseteq N \times N\) such that for all \(i,j \in N\):

\[\begin{equation} iR^\succsim_\textrm{CP}j \Leftrightarrow d_{ij}(\succsim) \geq d_{ji}(\succsim) \end{equation}\]

where \(d_{ij}(\succsim)\) represents the cardinality of the set \(D_{ij}(\succsim)\), the set of all coalitions \(S \in 2^{N \setminus \{i,j\}}\) for which \(S \cup \{i\} \succsim S \cup \{j\}\).

cpMajorityComparisonScore(pr, e1, e2) calculates the two scores \(d_{ij}(\succsim)\) and \(-d_{ji}(\succsim)\). Notice the minus sign - that way we can use the sum of both values to determine the relation between e1 and e2.

pr <- as.PowerRelation("ab > (ac ~ bc) > (a ~ c) > {} > b")
cpMajorityComparisonScore(pr, "a", "b")
## [1]  2 -1
cpMajorityComparisonScore(pr, "b", "a")
## [1]  1 -2
if(sum(cpMajorityComparisonScore(pr, "a", "b")) >= 0) {
  print("a >= b")
} else {
  print("b > a")
}
## [1] "a >= b"

As a slight variation the logical parameter strictly calculates \(d^*_{ij}(\succsim)\) and \(-d^*_{ji}(\succsim)\), the number of coalitions \(S \in 2^{N\setminus \{i,j\}}\) where \(S\cup\{i\}\succ S\cup\{j\}\).

# Now (ac ~ bc) is not counted
cpMajorityComparisonScore(pr, "a", "b", strictly = TRUE)
## [1] 1 0
# Notice that the sum is still the same
sum(cpMajorityComparisonScore(pr, "a", "b", strictly = FALSE)) ==
  sum(cpMajorityComparisonScore(pr, "a", "b", strictly = TRUE))
## [1] TRUE

Coincidentally, cpMajorityComparisonScore with strictly = TRUE can be used to determine if e1 (strictly) dominates e2.

cpMajorityComparisonScore should be used for simple and quick calculations. The more comprehensive function cpMajorityComparison(pr, e1, e2) does the same calculations, but in the process retains more information about all the comparisons that might be interesting to a user, i.e., the set \(D_{ij}(\succsim)\) and \(D_{ji}(\succsim)\) as well as the relation \(iR^\succsim_\textrm{CP}j\). See the documentation for a full list of available data.

# extract more information in cpMajorityComparison
cpMajorityComparison(pr, "a", "b")
## a > b
## D_ab = {c, {}}
## D_ba = {c}
## Score of a = 2
## Score of b = 1
# with strictly set to TRUE, coalition c does
# neither appear in D_ab nor in D_ba
cpMajorityComparison(pr, "a", "b", strictly = TRUE)
## a > b
## D_ab = {{}}
## D_ba = {}
## Score of a = 1
## Score of b = 0

The CP-Majority relation can generate cycles, which is the reason that it is not offered as a social ranking solution. Instead, we will introduce the Copeland-like method and Kramer-Simpson-like method that make use of the CP-Majority functions to determine a power relation between elements. For further readings on CP-Majority, see [7] and [10].

3.3 Social Ranking Solutions

3.3.1 Ordinal Banzhaf

The Ordinal Banzhaf Score is a vector defined by the principle of marginal contributions. Intuitively speaking, if a player joining a coalition causes it to move up in the ranking, it can be interpreted as a positive contribution. On the contrary a negative contribution means that participating causes the coalition to go down in the ranking.

(Ordinal marginal contribution [5]