socialranking: A package for constructing ordinal power relations and evaluating social ranking solutions

Description

The package socialranking offers functions to represent ordinal information of coalitions and calculate the power relation between elements.

Details

Use browseVignettes("socialranking") for more information.

Author(s)

Maintainer: Felix Fritz felix.fritz@dauphine.eu

Authors:

• Jochen Staudacher jochen.staudacher@hs-kempten.de [copyright holder, thesis advisor]

• Moretti Stefano stefano.moretti@lamsade.dauphine.fr [copyright holder, thesis advisor]

See Also

Useful links:

• https://github.com/jassler/socialranking

• Report bugs at https://github.com/jassler/socialranking/issues

L1 Ranking

Description

Calculate the L^{(1)} scores.

Usage

L1Scores(powerRelation, elements = powerRelation$elements)

L1Ranking(powerRelation)

lexcel1Scores(powerRelation, elements = powerRelation$elements)

lexcel1Ranking(powerRelation)

Arguments

Details

Similar to lexcelRanking(), the number of times an element appears in each equivalence class is counted. In addition, we now also consider the size of the coalitions.

Let N be a set of elements, \succsim \in \mathcal{T}(\mathcal{P}) a power relation, and \Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_m its corresponding quotient order.

For an element i \in N, construct a matrix M^\succsim_i with m columns and |N| rows. Whereas each column q represents an equivalence class, each row p corresponds to the coalition size.

(M^\succsim_i)_{p,q} = |\lbrace S \in \Sigma_q: |S| = p \text{ and } i \in S\rbrace|

The L^{(1)} rewards elements that appear in higher ranking coalitions as well as in smaller coalitions. When comparing two matrices for a power relation, if M^\succsim_i >_{L^{(1)}} M^\succsim_j, this suggests that there exists a p^0 \in \{1, \dots, |N|\} and q^0 \in \{1, \dots, m\} such that the following holds:

1. (M^\succsim_i)_{p^0,q^0} > (M^\succsim_j)_{p^0,q^0}

2. (M^\succsim_i)_{p,q^0} = (M^\succsim_j)_{p,q^0} for all p < p^0

3. (M^\succsim_i)_{p,q} = (M^\succsim_j)_{p,q} for all q < q^0 and p \in \{1, \dots, |N|\}

Value

Score function returns a list of type L1Scores and length of powerRelation$elements (unless parameter elements is specified). Each index contains a vector of length powerRelation$eqs, the number of times the given element appears in each equivalence class.

Ranking function returns corresponding SocialRanking object.

Example

Let \succsim: (123 \sim 13 \sim 2) \succ (12 \sim 1 \sim 3) \succ (23 \sim \{\}). From this, we get the following three matrices:

M^\succsim_1 = \begin{bmatrix} 0 & 1 & 0\\ 1 & 1 & 0\\ 1 & 0 & 0 \end{bmatrix} M^\succsim_2 = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 0 \end{bmatrix} M^\succsim_3 = \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix}

From (M^\succsim_2)_{1,1} > (M^\succsim_1)_{1,1} and (M^\succsim_2)_{1,1} > (M^\succsim_3)_{1,1} it immediately follows that 2 is ranked above 1 and 3 according to L^{(1)}.

Comparing 1 against 3 we can set p^0 = 2 and q^0 = 2. Following the constraints from the definition above, we can verify that the entire column 1 is identical. In column 2, we determine that (M^\succsim_1)_{1,q^0} = (M^\succsim_3)_{1,q^0}, whereas (M^\succsim_1)_{p^0,q^0} > (M^\succsim_3)_{p^0,q^0}, indicating that 1 is ranked higher than 3, hence 2 \succ 1 \succ 3 according to L^{(1)}.

Aliases

For better discoverability, lexcel1Scores() and lexcel1Ranking() serve as aliases for L1Scores() and L1Ranking(), respectively.

References

Algaba E, Moretti S, Rémila E, Solal P (2021). “Lexicographic solutions for coalitional rankings.” Social Choice and Welfare, 57(4), 1–33.

See Also

Other ranking solution functions: L2Scores(), LPSScores(), LPScores(), copelandScores(), cumulativeScores(), kramerSimpsonScores(), lexcelScores(), ordinalBanzhafScores()

Examples

pr <- as.PowerRelation("(123 ~ 13 ~ 2) > (12 ~ 1 ~ 3) > (23 ~ {})")
scores <- L1Scores(pr)
scores$`1`
#      [,1] [,2] [,3]
# [1,]    0    1    0
# [2,]    1    1    0
# [3,]    1    0    0

L1Ranking(pr)
# 2 > 1 > 3

L2 Ranking

Description

Calculate the L^{(2)} scores.

Usage

L2Scores(powerRelation, elements = powerRelation$elements)

L2Ranking(powerRelation)

lexcel2Scores(powerRelation, elements = powerRelation$elements)

lexcel2Ranking(powerRelation)

Arguments

Details

Let N be a set of elements, \succsim \in \mathcal{T}(\mathcal{P}) a power relation, and \Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_m its corresponding quotient order.

For an element i \in N, construct a matrix M^\succsim_i with m columns and |N| rows. Whereas each column q represents an equivalence class, each row p corresponds to the coalition size.

(M^\succsim_i)_{p,q} = |\lbrace S \in \Sigma_q: |S| = p \text{ and } i \in S\rbrace|

Given two elements i, j \in N, L^{(2)} then ranks i strictly above j if there is some row p^0 \in \lbrace 1, \dots, |N| \rbrace and column q^0 \in \lbrace 1, \dots, m \rbrace such that

1. \sum_{p = 1}^{|N|} (M^\succsim_i)_{p,q} = \sum_{p = 1}^{|N|} (M^\succsim_j)_{p,q}\text{ for all } q < q^0,

2. \begin{cases} \text{(i)\hphantom{i} either } & \sum_{p=1}^{|N|} (M^\succsim_i)_{p,q^0} > \sum_{p=1}^{|N|} (M^\succsim_j)_{p,q^0}\\[5pt] \text{(ii) or } & (M^\succsim_i)_{p^0,q^0} > (M^\succsim_j)_{p^0,q^0} \text{ and } (M^\succsim_i)_{p,q^0} = (M^\succsim_j)_{p,q^0} \text{ for all } p < p^0 \end{cases}

Note that the conditions are very similar to L1Ranking(), with the difference that condition 3.(i) also ranks an element over another if they simply appear more often in an equivalence class, regardless of coalition size. This implies that a row p^0 for condition 3.(ii) to be satisfied may not have to exist.

Value

Score function returns a list of type L2Scores and length of powerRelation$elements (unless parameter elements is specified). Each index contains a matrix with length(powerRelation$eqs) columns and 1 + length(powerRelation$elements) rows.

Ranking function returns corresponding SocialRanking object.

Example

Let N = \lbrace 1, 2, 3, 4 \rbrace and \succsim: (123 \sim 12 \sim 13 \sim 14 \sim 2 \sim 4) \succ S, where S is every other coalition not present in the first equivalence class. From this, we get the following four matrices:

M^\succsim_1 = \begin{bmatrix} 0 & 1\\ 3 & 0\\ 1 & 2\\ 0 & 1 \end{bmatrix} M^\succsim_2 = \begin{bmatrix} 1 & 0\\ 1 & 2\\ 1 & 2\\ 0 & 1 \end{bmatrix} M^\succsim_3 = \begin{bmatrix} 0 & 1\\ 1 & 2\\ 1 & 2\\ 0 & 1 \end{bmatrix} M^\succsim_4 = \begin{bmatrix} 1 & 0\\ 1 & 2\\ 0 & 3\\ 0 & 1 \end{bmatrix}

For the sums in column 1, we get

\begin{aligned}\sum_{p=1}^{4} (M^\succsim_1)_{p,1} &= 4,\\\sum_{p=1}^{4} (M^\succsim_2)_{p,1} &= 3,\\\sum_{p=1}^{4} (M^\succsim_3)_{p,1} = \sum_{p=1}^{4} (M^\succsim_4)_{p,1} &= 2\end{aligned}.

This immediately puts 1 above all other elements and 2 above 3 and 4 according to the L^{(2)}. L^{(1)} would in this case prefer 2 over 1, simply because 2 appears once in a coalition of size 1 and 1 doesn't.

Since the column sum for 3 and 4 is the same, we can next evaluate if the individual row values are also the same. Here, since (M^\succsim_4)_{1,1} > (M^\succsim_3)_{1,1}, this gives an edge of element 4 over 3.

Note that, if the column was identical for 3 and 4, we would go to the next column and repeat the process. Elements are only then considered indifferent from each other, if the entire matrix is identical between the two.

Alterations

The matrices as described above and in Béal S, Rémila E, Solal P (2022). “Lexicographic solutions for coalitional rankings based on individual and collective performances.” Journal of Mathematical Economics, 102, 102738. can be investigated with the L1Scores() function.

For less complexity, another row is prepended to the matrix showing the sum of each column. Through this, a simple L^{(1)} comparison can be applied.

Aliases

For better discoverability, lexcel2Scores() and lexcel2Ranking() serve as aliases for L2Scores() and L2Ranking(), respectively.

References

Algaba E, Moretti S, Rémila E, Solal P (2021). “Lexicographic solutions for coalitional rankings.” Social Choice and Welfare, 57(4), 1–33.

See Also

Other ranking solution functions: L1Scores(), LPSScores(), LPScores(), copelandScores(), cumulativeScores(), kramerSimpsonScores(), lexcelScores(), ordinalBanzhafScores()

Examples

pr <- as.PowerRelation("123 ~ 12 ~ 13 ~ 14 ~ 2 ~ 4")
pr <- appendMissingCoalitions(pr)
scores <- L2Scores(pr)
scores$`1`
#      [,1] [,2]
# [1,]    0    1
# [2,]    3    0
# [3,]    1    2
# [3,]    0    1

L2Ranking(pr)
# 1 > 2 > 4 > 3

L1Ranking(pr)
# 2 > 4 > 1 > 3

LP* Ranking

Description

Calculate the L^{p^*} scores.

Usage

LPSScores(powerRelation, elements = powerRelation$elements)

LPSRanking(powerRelation)

lexcelPSScores(powerRelation, elements = powerRelation$elements)

lexcelPSRanking(powerRelation)

Arguments

Details

Let N be a set of elements, \succsim \in \mathcal{T}(\mathcal{P}) a power relation, and \Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_m its corresponding quotient order.

For an element i \in N, construct a matrix M^\succsim_i with m columns and |N| rows. Whereas each column q represents an equivalence class, each row p corresponds to the coalition size.

(M^\succsim_i)_{p,q} = |\lbrace S \in \Sigma_q: |S| = p \text{ and } i \in S\rbrace|

For i, j \in N, the social ranking solution L^{p^*} then ranks i strictly above j if one of the following conditions hold:

1. \lbrace i \rbrace \succ \lbrace j \rbrace;

2. \lbrace i \rbrace, \lbrace j \rbrace \in \Sigma_k and there exists a row p_0 \in \lbrace 2, \dots, |N|\rbrace and column q_0 \in \lbrace 1, \dots, k-1\rbrace such that:

   (M^\succsim_i)_{p,q} = (M^\succsim_j)_{p,q}\quad \forall p < p_0, q < k,

   (M^\succsim_i)_{p_0,q} = (M^\succsim_j)_{p_0,q}\quad \forall q < q_0,\text{ and}

   (M^\succsim_i)_{p_0,q_0} > (M^\succsim_j)_{p_0,q_0}.

Value

Score function returns a list of type LP*Scores and length of powerRelation$elements (unless parameter elements is specified). Each index contains a matrix with length(powerRelation$elements) rows and a variable number of columns, depending on the equivalence class index containing the singleton coalition of that element (matrix can have 0 columns).

Ranking function returns corresponding SocialRanking object.

Example

Let \succsim: (123 \sim 12 \sim 2) \succ (13 \sim 23) \succ (1 \sim 3 \sim \{\}). From this, we get the following three matrices:

M^\succsim_1 = \begin{bmatrix} 0 & 0 & 1\\ 1 & 1 & 0\\ 1 & 0 & 0 \end{bmatrix} M^\succsim_2 = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix} M^\succsim_3 = \begin{bmatrix} 0 & 0 & 1\\ 0 & 2 & 0\\ 1 & 0 & 0 \end{bmatrix}

(M^\succsim_2)_{2,3} in this context refers to the value in the second row and third column of element 2, in this case 1.

In the example, 2 will be immediately put above 1 and 3 because \lbrace 2 \rbrace \succ \lbrace 1 \rbrace and \lbrace 2 \rbrace \succ \lbrace 3 \rbrace. Since \lbrace 1 \rbrace \sim \lbrace 3 \rbrace, we next consider the coalitions of size 2. Here, it turns out that (M^\succsim_1)_{2,1} = 1 > 0 = (M^\succsim_3)_{2,1}, setting 3 to be the least preferred option (this is opposed to the L^p relation, which has no strict preference of 1 over 3).

As alluded to, L^{p^*} is similar to L^p, LPRanking(), in that it first considers the singleton coalitions, then sequentially every coalition of size 2 and above that ranks better than the corresponding singleton. It can be assumed, however, that L^{p^*} is more granular, as it doesn't throw away any information about which equivalence class these bigger coalitions belong to.

Alterations

The matrices as described above and in Béal S, Rémila E, Solal P (2022). “Lexicographic solutions for coalitional rankings based on individual and collective performances.” Journal of Mathematical Economics, 102, 102738. can be investigated with the L1Scores() function.

LPSScores() discards some redundant information, most notably all columns from each element's singleton class and the ones thereafter. The first row is also removed, as all values there are guaranteed to be 0.

For the example above, this would actually result in the matrices

matrix(c(1,1, 1,0), nrow=2)
matrix(numeric(), nrow=2)
matrix(c(0,1, 2,0), nrow=2)

Aliases

For better discoverability, lexcelPSScores() and lexcelPSRanking() serve as aliases for LPSScores() and LPSRanking(), respectively.

References

Béal S, Rémila E, Solal P (2022). “Lexicographic solutions for coalitional rankings based on individual and collective performances.” Journal of Mathematical Economics, 102, 102738.

See Also

Other ranking solution functions: L1Scores(), L2Scores(), LPScores(), copelandScores(), cumulativeScores(), kramerSimpsonScores(), lexcelScores(), ordinalBanzhafScores()

Examples

pr <- as.PowerRelation("(123 ~ 12 ~ 2) > (13 ~ 23) > (1 ~ 3 ~ {})")
scores <- LPSScores(pr)
scores$`1`
#      [,1] [,2]
# [1,]    1    1
# [2,]    1    0

scores$`2`
#
# [1,]
# [2,]

LPSRanking(pr)
# 2 > 1 > 3

LP Ranking

Description

Calculate the L^{p} scores.

Usage

LPScores(powerRelation, elements = powerRelation$elements)

LPRanking(powerRelation)

lexcelPScores(powerRelation, elements = powerRelation$elements)

lexcelPRanking(powerRelation)

Arguments

Details

Let N be a set of elements, \succsim \in \mathcal{T}(\mathcal{P}) a power relation, and \Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_m its corresponding quotient order.

For an element i \in N, construct a matrix M^\succsim_i with m columns and |N| rows. Whereas each column q represents an equivalence class, each row p corresponds to the coalition size.

(M^\succsim_i)_{p,q} = |\lbrace S \in \Sigma_q: |S| = p \text{ and } i \in S\rbrace|

For i, j \in N, the social ranking solution L^p then ranks i strictly above j if one of the following conditions hold:

1. \lbrace i \rbrace \succ \lbrace j \rbrace;

2. \lbrace i \rbrace, \lbrace j \rbrace \in \Sigma_k and there exists a row p_0 \in \lbrace 2, \dots, |N|\rbrace such that:

   \sum_{q < k} (M^\succsim_i)_{p,q} = \sum_{q < k} (M^\succsim_j)_{p,q}\quad \forall p < p_0,\text{ and}

   \sum_{q < k} (M^\succsim_i)_{p_0,q} > \sum_{q < k} (M^\succsim_j)_{p_0,q}.

In R, given two matrices M_i and M_j, this comparison could be expressed as

# function that returns TRUE if i should be ranked strictly above j
k_i <- which(M_i[1,] == 1)
k_j <- which(M_j[1,] == 1)
if(k_i != k_j) return(k_i < k_j)
if(k_i == 1)   return(FALSE)
# get sum for each row
# removing the first row implies that we start in row 2
sums_i <- apply(M_i[-1,seq(k_i-1)], 1, sum)
sums_j <- apply(M_j[-1,seq(k_j-1)], 1, sum)
# apply lexcel comparison
i <- which(a != b)
return(length(i) > 0 && a[i[1]] > b[i[1]])

Value

Score function returns a list of type LPScores and length of powerRelation$elements (unless parameter elements is specified). Each index contains a vector of length length(powerRelation$elements).

Ranking function returns corresponding SocialRanking object.

Example

Let \succsim: (123 \sim 12 \sim 2) \succ (13 \sim 23) \succ (1 \sim 3 \sim \{\}). From this, we get the following three matrices:

M^\succsim_1 = \begin{bmatrix} 0 & 0 & 1\\ 1 & 1 & 0\\ 1 & 0 & 0 \end{bmatrix} M^\succsim_2 = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix} M^\succsim_3 = \begin{bmatrix} 0 & 0 & 1\\ 0 & 2 & 0\\ 1 & 0 & 0 \end{bmatrix}

(M^\succsim_2)_{2,3} in this context refers to the value in the second row and third column of element 2, in this case 1.

In the example, 2 will be immediately put above 1 and 3 because \lbrace 2 \rbrace \succ \lbrace 1 \rbrace and \lbrace 2 \rbrace \succ \lbrace 3 \rbrace. Since \lbrace 1 \rbrace \sim \lbrace 3 \rbrace, we next consider the coalitions of size 2. Here, it turns out that (M^\succsim_1)_{2,1} + (M^\succsim_1)_{2,2} = 1 + 1 is equal to (M^\succsim_3)_{2,1} + (M^\succsim_3)_{2,2} = 0 + 2. For obvious reasons the grand coalition does not have to be considered, thus 1 and 3 are considered equally powerful by the L^p solution.

L^{p} is a social ranking solution belonging to the family of lexicographical ranking functions. While related to L1Ranking(), it incorporates the property of "standardness", stating that if the singleton coalition \lbrace i\rbrace \succ \lbrace j\rbrace, then the ranking solution should also prefer i over j.

If \lbrace i\rbrace \sim \lbrace j\rbrace, then all coalitions from size 2 and upward are inspected, giving higher precedence to coalitions with a lower number of elements. While this preference is similar to the L^{(1)}, it differs in two notable ways:

1. If \lbrace i\rbrace, \lbrace j\rbrace \in \Sigma_k, then only coalitions S \succsim (\lbrace i \rbrace \sim \lbrace j \rbrace) are considered,

2. From this subset of coalitions, consider the total number of coalitions i (or j) belongs to, given each coalition size. This may ignore information about the distribution of these coalitions within the different equivalence classes, which L^{(1)} and the slight variation L^{p^*} of the L^p solution take into account.

Alterations

The matrices as described above and in Béal S, Rémila E, Solal P (2022). “Lexicographic solutions for coalitional rankings based on individual and collective performances.” Journal of Mathematical Economics, 102, 102738. can be investigated with the L1Scores() function.

For efficiency, LPScores() discards much of the redundant information. Instead of a matrix for each element, it returns a vector of size |N|.

Given a score vector v for an element i, v[1] is the position of the singleton coalition {i}. This implies that if v[1] < w[1], where w is the score vector of an element j, then i is ranked strictly above j.

v[2], v[3], ..., v[n] then indicates the number of coalitions of size 2, 3, ..., n that the element i appears in.

Aliases

For better discoverability, lexcelPScores() and lexcelPRanking() serve as aliases for LPScores() and LPRanking(), respectively.

References

Béal S, Rémila E, Solal P (2022). “Lexicographic solutions for coalitional rankings based on individual and collective performances.” Journal of Mathematical Economics, 102, 102738.

See Also

Other ranking solution functions: L1Scores(), L2Scores(), LPSScores(), copelandScores(), cumulativeScores(), kramerSimpsonScores(), lexcelScores(), ordinalBanzhafScores()

Examples

pr <- as.PowerRelation("(123 ~ 13 ~ 2) > (12 ~ 1 ~ 3) > (23 ~ {})")
scores <- LPScores(pr)
scores$`2`
# [1] 1 0 0

LPRanking(pr)
# 2 > 1 ~ 3

# Since L^(1) also the relation {1,2}, which ranks above {2,3}, it will place 1 above 3
L1Ranking(pr)
# 2 > 1 > 3

PowerRelation object

Description

Create a PowerRelation object.

Usage

PowerRelation(
  equivalenceClasses,
  elements = NULL,
  coalitionLookup = NULL,
  elementLookup = NULL
)

is.PowerRelation(x, ...)

## S3 method for class 'PowerRelation'
print(x, ...)

Arguments

Details

A power relation describes the ordinal information between elements. Here specifically, we are interested in the power relation between coalitions, or groups of elements. Each coalition is assumed to be a vector containing zero (empty coalition), one (singleton) or more elements.

createPowerset() offers a convenient way of creating a power set over a set of elements that can be used to call PowerRelation() or as.PowerRelation().

Trying to figure out what equivalence class certain coalitions or elements belong to is quite common. For these sets of problems, the functions ⁠$coalitionLookup(v)⁠ and ⁠$elementLookup(e)⁠ should be utilized. We use some redundancy to speed up the lookup methods. As such, it is highly discouraged to edit a PowerRelation object directly, as the different power relation representations will fall out of sync. For more information, see the vignette: vignette(package = 'socialranking')

The PowerRelation() function expects a nested list of coalitions as input. For alternatives, see as.PowerRelation().

Value

PowerRelation object containing the following values:

• ⁠$elements⁠: vector of elements

• ⁠$eqs⁠: equivalence classes. Nested list of lists, each containing vectors representing groups of elements in the same equivalence class

• ⁠$coalitionLookup⁠: ⁠function(v)⁠ taking a coalition vector v and returning the equivalence class it belongs to. See coalitionLookup() for more.

• ⁠$elementLookup⁠: ⁠function(e)⁠ taking an element e and returning a list of 2-sized tuples. See elementLookup() for more.

Mathematical background

Let N = \lbrace 1, ..., n \rbrace be a finite set of elements (also called players). Any subset S \subseteq N is considered to be a group or coalition of elements, where \{\} is referred to as the empty coalition, \{i\} as a singleton (a coalition of size 1), and N as the grand coalition. The power set 2^N denotes the set of all subsets over N.

Let \mathcal{P} \subseteq 2^N be a collection of coalitions. A power relation on \mathcal{P} is a total preorder \succsim \subseteq \mathcal{P} \times \mathcal{P}. That is, for any two coalitions S, T \in \mathcal{P}, either (S,T) \in \succsim, or (T,S) \in \succsim, or both. In other words, we can compare any two groups of elements in \mathcal{P} and determine, if one group is better than, worse than, or equivalent to the other.

More commonly, the relation (S,T) \in \succsim is notated as S \succsim T.

\mathcal{T}(\mathcal{P}) denotes the family of all power relations on every collection \mathcal{P} \subseteq 2^N. Given a power relation \succsim \in \mathcal{T}(\mathcal{P}), \sim denotes its symmetric part whereas \succ its asymmetric part. Let S, T \in \mathcal{P}. Then,

S \sim T \textrm{ if } S \succsim T \textrm{ and } T \succsim S,\\ S \succ T \textrm{ if } S \succsim T \textrm{ and not } T \succsim S.

Coalitions which are deemed equivalent (S \sim T) can be collected into an equivalence class \Sigma_i. The list of equivalence classes forms a linear order, \Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_m.

Mathematical example

As an example, consider the elements N = \{\textrm{apple}, \textrm{banana}, \textrm{chocolate}\}. Each of them individually may go well with pancakes, but we are also interested in the combination of condiments. If we consider all possibilities, we will have to compare the sets

\mathcal{P} = 2^N = \{\{a,b,c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a\}, \{b\}, \{c\}, \{\}\}.

Looking for a way to rank this group of objects, one may arrive at the following total preorder \succsim \in \mathcal{T}(\mathcal{P}):

\{b,c\} \succ (\{a\} \sim \{c\}) \succ \{b\} \succ \{\} \succ (\{a,b,c\} \sim \{a,b\} \sim \{a, c\}).

In this particular case, we get five equivalence classes.

\Sigma_1 = \{\{b,c\}\}\\ \Sigma_2 = \{\{a\}, \{c\}\}\\ \Sigma_3 = \{\{b\}\}\\ \Sigma_4 = \{\{\}\}\\ \Sigma_5 = \{\{a,b,c\},\{a,b\},\{a,c\}\}

The power relation \succsim can be copy-pasted as a character string to the as.PowerRelation() function (it should accept the special characters \succsim and \sim).

as.PowerRelation("{b,c} > ({a} ~ {c}) > {b} > {} > ({a,b,c} ~ {a,b} ~ {a,c})")

References

Moretti S, Öztürk M (2017). “Some axiomatic and algorithmic perspectives on the social ranking problem.” In International Conference on Algorithmic Decision Theory, 166–181. Springer.

Bernardi G, Lucchetti R, Moretti S (2019). “Ranking objects from a preference relation over their subsets.” Social Choice and Welfare, 52(4), 589–606.

Algaba E, Moretti S, Rémila E, Solal P (2021). “Lexicographic solutions for coalitional rankings.” Social Choice and Welfare, 57(4), 1–33.

See Also

Other ways to create a PowerRelation() object using as.PowerRelation().

Examples

pr <- PowerRelation(list(
  list(c(1,2,3)),
  list(c(1, 2), 2, 3),
  list(c(2, 3), c()),
  list(c(1, 3)),
  list(1)
))

pr
# 123 > (12 ~ 2 ~ 3) > (23 ~ {}) > 13 > 1

stopifnot(pr$elements == 1:3)
stopifnot(pr$coalitionLookup(1) == 5)
stopifnot(pr$coalitionLookup(c()) == 3)
stopifnot(pr$coalitionLookup(c(1,2)) == 2)

# find coalitions an element appears in
for(t in pr$elementLookup(2)) {
  stopifnot(2 %in% pr$eqs[[t[1]]][[t[2]]])
}

# use createPowerset to help generate a valid function call
if(interactive())
  createPowerset(letters[1:3], result = "copy")

# pasted, rearranged using alt+up / alt+down in RStudio

# note that the function call looks different if elements are multiple characters long
if(interactive())
  createPowerset(c("apple", "banana", "chocolate"), result = "copy")

# pasted clipboard
PowerRelation(rlang::list2(
  list(c("banana", "chocolate")),
  list(c("apple"),
       c("chocolate")),
  list(c("banana")),
  list(c()),
  list(c("apple", "banana", "chocolate"),
       c("apple", "banana"),
       c("apple", "chocolate")),
))
# {banana, chocolate} > ({apple} ~ {chocolate}) > {banana} > {} > ...

SocialRanking object

Description

Create a SocialRanking object.

Usage

SocialRanking(l)

Arguments

Details

Similar to PowerRelation(), SocialRanking expects expects a list to represent a power relation. Unlike PowerRelation() however, this list should not be nested and should only contain vectors, each vector containing elements that are deemed equally preferable.

Use doRanking() to rank elements based on arbitrary score objects.

A social ranking solution, or ranking solution, or solution, maps each power relation between coalitions to a power relation between its elements. I.e., from the power relation \succsim: \{1,2\} \succ \{2\} \succ \{1\}, we may expect the result of a ranking solution R^\succsim to rank element 2 over 1. Therefore 2 R^\succsim 1 will be present, but not 1 R^\succsim 2.

Formally, a ranking solution R: \mathcal{T}(\mathcal{P}) \rightarrow \mathcal{T}(N) is a function that, given a power relation \succsim \in \mathcal{T}(\mathcal{P}), always produces a power relation R(\succsim) (or R^\succsim) over its set of elements. For two elements i, j \in N, i R^\succsim j means that applying the solution R on the ranking \succsim makes i at least as preferable as j. Often times iI^\succsim j and iP^\succsim j are used to indicate its symmetric and asymmetric part, respectively. As in, iI^\succsim j implies that iR^\succsim j and jR^\succsim i, whereas iP^\succsim j implies that iR^\succsim j but not jR^\succsim i.

Value

A list of type SocialRanking. Each element of the list contains a vector of elements in powerRelation$elements that are indifferent to one another.

See Also

Function that ranks elements based on their scores, doRanking()

Examples

SocialRanking(list(c("a", "b"), "f", c("c", "d")))
# a ~ b > f > c ~ d

Append missing coalitions

Description

Append an equivalence class to a power relation with all coalitions of elements that do not appear in the power relation.

Usage

appendMissingCoalitions(powerRelation, includeEmptySet = TRUE)

Arguments

Details

For a given set of elements N = \lbrace 1, ..., n \rbrace, a PowerRelation object describes a total preorder of its subsets, or coalitions, \mathcal{P} \subseteq 2^N, where 2^N is the superset of elements.

If \mathcal{P} \neq 2^N, that means that there are some coalitions S \in 2^N, S \notin \mathcal{P}, such that we cannot compare S \succsim T or T \succsim S for every T \in \mathcal{P}.

This may be caused by 2^N having too many coalitions to consider. In certain cases, it may be more interesting to only consider the top ranking coalitions and "shoving" all remaining coalitions into the back.

For this use-case, appendMissingCoalitions() takes the set 2^N \setminus \mathcal{P} and attaches it in form of an equivalence class to the back of the power relation.

I.e., take as an example 12 \succ 13 \succ (1 \sim 2). Here, we have

\begin{aligned} 2^N &= \lbrace 123, 12, 13, 23, 1, 2, 3, \emptyset \rbrace\\ \mathcal{P} &= \lbrace 12, 13, 1, 2 \rbrace\\ 2^N \setminus \mathcal{P} &= \lbrace 123, 23, 3, \emptyset \rbrace . \end{aligned}

Adding the missing coalitions to the power relation then gives us 12 \succ 13 \succ (1 \sim 2) \succ (123 \sim 23 \sim 3 \sim \emptyset).

Value

PowerRelation object containing the following values:

• ⁠$elements⁠: vector of elements

• ⁠$eqs⁠: equivalence classes. Nested list of lists, each containing vectors representing groups of elements in the same equivalence class

• ⁠$coalitionLookup⁠: ⁠function(v)⁠ taking a coalition vector v and returning the equivalence class it belongs to. See coalitionLookup() for more.

• ⁠$elementLookup⁠: ⁠function(e)⁠ taking an element e and returning a list of 2-sized tuples. See elementLookup() for more.

See Also

Other helper functions for transforming power relations: makePowerRelationMonotonic()

Examples

pr <- as.PowerRelation(list(c(1,2), 3))
# 12 > 3

appendMissingCoalitions(pr)
# 12 > 3 > (123 ~ 13 ~ 23 ~ 1 ~ 2 ~ {})

appendMissingCoalitions(pr, includeEmptySet = FALSE)
# 12 > 3 > (123 ~ 13 ~ 23 ~ 1 ~ 2)

Create PowerRelation object

Description

Alternative ways of creating PowerRelation objects.

Usage

as.PowerRelation(x, ...)

## S3 method for class 'character'
as.PowerRelation(x, ...)

## S3 method for class 'list'
as.PowerRelation(x, ..., comparators = c(">"))

Arguments

Using a character string

The same way a power relation \succsim may be represented in literature (or printed by an PowerRelation object), a simple string containing letters, numbers, > or ~ can be used to input a new power relation.

Every special character is ignored, with the exception of \succsim ("\u227B") and \sim ("\u223C").

Every letter or number is assumed to be an individual element. "abc > ac" therefore would represent two coalitions, the first one of size 3 with the elements a, b, and c. This method does not allow for elements to be entered that are supposed to be multiple characters long.

An empty coalitions can be simply left blank (i.e., "abc > ~ ac"), though it is often clearer if curly braces are used to indicate such (i.e., "abc > {} ~ ac").

Using a list

Create a PowerRelation object with an unnested list of coalition vectors.

By default, a linear order is assumed on the coalitions. I.e., if it is given list(c(1,2),1,2), these three coalitions are put into their own equivalence class, producing ⁠12 > 1 > 2⁠.

The comparators in-between can be adjusted to indicate whether the relation between two coalitions is that of strict preference > or indifference ~.

Examples

# Using character strings
as.PowerRelation("abc > ab > ({} ~ c) > (a ~ b ~ ac) > bc")
# abc > ab > ({} ~ c) > (a ~ b ~ ac) > bc

# using createPowerset(), then shifting coalitions up and down using Alt+Up and Alt+Down
if(interactive()) {
  createPowerset(1:2, result = "copy")
}
as.PowerRelation("
  12
  > 1
  ~ {}
  > 2
")

# Using lists
as.PowerRelation(list(c(1,2), 2, c(), 1))
# 12 > 2 > {} > 1

as.PowerRelation(list(c(1,2), 2, c(), 1), comparators = c("~", ">", ">"))
# (12 ~ 2) > {} > 1

# the length of comparators doesn't necessarily matter.
# If comparators are missing, the existing ones are simply repeated...
as.PowerRelation(list(c(1,2), 2, c(), 1), comparators = "~")
# (12 ~ 2 ~ {} ~ 1)

as.PowerRelation(list(c(1,2), 2, c(), 1), comparators = c("~", ">"))
# (12 ~ 2) > ({} ~ 1)

# ... or the rest is cut off
as.PowerRelation(list(c(1,2), 2, c(), 1), comparators = c("~", ">", "~", "~", ">"))
# (12 ~ 2) > ({} ~ 1)

Are coalitions indifferent

Description

Check if coalitions are indifferent to one another, or, in other words, if they appear in the same equivalence class.

Usage

coalitionsAreIndifferent(powerRelation, c1, c2)

Arguments

Value

Logical value TRUE if c1 and c2 are in the same equivalence class, else FALSE.

See Also

Other lookup functions: elementLookup(), equivalenceClassIndex()

Examples

pr <- PowerRelation(list(list(c(1,2)), list(1, 2)))

stopifnot(coalitionsAreIndifferent(pr, c(1,2), c(1)) == FALSE)
stopifnot(coalitionsAreIndifferent(pr, 2, 1) == TRUE)

# Note that it doesn't fail with non-existing power relations
stopifnot(coalitionsAreIndifferent(pr, 1, c()) == FALSE)
stopifnot(coalitionsAreIndifferent(pr, 3, c(1,2,3)) == TRUE)

Copeland-like method

Description

Based on cpMajorityComparison(), add or subtract scores based on how an element fares against the others.

copelandRanking() returns the corresponding ranking.

Usage

copelandScores(powerRelation, elements = powerRelation$elements)

copelandRanking(powerRelation)

Arguments

Details

Strongly inspired by the Copeland score of social choice theory (Copeland 1951), the Copeland-like solution is based on the net flow of the CP-majority graph (Allouche et al. 2020).

Individuals are ordered according to the number of pairwise winning comparisons, minus the number of pairwise losing comparisons, over the set of all CP-comparisons.

More formally, in a given ⁠PowerRelation pr⁠ with element i, count the number of elements j \in N \setminus \lbrace i \rbrace where cpMajorityComparison⁠(pr, i, j) >= 0⁠ and subtract those where cpMajorityComparison⁠(pr, i, j) <= 0⁠.

Value

Score function returns a list of type CopelandScores and length of powerRelation$elements (unless parameter elements is specified). Each element is a vector of 2 numbers, the number of pairwise winning comparisons and the number of pairwise losing comparisons. Those two numbers summed together gives us the actual ordinal Copeland score.

Ranking function returns corresponding SocialRanking object.

References

Allouche T, Escoffier B, Moretti S, Öztürk M (2020). “Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions.” In Bessiere C (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, 17–23. doi:10.24963/ijcai.2020/3, Main track.

Copeland AH (1951). “A reasonable social welfare function.” mimeo, 1951. University of Michigan.

See Also

Other CP-majority based functions: cpMajorityComparison(), kramerSimpsonScores()

Other ranking solution functions: L1Scores(), L2Scores(), LPSScores(), LPScores(), cumulativeScores(), kramerSimpsonScores(), lexcelScores(), ordinalBanzhafScores()

Examples

# (123 ~ 12 ~ 3 ~ 1) > (2 ~ 23) > 13
pr <- PowerRelation(list(
  list(c(1,2,3), c(1,2), 3, 1),
  list(c(2,3), 2),
  list(c(1,3))
))

copelandScores(pr)
# `1` = c(2, -1)
# `2` = c(2, -2)
# `3` = c(1, -2)

# only calculate results for two elements
copelandScores(pr, c(1,3))
# `1` = c(2, -1)
# `3` = c(1, -2)

# or just one element
copelandScores(pr, 2)
# `2` = c(2, -2)

# 1 > 2 > 3
copelandRanking(pr)

CP-Majority relation

Description

The Ceteris Paribus-majority relation compares the relative success between two players joining a coalition.

cpMajorityComparisonScore() only returns two numbers, a positive number of coalitions where e1 beats e2, and a negative number of coalitions where e1 is beaten by e2.

Usage

cpMajorityComparison(
  powerRelation,
  e1,
  e2,
  strictly = FALSE,
  includeEmptySet = TRUE
)

cpMajorityComparisonScore(
  powerRelation,
  e1,
  e2,
  strictly = FALSE,
  includeEmptySet = TRUE
)

Arguments

Details

Given two elements i and j, go through each coalition S \in 2^{N \setminus \lbrace i, j \rbrace}. D_{ij}(\succsim) then contains all coalitions S where S \cup \lbrace i \rbrace \succsim S \cup \lbrace j \rbrace and D_{ji}(\succsim) contains all coalitions where S \cup \lbrace j \rbrace \succsim S \cup \lbrace i \rbrace.

The cardinalities d_{ij}(\succsim) = |D_{ij}| and d_{ji}(\succsim) = |D_{ji}| represent the score of the two elements, where i \succ j if d_{ij}(\succsim) > d_{ji}(\succsim) and i \sim j if d_{ij}(\succsim) == d_{ji}(\succsim).

cpMajorityComparison() tries to retain all that information. The list returned contains the following information. Note that in this context the two elements i and j refer to element 1 and element 2 respectively.

• ⁠$e1⁠: list of information about element 1

  • ⁠$e1$name⁠: name of element 1

  • ⁠$e1$score⁠: score d_{ij}(\succsim). d_{ij}(\succ) if strictly == TRUE

  • ⁠$e1$winningCoalitions⁠: list of coalition vectors S \in D_{ij}(\succsim). S \in D_{ij}(\succ) if strictly == TRUE

• ⁠$e2⁠: list of information about element 2

  • ⁠$e2$name⁠: name of element 2

  • ⁠$e1$score⁠: score d_{ji}(\succsim). d_{ji}(\succ) if strictly == TRUE

  • ⁠$e1$winningCoalitions⁠: list of coalition vectors S \in D_{ji}(\succsim). S \in D_{ji}(\succ) if strictly == TRUE

• ⁠$winner⁠: name of higher scoring element. NULL if they are indifferent.

• ⁠$loser⁠: name of lower scoring element. NULL if they are indifferent.

• ⁠$tuples⁠: a list of coalitions S \in 2^{N \setminus \lbrace i, j \rbrace } with:

  • ⁠$tuples[[x]]$coalition⁠: vector, the coalition S

  • ⁠$tuples[[x]]$included⁠: logical, TRUE if S \cup \lbrace i \rbrace and S \cup \lbrace j \rbrace are in the power relation

  • ⁠$tuples[[x]]$winner⁠: name of the winning element i where S \cup \lbrace i \rbrace \succ S \cup \lbrace j \rbrace. It is NULL if S \cup \lbrace i \rbrace \sim S \cup \lbrace j \rbrace

  • ⁠$tuples[[x]]$e1⁠: index x_1 at which S \cup \lbrace i \rbrace \in \sum_{x_1}

  • ⁠$tuples[[x]]$e2⁠: index x_2 at which S \cup \lbrace j \rbrace \in \sum_{x_2}

The much more efficient cpMajorityComparisonScore() only calculates ⁠$e1$score⁠.

Unlike Lexcel, Ordinal Banzhaf, etc., this power relation can introduce cycles. For this reason the function cpMajorityComparison() and cpMajorityComparisonScore() only offers direct comparisons between two elements and not a ranking of all players. See the other CP-majority based functions that offer a way to rank all players.

Value

cpMajorityComparison() returns a list with elements described in the details.

cpMajorityComparisonScore() returns a vector of two numbers, a positive number of coalitions where e1 beats e2 (d_{ij}(\succsim)), and a negative number of coalitions where e1 is beaten by e2 (-d_{ji}(\succsim)).

References

Haret A, Khani H, Moretti S, Öztürk M (2018). “Ceteris paribus majority for social ranking.” In 27th International Joint Conference on Artificial Intelligence (IJCAI-ECAI-18), 303–309.

Fayard N, Escoffier MÖ (2018). “Ordinal Social ranking: simulation for CP-majority rule.” In DA2PL'2018 (From Multiple Criteria Decision Aid to Preference Learning).

See Also

Other CP-majority based functions: copelandScores(), kramerSimpsonScores()

Examples

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

scores <- cpMajorityComparison(pr, "a", "b")
scores
# a > b
# D_ab = {c, {}}
# D_ba = {{}}
# Score of a = 2
# Score of b = 1

stopifnot(scores$e1$name == "a")
stopifnot(scores$e2$name == "b")
stopifnot(scores$e1$score == 2)
stopifnot(scores$e2$score == 1)
stopifnot(scores$e1$score == length(scores$e1$winningCoalitions))
stopifnot(scores$e2$score == length(scores$e2$winningCoalitions))

# get tuples with coalitions S in 2^(N - {i,j})
emptySetTuple <- Filter(function(x) identical(x$coalition, c()), scores$tuples)[[1]]
playerCTuple  <- Filter(function(x) identical(x$coalition, "c"), scores$tuples)[[1]]

# because {}u{a} ~ {}u{b}, there is no winner
stopifnot(is.null(emptySetTuple$winner))
stopifnot(emptySetTuple$e1 == emptySetTuple$e2)

# because {c}u{a} > {c}u{b}, player "a" gets the score
stopifnot(playerCTuple$winner == "a")
stopifnot(playerCTuple$e1 < playerCTuple$e2)
stopifnot(playerCTuple$e1 == 1L)
stopifnot(playerCTuple$e2 == 3L)

cpMajorityComparisonScore(pr, "a", "b") # c(1,0)
cpMajorityComparisonScore(pr, "b", "a") # c(0,-1)

Create powerset

Description

Given a vector of elements generate a power set.

Usage

createPowerset(
  elements,
  includeEmptySet = TRUE,
  result = c("return", "print", "copy", "printCompact", "copyCompact")
)

Arguments

Value

List of power set vectors. If the parameter result is set to "print" or "copy", nothing is returned. Instead, a character string is generated that can be used in R to call and create a new PowerRelation object. This string is either printed or copied to clipboard (see argument result).

Examples

# normal return type is a list of vectors
createPowerset(c("Alice", "Bob"), includeEmptySet = FALSE)
## [[1]]
## [1] "Alice" "Bob"
##
## [[2]]
## [1] "Alice"
##
## [[3]]
## [1] "Bob"

# instead of creating a list, print the power set such that it can be copy-pasted
# and used to create a new PowerRelation object
createPowerset(letters[1:4], result = "print")
# prints
# as.PowerRelation("
#   abcd
#   > abc
#   > abd
#   > acd
#   > bcd
#   > ab
#   ...
#   > {}
# ")

createPowerset(letters[1:3], includeEmptySet = FALSE, result = "printCompact")
# as.PowerRelation("abc > ab > ac > bc > a > b > c")

# create the same string as before, but now copy it to the clipboard instead
if(interactive()) {
  createPowerset(1:3, result = "copyCompact")
}

# Note that as.PowerRelation(character) only assumes single-char elements.
# As such, the generated function call string with multi-character names
# looks a little different.
createPowerset(c("Alice", "Bob"), result = "print")
# PowerRelation(rlang::list2(
#   list(c("Alice", "Bob")),
#   list(c("Alice")),
#   list(c("Bob")),
#   list(c()),
# ))

Cumulative scores

Description

Calculate cumulative score vectors for each element.

Usage

cumulativeScores(powerRelation, elements = powerRelation$elements)

cumulativelyDominates(powerRelation, e1, e2, strictly = FALSE)

Arguments

Details

An element's cumulative score vector is calculated by cumulatively adding up the amount of times it appears in each equivalence class in the powerRelation. I.e., in a linear power relation with eight coalitions, if element 1 appears in coalitions placed at 1, 3, and 6, its score vector is [1, 1, 2, 2, 2, 3, 3, 3].

Value

Score function returns a list of type CumulativeScores and length of powerRelation$elements (unless parameter elements is specified). Each index contains a vector of length powerRelation$eqs, cumulatively counting up the number of times the given element appears in each equivalence class.

cumulativelyDominates() returns TRUE if e1 cumulatively dominates e2, else FALSE.

Dominance

i dominates j if, for each index x, \textrm{Score}(i)_x \geq \textrm{Score}(j)_x.

i strictly dominates j if there exists an x such that \textrm{Score}(i)_x > \textrm{Score}(j)_x.

References

Moretti S (2015). “An axiomatic approach to social ranking under coalitional power relations.” Homo Oeconomicus, 32(2), 183–208.

Moretti S, Öztürk M (2017). “Some axiomatic and algorithmic perspectives on the social ranking problem.” In International Conference on Algorithmic Decision Theory, 166–181. Springer.

See Also

Other ranking solution functions: L1Scores(), L2Scores(), LPSScores(), LPScores(), copelandScores(), kramerSimpsonScores(), lexcelScores(), ordinalBanzhafScores()

Examples

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

# `1`: c(1, 2, 2)
# `2`: c(1, 1, 2)
cumulativeScores(pr)

# calculate for selected number of elements
cumulativeScores(pr, c(2))

# TRUE
d1 <- cumulativelyDominates(pr, 1, 2)

# TRUE
d2 <- cumulativelyDominates(pr, 1, 1)

# FALSE
d3 <- cumulativelyDominates(pr, 1, 1, strictly = TRUE)

stopifnot(all(d1, d2, !d3))

Create a SocialRanking object

Description

Rank elements based on their scores.

Usage

doRanking(scores, compare = NULL, decreasing = TRUE)

Arguments

Details

All ranking solutions in the package are tied to the scores or score vectors of the elements. For these kinds of solutions, doRanking() offers a simple way that turns a (named) vector or list of scores for each element into a SocialRanking object. For example, doRanking(c(a=1,b=2)) produces b > a (b P^\succsim a), because b with a score of 2 should be placed higher than a with a score of 1.

Ranking solutions in the package include lexcelRanking(), ordinalBanzhafRanking() and L1Ranking(), among others. These functions take a power relation, calculate the scores of each element and returns a SocialRanking object.

R natively supports sorting for vectors, but not for lists. If the use of lists is necessary, or if the native sort method in vectors does not produce the desired results, there are two possible ways to solve this:

1. by the introduction of custom S3 classes, or

2. by setting the compare parameter in doRanking().

For S3 classes, the class for the score object has to be set and the == and > (and [ for lists) operators overloaded. I.e., lexcelScores() returns a list with the custom class LexcelScores that implements ⁠==.LexcelScores⁠, ⁠>.LexcelScores⁠, ⁠[.LexcelScores⁠ and is.na.LexcelScores.

In cases where we only want to experiment, introducing new S3 classes can be cumbersome. As an alternative, the compare parameter can be assigned a function. This function must take two parameters, i.e., ⁠function(a, b)⁠, where a and b are the scores of two arbitrary elements. The function then must return one of the following:

• ⁠> 0⁠ (positive value) if score a is ranked higher than score b,

• ⁠< 0⁠ (negative value) if score a is ranked lower than score b, or

• ⁠= 0⁠ if both scores a and b are considered equal.

In doRanking(c(a=3,b=2,c=2), compare = function(a,b) a - b), the compare function returns a positive value of the first parameter is larger than the second. a has the highest value and will there for be ranked highest, a > b ~ c.

Conversely, doRanking(c(a=3,b=2,c=2), compare = function(a,b) b - a) favors elements with lower scores, resulting in the element ranking b ~ c > a.

Value

A list of type SocialRanking. Each element of the list contains a vector of elements in powerRelation$elements that are indifferent to one another.

See Also

SocialRanking()

Examples

doRanking(c(a=1,b=2))
# b > a

doRanking(c(a=2,b=2))
# a ~ b

# a custom ranking function. Here, we implement the following ranking solution:
# disregard any big coalitions and only rank elements based on their individual performances
# iRj if and only if {i} >= {j}
singletonRanking <- function(pr) {
  scores <- sapply(pr$elements, equivalenceClassIndex, powerRelation = pr)
  # note that coalitions in higher indexed equivalence classes are less preferable
  # hence, scores should be sorted in an increasing order
  doRanking(scores, decreasing = FALSE)
}

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

# a reverse lexcel ranking, where vectors are compared right to left
# here, we introduce a compare function. It returns:
# * 0, if a and b are identical
# * a positive value, if a[i] > b[i] and every value after that is equal
# * a negative value, if a[i] < b[i] and every value after that is equal
reverseLexcelCompare <- function(a, b) {
  i <- which(a != b) |> rev()
  if(length(i) == 0) 0
  else a[i[1]] - b[i[1]]
}

scores <- unclass(cumulativeScores(pr))

# R cannot natively sort a class. Instead:
# Method 1 - utilize the compare parameter
doRanking(scores, compare = reverseLexcelCompare)


# Method 2 - introduce S3 class
`[.RevLex` <- function(x, i, ...) structure(unclass(x)[i], class = "RevLex")
`==.RevLex` <- function(a, b) reverseLexcelCompare(a[[1]],b[[1]]) == 0
`>.RevLex` <- function(a, b) reverseLexcelCompare(a[[1]],b[[1]]) > 0
is.na.RevLex <- function(x) FALSE
doRanking(structure(scores, class = "RevLex"))

stopifnot(
  doRanking(scores, compare = reverseLexcelCompare) ==
  doRanking(structure(scores, class = "RevLex"))
)

Dominance

Description

Check if one element dominates the other.

Usage

dominates(powerRelation, e1, e2, strictly = FALSE, includeEmptySet = TRUE)

Arguments

Details

i is said to dominate j if S \cup \lbrace i \rbrace \succsim S \cup \lbrace j \rbrace for all S \in 2^{N \setminus \lbrace i,j \rbrace}.

i strictly dominates j if there also exists an S \in 2^{N \setminus \lbrace i,j \rbrace} such that S \cup \lbrace i \rbrace \succ S \cup \lbrace j \rbrace.

Value

Logical value TRUE if e1 dominates e2, else FALSE.

Examples

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

# TRUE
d1 <- dominates(pr, 1, 2)

# FALSE
d2 <- dominates(pr, 2, 1)

# TRUE (because it's not strict dominance)
d3 <- dominates(pr, 1, 1)

# FALSE
d4 <- dominates(pr, 1, 1, strictly = TRUE)

stopifnot(all(d1, !d2, d3, !d4))

Element lookup

Description

List coalitions that an element appears in.

Usage

elementLookup(powerRelation, element)

Arguments

Details

This function calls powerRelation$elementLookup(element). The returned list contains tuples containing the index to find the corresponding coalitions in powerRelation$eqs.

If elementLookup(powerRelation, 2) returns list(c(1,1), c(1,2), c(3,1)), we can determine that the element 2 appears twice in equivalence class 1 and once in equivalence class 3. The specific coalition then can be accessed with powerRelation$eqs[[i]][[j]], where i is the equivalence class index and j is the coalition in that equivalence class containing the element.

Value

List of tuples, each of size 2. First value of a tuple indicates the equivalence class index, the second value the index inside that equivalence class with the coalition containing the element. Returns NULL if the element does not exist.

See Also

Other lookup functions: coalitionsAreIndifferent(), equivalenceClassIndex()

Examples

pr <- as.PowerRelation("12 > 2 ~ 1")

l <- elementLookup(pr, 1)
l
# (1,1), (2,2)

sapply(l, function(tuple) 1 %in% pr$eqs[[tuple[1]]][[tuple[2]]]) |> all() |> stopifnot()

# if element does not exist, it returns NULL
elementLookup(pr, 3) |> is.null() |> stopifnot()

Get index of equivalence class containing a coalition

Description

Given a coalition vector, return the equivalence class index it appears in.

Usage

equivalenceClassIndex(powerRelation, coalition)

coalitionLookup(powerRelation, coalition)

Arguments

Details

This function calls powerRelation$coalitionLookup(coalition).

equivalenceClassIndex() serves as an alias to coalitionLookup().

Value

Numeric value, equivalence class index containing coalition. NULL if the coalition does not exist. If the powerRelation contains cycles, it is possible that multiple values are returned.

See Also

Other lookup functions: coalitionsAreIndifferent(), elementLookup()

Examples

pr <- as.PowerRelation("12 > 2 ~ 1")

(e1 <- equivalenceClassIndex(pr, c(1, 2)))
# 1

(e2 <- equivalenceClassIndex(pr, c(1)))
# 2

(e3 <- equivalenceClassIndex(pr, c(2)))
# 2

(e4 <- equivalenceClassIndex(pr, c()))
# NULL <- empty set does not exist

stopifnot(all(c(e1,e2,e3,e4) == c(1,2,2)))

Kramer-Simpson-like method

Description

Calculate the Kramer-Simpson-like scores. Higher scores are better.

kramerSimpsonRanking() returns the corresponding ranking.

Usage

kramerSimpsonScores(powerRelation, elements = powerRelation$elements)

kramerSimpsonRanking(powerRelation)

Arguments

Details

Inspired by the Kramer-Simpson method of social choice theory (Simpson 1969) (Kramer 1975), the Kramer-Simpson-like method compares each element against all other elements using the CP-Majority rule.

For a given element i, calculate the cpMajorityComparisonScore() against all elements j, d_{ji}(\succsim) (notice that i and j are in reverse order). -\max_{j \in N \setminus \lbrace i \rbrace}(d_{ji}(\succsim)) then determines the final score, where higher scoring elements are ranked higher (notice the negative symbol in front of the \max statement).

The implementation slightly differs from the original definition in Allouche T, Escoffier B, Moretti S, Öztürk M (2020). “Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions.” In Bessiere C (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, 17–23. doi:10.24963/ijcai.2020/3, Main track.. While the ranking solution itself is the same, the scores for this package are intentionally multiplied by -1, as this significantly improves performance when sorting the elements, as well as making simple comparisons between elements more logical to the user.

Value

Score function returns a vector of type KramerSimpsonScores and length of powerRelation$elements (unless parameter elements is specified). Higher scoring elements are ranked higher.

Ranking function returns corresponding SocialRanking object.

References

Allouche T, Escoffier B, Moretti S, Öztürk M (2020). “Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions.” In Bessiere C (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, 17–23. doi:10.24963/ijcai.2020/3, Main track.

Simpson PB (1969). “On defining areas of voter choice: Professor Tullock on stable voting.” The Quarterly Journal of Economics, 83(3), 478–490.

Kramer GH (1975). “A dynamical model of political equilibrium.” Journal of Economic Theory, 16(2), 310–334.

See Also

Other CP-majority based functions: copelandScores(), cpMajorityComparison()

Other ranking solution functions: L1Scores(), L2Scores(), LPSScores(), LPScores(), copelandScores(), cumulativeScores(), lexcelScores(), ordinalBanzhafScores()

Examples

# 2 > (1 ~ 3) > 12 > (13 ~ 23) > {} > 123
pr <- as.PowerRelation("2 > (1~3) > 12 > (13~23) > {} > 123")

# get scores for all elements
# cpMajorityComparisonScore(pr, 2, 1, strictly = TRUE)[1] = 1
# cpMajorityComparisonScore(pr, 3, 1, strictly = TRUE)[1] = 0
# therefore the Kramer-Simpson-Score for element
# `1` = -max(0, 1) = -1
#
# Score analogous for the other elements
# `2` = 0
# `3` = -2
kramerSimpsonScores(pr)

# get scores for two elements
# `1` = 1
# `3` = 2
kramerSimpsonScores(pr, c(1,3))

# or single element
# result is still a list
kramerSimpsonScores(pr, 2)

# 2 > 1 > 3
kramerSimpsonRanking(pr)

Lexicographical Excellence

Description

Calculate the Lexicographical Excellence (or Lexcel) score.

lexcelRanking() returns the corresponding ranking.

dualLexcelRanking() uses the same score vectors but instead of rewarding participation, it punishes mediocrity.

Usage

lexcelScores(powerRelation, elements = powerRelation$elements)

lexcelRanking(powerRelation)

dualLexcelRanking(powerRelation)

Arguments

Details

An equivalence class \sum_i contains coalitions that are indifferent to one another. In a given power relation created with PowerRelation() or as.PowerRelation(), the equivalence classes are saved in ⁠$eqs⁠.

As an example, consider the power relation \succsim: 123 \succ (12 \sim 13 \sim 1 \sim \emptyset) \succ (23 \sim 1 \sim 2). The corresponding equivalence classes are:

\sum_1 = \lbrace 123 \rbrace, \sum_2 = \lbrace 12, 13, 1, \emptyset \rbrace, \sum_3 = \lbrace 23, 1, 2 \rbrace.

The lexcel score of an element is a vector wherein each index indicates the number of times that element appears in the equivalence class. From our example, we would get

\textrm{lexcel}(1) = [ 1, 3, 1 ], \textrm{lexcel}(2) = [ 1, 1, 2 ], \textrm{lexcel}(3) = [ 1, 1, 1 ].

Value

Score function returns a list of type LexcelScores and length of powerRelation$elements (unless parameter elements is specified). Each index contains a vector of length powerRelation$eqs, the number of times the given element appears in each equivalence class.

Ranking function returns corresponding SocialRanking object.

Lexcel Ranking

The most "excellent contribution" of an element determines its ranking against the other elements. Given two Lexcel score vectors \textrm{Score}(i) and \textrm{Score}(j), the first index x where \textrm{Score}(i)_x \neq \textrm{Score}(j)_x determines which element should be ranked higher.

From the previous example this would be 1 > 2 > 3, because:

\textrm{Score}(1)_2 = 3 > \textrm{Score}(2)_2 = \textrm{Score}(3)_2 = 1, \textrm{Score}(2)_3 = 2 > \textrm{Score}(3)_3 = 1.

Dual Lexcel Ranking

The dual lexcel works in reverse order and, instead of rewarding high scores, punishes mediocrity. In that case we get 3 > 1 > 2 because:

\textrm{Score}(3)_3 < \textrm{Score}(2)_3 and \textrm{Score}(3)_2 < \textrm{Score}(1)_2, \textrm{Score}(1)_3 < \textrm{Score}(2)_3.

References

Bernardi G, Lucchetti R, Moretti S (2019). “Ranking objects from a preference relation over their subsets.” Social Choice and Welfare, 52(4), 589–606.

Algaba E, Moretti S, Rémila E, Solal P (2021). “Lexicographic solutions for coalitional rankings.” Social Choice and Welfare, 57(4), 1–33.

Serramia M, López-Sánchez M, Moretti S, Rodríguez-Aguilar JA (2021). “On the dominant set selection problem and its application to value alignment.” Autonomous Agents and Multi-Agent Systems, 35(2), 1–38.

See Also

Other ranking solution functions: L1Scores(), L2Scores(), LPSScores(), LPScores(), copelandScores(), cumulativeScores(), kramerSimpsonScores(), ordinalBanzhafScores()

Examples

# note that the coalition {1} appears twice
# 123 > 12 ~ 13 ~ 1 ~ {} > 23 ~ 1 ~ 2
# E = {123} > {12, 13, 1, {}} > {23, 1, 2}
pr <- suppressWarnings(as.PowerRelation(
  "123 > (12 ~ 13 ~ 1 ~ {}) > (23 ~ 1 ~ 2)"
))

# lexcel scores for all elements
# `1` = c(1, 3, 1)
# `2` = c(1, 1, 2)
# `3` = c(1, 1, 1)
lexcelScores(pr)

# lexcel scores for a subset of all elements
lexcelScores(pr, c(1, 3))
lexcelScores(pr, 2)

# 1 > 2 > 3
lexcelRanking(pr)

# 3 > 1 > 2
dualLexcelRanking(pr)

Make Power Relation monotonic

Description

Given a powerRelation object, make its order monotonic.

Usage

makePowerRelationMonotonic(powerRelation, addMissingCoalitions = TRUE)

Arguments

Details

A power relation is monotonic if

T \subset S \Leftrightarrow S \succsim T.

for every coalition S \subseteq N.

Calling makePowerRelationMonotonic() on some PowerRelation object moves or adds coalitions to certain equivalence classes so that the power relation becomes monotonic.

Value

PowerRelation object containing the following values:

• ⁠$elements⁠: vector of elements

• ⁠$eqs⁠: equivalence classes. Nested list of lists, each containing vectors representing groups of elements in the same equivalence class

• ⁠$coalitionLookup⁠: ⁠function(v)⁠ taking a coalition vector v and returning the equivalence class it belongs to. See coalitionLookup() for more.

• ⁠$elementLookup⁠: ⁠function(e)⁠ taking an element e and returning a list of 2-sized tuples. See elementLookup() for more.

See Also

Other helper functions for transforming power relations: appendMissingCoalitions()

Examples

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

# notice that missing coalitions are automatically added,
# except for the empty set
pr <- as.PowerRelation("a > b > c")
makePowerRelationMonotonic(pr)
# (abc ~ ab ~ ac ~ a) > (bc ~ b) > c

# setting addMissingCoalitions to FALSE changes this behavior
pr <- as.PowerRelation("a > ab > c ~ {} > b")
makePowerRelationMonotonic(pr, addMissingCoalitions = FALSE)
# (ab ~ a) > (b ~ c ~ {})

# notice that an equivalence class containing an empty coalition
# automatically moves all remaining coalitions to that equivalence class.
pr <- as.PowerRelation("a > {} > b > c")
makePowerRelationMonotonic(pr)
# (abc ~ ab ~ ac ~ a) > (bc ~ b ~ c ~ {})

New Power Relation

Description

Deprecated. Use PowerRelation() instead.

Usage

newPowerRelation(...)

Arguments

Value

No return value.

New PowerRelation object

Description

Deprecated. Use as.PowerRelation() instead.

Usage

newPowerRelationFromString(...)

Arguments

Value

No return value.

Ordinal Banzhaf ranking

Description

Calculate the Ordinal Banzhaf scores, the number of positive and the number of negative marginal contributions.

ordinalBanzhafRanking() returns the corresponding ranking.

Usage

ordinalBanzhafScores(powerRelation, elements = powerRelation$elements)

ordinalBanzhafRanking(powerRelation)

Arguments

Details

Inspired by the Banzhaf index (Banzhaf III 1964), the Ordinal Banzhaf determines the score of element i by adding the amount of coalitions S \subseteq N \setminus \lbrace i \rbrace its contribution impacts positively (S \cup \lbrace i \rbrace \succ S) and subtracting the amount of coalitions where its contribution had a negative impact (S \succ S \cup \lbrace i \rbrace)(Khani et al. 2019).

The original definition only takes total power relations into account, where either S \succsim T or T \succsim S for every S,T \subseteq N. If coalitions are missing from the power relation, we may not be able to perform certain comparisons. To indicate these missing comparisons, the ordinal Banzhaf score of an element i also includes that number at index 3. I.e., if the ordinal Banzhaf score of an element is c(4, -2, 1), it means that it contributed positively to 4 coalitions and negatively to 2 others. For one coalition, no comparison could be made.

Value

Score function returns list of class type OrdinalBanzhafScores and length of powerRelation$elements. Each index contains a vector of three numbers, the number of positive marginal contributions, the number of negative marginal contributions, and the number of coalitions for which no comparison could be done. The first two numbers summed together gives us the actual ordinal Banzhaf score.

Ranking function returns corresponding SocialRanking object.

References

Khani H, Moretti S, Öztürk M (2019). “An ordinal banzhaf index for social ranking.” In 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), 378–384.

Banzhaf III JF (1964). “Weighted voting doesn't work: A mathematical analysis.” Rutgers L. Rev., 19, 317.

See Also

Other ranking solution functions: L1Scores(), L2Scores(), LPSScores(), LPScores(), copelandScores(), cumulativeScores(), kramerSimpsonScores(), lexcelScores()

Examples

pr <- as.PowerRelation("12 > (2 ~ {}) > 1")

# Player 1 contributes positively to {2}
# Player 1 contributes negatively to {empty set}
# Therefore player 1 has a score of 1 - 1 = 0
#
# Player 2 contributes positively to {1}
# Player 2 does NOT have an impact on {empty set}
# Therefore player 2 has a score of 1 - 0 = 0
ordinalBanzhafScores(pr)
# `1` = c(1, -1, 0)
# `2` = c(1, 0, 0)

ordinalBanzhafRanking(pr)
# 1 > 2

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.

Alternatively, use generateRandomPowerRelation() to create random power relations.

Usage

powerRelationGenerator(coalitions, startWithLinearOrder = FALSE)

generateNextPartition(gen)

generateRandomPowerRelation(coalitions, linearOrder = FALSE, monotonic = FALSE)

Arguments

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:

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.

A generator function. If the generator is already down to its last partition, it will throw an error.

Use generateNextPartition(gen) to skip to the next partition of the generator.

Note

Due to its implementation, randomPowerRelation() does not create weak orders uniformly. I.e., it is much less likely to generate linear orders even though they have the proportionally highest representation in the set of all weak orders.

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()
# ab > (a ~ b)

gen <- generateNextPartition(gen)
gen()
# ab > a > b

coalitions <- createPowerset(c('a','b'), includeEmptySet = FALSE)
# list(c('a','b'), 'a', 'b')

gen <- powerRelationGenerator(coalitions)
gen()
# (ab ~ a ~ b)

gen()
# (ab ~ b) > a

# skipping partition of size two, where the first partition has
# 2 coalitions and the second partition has 1 coalition
gen <- generateNextPartition(gen)
gen()
# ab > (a ~ b)

# only remaining partition is one of size 3, wherein each
# equivalence class is of size 1
gen <- generateNextPartition(gen)
gen()
# ab > a > b

# went through all partitions, it will only generate NULL now
gen <- generateNextPartition(gen)
stopifnot(is.null(gen()))


# create random power relation
generateRandomPowerRelation(coalitions)

# make sure it's monotonic, i.e., {1} > {1,2} cannot exist
# because {1} is a subset of {1,2}
generateRandomPowerRelation(coalitions, monotonic = TRUE)

Create relation matrix

Description

For a given PowerRelation object create a relations::relation() object.

Usage

powerRelationMatrix(
  powerRelation,
  domainNames = c("pretty", "numericPrec", "numeric")
)

## S3 method for class 'PowerRelation'
as.relation(x, ...)

Arguments

Details

Turn a PowerRelation object into a relations::relation() object. The incidence matrix can be viewed with relations::relation_incidence().

The columns and rows of a PowerRelation object are ordered by TODO powerRelation$rankingCoalitions. The relations package automatically sorts the columns and rows by their domain names, which is the reason the parameter domainNames is included. This way we ensure that the columns and rows are sorted by the order of the power relation.

Value

relations::relation() object to the corresponding power relation.

Cycles

A PowerRelation object is defined as being transitive. If a power relation includes a cycle, meaning that the same coalition appears twice in the ranking, all coalitions within that cycle will be considered to be indifferent from one another.

For example, given the power relation 1 \succ 2 \succ 3 \succ 1 \succ 12, the relation is somewhat equivalent to 1 \sim 2 \sim 3 \succ 12. There is no way to check for cycles in the incidence matrix only.

Call transitiveClosure() to remove cycles in a PowerRelation object.

See Also

relations::as.relation()

Examples

pr <- as.PowerRelation("12 > 1 > 2")
relation <- powerRelationMatrix(pr)

# do relation stuff
# Incidence matrix
# 111
# 011
# 001
relations::relation_incidence(relation)

# all TRUE
stopifnot(all(
  relations::relation_is_acyclic(relation),
  relations::relation_is_antisymmetric(relation),
  relations::relation_is_linear_order(relation),
  relations::relation_is_complete(relation),
  relations::relation_is_reflexive(relation),
  relations::relation_is_transitive(relation)
))


# a power relation where coalitions {1} and {2} are indifferent
pr <- as.PowerRelation("12 > (1 ~ 2)")
relation <- powerRelationMatrix(pr)

# Incidence matrix
# 111
# 011
# 011
relations::relation_incidence(relation)

# FALSE
stopifnot(!any(
  relations::relation_is_acyclic(relation),
  relations::relation_is_antisymmetric(relation),
  relations::relation_is_linear_order(relation)
))
# TRUE
stopifnot(all(
  relations::relation_is_complete(relation),
  relations::relation_is_reflexive(relation),
  relations::relation_is_transitive(relation)
))


# a pr with cycles
pr <- suppressWarnings(as.PowerRelation("12 > 1 > 2 > 1"))
relation <- powerRelationMatrix(pr)

# Incidence matrix
# 1111
# 0111
# 0111
# 0111
relations::relation_incidence(relation)

# custom naming convention
relation <- powerRelationMatrix(
  pr,
  function(x) paste0(letters[x], ":", paste(pr$rankingCoalitions[[x]], collapse = "|"))
)

relations::relation_incidence(relation)
# Incidences:
#       a:1|2 b:1 c:2 d:1
# a:1|2     1   1   1   1
# b:1       0   1   1   1
# c:2       0   1   1   1
# d:1       0   1   1   1

Test relation between two elements

Description

On a given PowerRelation object pr, check if e1 relates to e2 based on the given social ranking solution.

Usage

testRelation(powerRelation, e1)

powerRelation %:% e1

pr_e1 %>=dom% e2

pr_e1 %>dom% e2

pr_e1 %>=cumuldom% e2

pr_e1 %>cumuldom% e2

pr_e1 %>=cp% e2

pr_e1 %>cp% e2

pr_e1 %>=banz% e2

pr_e1 %>banz% e2

pr_e1 %>=cop% e2

pr_e1 %>cop% e2

pr_e1 %>=ks% e2

pr_e1 %>ks% e2

pr_e1 %>=lex% e2

pr_e1 %>lex% e2

pr_e1 %>=duallex% e2

pr_e1 %>duallex% e2

pr_e1 %>=L1% e2

pr_e1 %>L1% e2

pr_e1 %>=L2% e2

pr_e1 %>L2% e2

pr_e1 %>=LP% e2

pr_e1 %>LP% e2

pr_e1 %>=LPS% e2

pr_e1 %>LPS% e2

Arguments

Details

The function testRelation is somewhat only used to make the offered comparison operators in the package better discoverable.

testRelation(pr, e1) is equivalent to pr %:% e1 and list(pr, e1). It should be used together with one of the comparison operators listed in the usage section.

Value

testRelation() and ⁠%:%⁠ returns list(powerRelation, e1).

Followed by a ⁠%>=comparison%⁠ or ⁠%>comparison%⁠ it returns TRUE or FALSE, depending on the relation between e1 and e2.

See Also

Comparison function: dominates(), cumulativelyDominates(), cpMajorityComparison().

Score Functions: ordinalBanzhafScores(), copelandScores(), kramerSimpsonScores(), lexcelScores().

Examples

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

# Dominance
stopifnot(pr %:% 1 %>=dom% 2)

# Strict dominance
stopifnot((pr %:% 1 %>dom% 2) == FALSE)

# Cumulative dominance
stopifnot(pr %:% 1 %>=cumuldom% 2)

# Strict cumulative dominance
stopifnot((pr %:% 1 %>cumuldom% 2) == FALSE)

# CP-Majority relation
stopifnot(pr %:% 1 %>=cp% 2)

# Strict CP-Majority relation
stopifnot((pr %:% 1 %>cp% 2) == FALSE)

# Ordinal banzhaf relation
stopifnot(pr %:% 1 %>=banz% 2)

# Strict ordinal banzhaf relation
# (meaning 1 had a strictly higher positive contribution than 2)
stopifnot((pr %:% 1 %>banz% 2) == FALSE)

# Copeland-like method
stopifnot(pr %:% 1 %>=cop% 2)
stopifnot(pr %:% 2 %>=cop% 1)

# Strict Copeland-like method
# (meaning pairwise winning minus pairwise losing comparison of
# 1 is strictly higher than of 2)
stopifnot((pr %:% 1 %>cop% 2) == FALSE)
stopifnot((pr %:% 2 %>cop% 1) == FALSE)
stopifnot(pr %:% 3 %>cop% 1)

# Kramer-Simpson-like method
stopifnot(pr %:% 1 %>=ks% 2)
stopifnot(pr %:% 2 %>=ks% 1)

# Strict Kramer-Simpson-like method
# (meaning ks-score of 1 is actually higher than 2)
stopifnot((pr %:% 2 %>ks% 1) == FALSE)
stopifnot((pr %:% 1 %>ks% 2) == FALSE)
stopifnot(pr %:% 3 %>ks% 1)

# Lexicographical and dual lexicographical excellence
stopifnot(pr %:% 3 %>=lex% 1)
stopifnot(pr %:% 3 %>=duallex% 1)

# Strict lexicographical and dual lexicographical excellence
# (meaning their lexicographical scores don't match)
stopifnot(pr %:% 3 %>lex% 1)
stopifnot(pr %:% 3 %>duallex% 1)

# L^(1) and L^(2)
stopifnot(pr %:% 1 %>=L1% 2)
stopifnot(pr %:% 1 %>=L2% 2)

# Strict L^(1) and L^(2)
stopifnot((pr %:% 1 %>L1% 2) == FALSE)
stopifnot(pr %:% 3 %>L1% 1)

stopifnot((pr %:% 1 %>L2% 2) == FALSE)
stopifnot(pr %:% 3 %>L2% 1)

# L^p and L^p*
stopifnot(pr %:% 1 %>=LP% 2)
stopifnot(pr %:% 1 %>=LPS% 2)

# Strict L^(1) and L^(2)
stopifnot((pr %:% 1 %>LP% 2) == FALSE)
stopifnot(pr %:% 3 %>LP% 1)

stopifnot((pr %:% 1 %>LPS% 2) == FALSE)
stopifnot(pr %:% 3 %>LPS% 1)

Transitive Closure

Description

Apply transitive closure over power relation that has cycles.

Usage

transitiveClosure(powerRelation)

Arguments

Details

A power relation is a binary relationship between coalitions that is transitive. For coalitions a, b, c \in 2^N, this means that if a \succ b and b \succ c, then a \succ c.

A power relation with cycles is not transitive. A transitive closure over a power relation removes all cycles and turns it into a transitive relation, placing all coalitions within a cycle in the same equivalence class. If a \succ b \succ a, from the symmetric definition in PowerRelation() we therefore assume that a \sim b. Similarly, if a \succ b_1 \succ b_2 \succ \dots \succ b_n \succ a, the transitive closure turns it into a \sim b_1 \sim b_2 \sim \dots \sim b_n.

transitiveClosure() transforms a PowerRelation object with cycles into a PowerRelation object without cycles. As described above, all coalitions within a cycle then are put into the same equivalence class and all duplicate coalitions are removed.

Value

PowerRelation object with no cycles.

Examples

pr <- as.PowerRelation("1 > 2")

# nothing changes
transitiveClosure(pr)


pr <- suppressWarnings(as.PowerRelation("1 > 2 > 1"))

# 1 ~ 2
transitiveClosure(pr)


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

# 1 > 3 > 1 > 2 > 23 > 2 =>
# 1 ~ 3 > 2 ~ 23
transitiveClosure(pr)