socialranking
: A package for
evaluating ordinal power relations in cooperative game theoryAbstract
This document gives a brief introduction to power relations and social ranking solutions aimed at ranking elements based on their contributions within coalitions. This document accompanies version 0.1.0 of the packagesocialranking
. ¶ Keywords: power
relation, social ranking solution, cooperative game theory, dominance,
cpmajority, Copeland, KramerSimpson, ordinal Banzhaf, dominance,
lexicographical excellence, relations.
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 multiattribute nature of the problem and it seems more realistic to represent collective decisionmaking 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 powerset (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].
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:
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.
< newPowerRelationFromString("ab > ac ~ bc > a ~ c > {} > b")
pr
# 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
< cumulativeScores(pr)
scores # show score of element a
$a scores
## [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()
.
< relations::as.relation(pr)
rel rel
## A binary relation of size 7 x 7.
::relation_incidence(rel) relations
## 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
PowerRelation
ObjectsWe 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:
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\).
PowerRelation
ObjectsA 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)
< newPowerRelation(c(1,2), ">", 2, "~", c(), ">", 1)
pr 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.
< newPowerRelation(
prLong 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.
< newPowerRelation(c(2,2,1,1,2), ">", c(1,1,1), "~", c())
prAtts prAtts
## Elements: 1 2
## 12 > (1 ~ {})
$elements prAtts
## [1] 1 2
$rankingCoalitions prAtts
## [[1]]
## {1, 2}
##
## [[2]]
## {1}
##
## [[3]]
## {}
$rankingComparators prAtts
## [1] ">" "~"
$equivalenceClasses prAtts
## [[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
PowerRelation
ObjectsIt 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)
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(),
## )