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 1.1.0 of the packagesocialranking
.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–11].
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()
.
## 12 > (1 ~ {}) > 2
## 12 > (1 ~ {}) > 2
## ab > (a ~ {}) > b
## 12 > 1 > {} > 2
## 12 > (1 ~ {}) > 2
Functions used to analyze a given PowerRelation
object
can be grouped into three main categories:
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
## [1] 1 3 4 4 4
## a > b > c
## a > b > c
## a > c > b
## a > b ~ c
## a > b ~ c
## 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()
.
## A binary relation of size 8 x 8.
## 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
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\), 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.
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.
## 12 > (2 ~ {}) > 1
## [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.
## 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.
## {Alice, Bob} > ({Bob} ~ {}) > {Alice}
## [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
.
## {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.
## Warning in createLookupTables(equivalenceClasses): Found 1 coalition that contain elements more than once.
##  1, 2 in the coalition {1, 1, 2, 2, 2}
## 11222 > (12 ~ {})
## [1] 1 2
## [1] 2
## [1] 2
## [1] 1
## [[1]]
## [1] 1 1
##
## [[2]]
## [1] 1 1
##
## [[3]]
## [1] 1 1
##
## [[4]]
## [1] 2 1
PowerRelation
objectsIt 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.
## (1 ~ {}) > 2 > 12
## 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)
## 12 > 1 > {} > 2
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.
## ({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} ~ {})
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
nonmonotonic power relation into a monotonic one by moving and
(optionally) adding all missing coalitions in \(2^N  \mathcal{P}\) to the corresponding
equivalence classes.
## (abc ~ ab ~ ac ~ a) > (bc ~ b) > c
## (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 ~ {})
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).
## as.PowerRelation("
## abc
## > ab
## > ac
## > bc
## > a
## > b
## > c
## > {}
## ")
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.
## [[1]]
## [1] 1 2
##
## [[2]]
## [1] 1
##
## [[3]]
## [1] 2
## 12 > 1 > 2
## (12 ~ 1 ~ 2)
## abcd > abc > abd > acd > bcd > ab > ac > ad > bc > bd > cd > a > b > c > d > {}
PowerRelation
objectsGiven a list of coalitions, it is possible to loop through all
possible permutations of power relations using
powerRelationGenerator()
. Calling gen()
in the
example below always produces a unique PowerRelation
object. 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:
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}(kj)^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^41\)) 15  1.382.958.545  230.283.190.977.959 
16  10.480.142.147  5.315.654.681.940.580 
3
SocialRanking
ObjectsThe 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 thedoRanking
function. In the following sections, we will introduce the notion of dominance[4], cumulative dominance[13] and CPMajority comparison[6] that lets us compare two elements before diving into the social ranking solutions of the Ordinal Banzhaf Index[5], Copelandlike and KramerSimpsonlike 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
forlexcelRanking
,L1Ranking
andL2Ranking
a > c > b
fordualLexcelRanking
,ordinalBanzhafRanking
andLPSRanking
a > b ~ c
forcopelandRanking
andkramerSimpsonRanking
a ~ c > b
forordinalBanzhafRanking
andLPRanking
3.1 Creating
SocialRanking
objectsA
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 theequivalenceClasses
attribute inPowerRelation
objects.The function
doRanking
offers a generic way of creatingSocialRanking
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 thenames()
attribute ofscores
. Hence, aPowerRelation
object is not necessary to create aSocialRanking
object.When working with types that cannot be sorted (i.e.,
lists
), a function can be passed to thecompare
parameter that allows comparisons between arbitrary elements. This function must take two parameters (i.e.,a
andb
) and return a numeric value based on the comparison:compare(a,b) > 0
:a
scores higher thanb
,compare(a,b) < 0
:a
scores lower thanb
,compare(a,b) == 0
:a
andb
are equivalent.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 CPMajority 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 valueTRUE
ife1
dominatese2
, elseFALSE
. Note thate1
not dominatinge2
does not indicate thate2
dominatese1
, nor does it imply thate1
is indifferent toe2
.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 toFALSE
such that \(\emptyset \cup \{i\} \succsim \emptyset \cup \{j\}\) is not considered in the CPMajority comparison.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
objectpr
and two elementse1
ande2
,cumulativeScores(pr)
returns the vectors described in definition 2 for each element,cumulativelyDominates(pr, e1, e2)
returnsTRUE
orFALSE
based on definition 3.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 CPMajority comparison
The Ceteris Paribus Majority (CPMajority) 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 CPMajority 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\}\).
(CPMajority [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 betweene1
ande2
.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\}\).Coincidentally,
cpMajorityComparisonScore
withstrictly = TRUE
can be used to determine ife1
(strictly) dominatese2
.cpMajorityComparisonScore
should be used for simple and quick calculations. The more comprehensive functioncpMajorityComparison(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.The CPMajority relation can generate cycles, which is the reason that it is not offered as a social ranking solution. Instead, we will introduce the Copelandlike method and KramerSimpsonlike method that make use of the CPMajority functions to determine a power relation between elements. For further readings on CPMajority, 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]) Let \(\succsim \in \mathcal{T}(\mathcal{P})\). For a given element \(i \in N\), its ordinal marginal contribution \(m_i^S(\succsim)\) with right to a coalition \(S \in \mathcal{P}\) is defined as:
\[\begin{equation} m_i^S(\succsim) = \begin{cases} \hphantom{}1 & \textrm{if } S \cup \{i\} \succ S\\ 1 & \textrm{if } S \succ S \cup \{i\}\\ \hphantom{}0 & \textrm{otherwise} \end{cases} \end{equation}\]
(Ordinal Banzhaf relation) Let \(\succsim \in \mathcal{T}(\mathcal{P})\). The Ordinal Banzhaf relation is the binary relation \(R^\succsim_\textrm{Banz} \subseteq N \times N\) such that for all \(i,j \in N\):
\[\begin{equation} iR^\succsim_\textrm{Banz}j \Leftrightarrow \text{Score}_\text{Banz}(i) \geq \text{Score}_\text{Banz}(j), \end{equation}\]
where \(\text{Score}_\text{Banz}(i) = \sum_{S} m^S_i(\succsim)\) for all \(S \in N\setminus\{i\}\).
Note that if \(S \notin \mathcal{P}\) or \(S \cup \{i\} \notin \mathcal{P}\), \(m_i^S(\succsim) = 0\).
The function
ordinalBanzhafScores()
returns three numbers for each element,The sum of the first two numbers determines the score of a player. Players with higher scores rank higher.