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–10].

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 newPowerRelation() or newPowerRelationFromString() functions.

library(socialranking)
newPowerRelation(c(1,2), ">", 1, "~", c(), ">", 2)
## Elements: 1 2
## 12 > (1 ~ {}) > 2
newPowerRelationFromString("ab > a ~ {} > b")
## Elements: a b
## ab > (a ~ {}) > b
newPowerRelationFromString("12 > 1 ~ {} > 2", asWhat = as.numeric)
## Elements: 1 2
## 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 SocialRankingSolution 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()
ordinalBanzhafScores() ordinalBanzhafRanking()

These functions may be called as follows.

pr <- newPowerRelationFromString("ab > ac ~ bc > a ~ c > {} > b")

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

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

rel <- relations::as.relation(pr)
rel
## A binary relation of size 7 x 7.
relations::relation_incidence(rel)
## Incidences:
##    ab ​ac ​​bc ​​​a ​​​​c ​​​​​{} ​​​​​​b
## ab  1  1  1 1 1  1 1
## ​ac  0  1  1 1 1  1 1
## ​​bc  0  1  1 1 1  1 1
## ​​​a   0  0  0 1 1  1 1
## ​​​​c   0  0  0 1 1  1 1
## ​​​​​{}  0  0  0 0 0  1 1
## ​​​​​​b   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\)
  • 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\) (i.e., 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 \(\succeq \in \mathcal{T}(\mathcal{P})\) is said a power relation.

In a given power relation \(\succeq \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 \succeq T\) and \(T \succeq S\)), whereas its asymmetric part is denoted by \(\succ\) (i.e., \(S \succ T\) if \(S \succeq T\) and not \(T \succeq 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 \succeq S_2 \succeq \ldots \succeq 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: \(\succeq = \{(\{1,2\},\{2\}), (\{2\}, \emptyset), (\emptyset, \{2\}), (\emptyset, \{1\})\}\). 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 \(\succeq\) is such that \(\{\{1,2\}\} \succ \{\{2\}, \emptyset\} \succ \{\{1\}\}\).

A social ranking solution (also called social ranking or, simply, solution) on \(N\), is a function \(R: \mathcal{T}(\mathcal{P}) \longrightarrow \mathcal{T}(N)\) associating to each power relation \(\succeq \in \mathcal{T}(\mathcal{P})\) a total preorder \(R(\succeq)\) (or \(R^\succeq\)) over the elements of \(N\). By this definition, the notion \(i R^\succeq j\) means that applying the social ranking solution to the power relation \(\succeq\) gives the result that \(i\) is ranked higher than or equal to \(j\).

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 <- newPowerRelation(c(1,2), ">", 2, "~", c(), ">", 1)
pr
## Elements: 1 2
## 12 > (2 ~ {}) > 1
class(pr)
## [1] "PowerRelation"      "SingleCharElements"

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

newPowerRelationFromString("12 > 2~{} > 1", asWhat = as.numeric)
## Elements: 1 2
## 12 > (2 ~ {}) > 1

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

prLong <- newPowerRelation(
  c("Alice", "Bob"), ">", "Bob", "~", c(), ">", "Alice"
)
prLong
## Elements: Alice Bob
## {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 the way 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
## Elements: 1 2
## {1, 2} > ({2} ~ {}) > {1}

Internally a PowerRelation is a list with four attributes (see table below). Notice that every coalition vector is turned into a set object from the sets package[12].

Attribute Description Value in pr
elements Sorted vector of elements c(1,2)
rankingCoalitions Coalitions in power relation list(set(1,2),set(2),set(),set(1))
equivalenceClasses List containing lists, each
containing coalitions in the
same equivalence class 		list(list(set(1,2)),
list(set(2), set()),
list(set(1)))

Since each coalition vector is turned into a set, coalitions such as c(1,2), c(2,1) and c(1,1,2,2) are equivalent.

prAtts <- newPowerRelation(c(2,2,1,1,2), ">", c(1,1,1), "~", c())
prAtts
## Elements: 1 2
## 12 > (1 ~ {})
prAtts$elements
## [1] 1 2
prAtts$rankingCoalitions
## [[1]]
## {1, 2}
## 
## [[2]]
## {1}
## 
## [[3]]
## {}
prAtts$rankingComparators
## [1] ">" "~"
prAtts$equivalenceClasses
## [[1]]
## [[1]][[1]]
## {1, 2}
## 
## 
## [[2]]
## [[2]][[1]]
## {1}
## 
## [[2]][[2]]
## {}

equivalenceClassIndex() determines at which index \(i\) a coalition \(S \in \sum_i\).

equivalenceClassIndex(prAtts, c(2,1))
## [1] 1
equivalenceClassIndex(prAtts, 1)
## [1] 2
equivalenceClassIndex(prAtts, c())
## [1] 2
# are the given coalitions in the same equivalence class?
coalitionsAreIndifferent(prAtts, 1, c())
## [1] TRUE
coalitionsAreIndifferent(prAtts, 1, c(1,2))
## [1] FALSE

2.2 Manipulating PowerRelation Objects

It is strongly discouraged to directly manipulate PowerRelation objects, since modifying one list or vector entry would require updates on all attributes. Instead newPowerRelation offers two parameters rankingCoalitions and rankingComparators, each corresponding to the same named attributes of a PowerRelation object.

pr
## Elements: 1 2
## {1, 2} > ({2} ~ {}) > {1}
# reverse power ranking
newPowerRelation(
  rankingCoalitions = rev(pr$rankingCoalitions),
  rankingComparators = pr$rankingComparators
)
## Elements: 1 2
## 1 > ({} ~ 2) > 12

Note that rankingComparators is optional. By default it assumes rankingCoalitions to be a linear order.

newPowerRelation(rankingCoalitions = rev(pr$rankingCoalitions))
## Elements: 1 2
## 1 > {} > 2 > 12

If the length of the rankingComparators vector is smaller or larger than the length of rankingCoalitions, the function silently fills in any gaps.

# if too short -> comparator values are repeated
newPowerRelation(
  rankingCoalitions = as.list(1:9),
  rankingComparators = "~"
)
## Elements: 1 2 3 4 5 6 7 8 9
## (1 ~ 2 ~ 3 ~ 4 ~ 5 ~ 6 ~ 7 ~ 8 ~ 9)
newPowerRelation(
    rankingCoalitions = as.list(letters[1:9]),
    rankingComparators = c(">", "~", "~")
)
## Elements: a b c d e f g h i
## a > (b ~ c ~ d) > (e ~ f ~ g) > (h ~ i)
# if too long -> ignore excessive comparators
newPowerRelation(
  rankingCoalitions = pr$rankingCoalitions,
  rankingComparators = c("~", ">", "~", ">", ">", "~")
)
## Elements: 1 2
## (12 ~ 2) > ({} ~ 1)

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 newPowerRelation, but also formats the function call in such a way that makes it easy to rearrange the ordering of the coalitions. RStudio offers shortcuts 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"),
  writeLines = TRUE,
  copyToClipboard = FALSE
)
## newPowerRelation(
##   c("a", "b", "c"),
##   ">", c("a", "b"),
##   ">", c("a", "c"),
##   ">", c("b", "c"),
##   ">", c("a"),
##   ">", c("b"),
##   ">", c("c"),
##   ">", c(),
## )