Package 'socialranking'

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
includeEmptySet	If TRUE, include the empty set in the last equivalence class if it is missing from the power relation.

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

x	An object
...	Optional additional parameters
comparators	Vector of ">" or "~" characters

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
c1	Coalition vector
c2	Coalition vector

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
e1, e2	Elements in powerRelation$elements
strictly	Only include $D_{ij}(\succ)$ and $D_{ji}(\succ)$, i.e., coalitions $S \in 2^{N \setminus \lbrace i,j\rbrace}$ where $S \cup \lbrace i\rbrace \succ S \cup \lbrace j\rbrace$ and vice versa.
includeEmptySet	If TRUE, check $\lbrace i \rbrace \succsim \lbrace j \rbrace$ even if empty set is not part of the power relation.

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

elements	vector of elements
includeEmptySet	If TRUE, an empty vector is added at the end
result	What to do with the result. Can be either: "return": return list object "print": create valid string to call PowerRelation() or as.PowerRelation() and print it "copy": create valid string to call PowerRelation() or as.PowerRelation() and copy it to clipboard "printCompact" and "copyCompact": same as "print" and "copy" but without newlines

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.
e1, e2	Elements in powerRelation$elements
strictly	If TRUE, check if p1 strictly dominates p2

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))

---

Dominance

Description

Check if one element dominates the other.

Usage

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

Arguments

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
e1, e2	Elements in powerRelation$elements
strictly	If TRUE, check if p1 strictly dominates p2
includeEmptySet	If TRUE, check $\lbrace i \rbrace \succsim \lbrace j \rbrace$ even if empty set is not part of the power relation.

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))

---

Create a SocialRanking object

Description

Rank elements based on their scores.

Usage

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

Arguments

scores	A vector or list representing each element's score. If names(scores) is not NULL, those will be used as element names. Else a number sequence corresponding to the elements is generated.
compare	Optional comparison function taking in two elements and returning a numerical value based on the relation between these two elements. If set to NULL, the default order() function is called. See details for more information.
decreasing	If TRUE (default), elements with higher scores are ranked higher.

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"))
)

---

Element lookup

Description

List coalitions that an element appears in.

Usage

elementLookup(powerRelation, element)

Arguments

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
element	an element in powerRelation$elements

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
coalition	a coalition vector or that is part of powerRelation

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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)

---

L1 Ranking

Description

Calculate the $L^{(1)}$ scores.

Usage

L1Scores(powerRelation, elements = powerRelation$elements)

L1Ranking(powerRelation)

lexcel1Scores(powerRelation, elements = powerRelation$elements)

lexcel1Ranking(powerRelation)

Arguments

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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

---

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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)

---

LP Ranking

Description

Calculate the $L^{p}$ scores.

Usage

LPScores(powerRelation, elements = powerRelation$elements)

LPRanking(powerRelation)

lexcelPScores(powerRelation, elements = powerRelation$elements)

lexcelPRanking(powerRelation)

Arguments

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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

---

LP* Ranking

Description

Calculate the $L^{p^*}$ scores.

Usage

LPSScores(powerRelation, elements = powerRelation$elements)

LPSRanking(powerRelation)

lexcelPSScores(powerRelation, elements = powerRelation$elements)

lexcelPSRanking(powerRelation)

Arguments

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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

---

Make Power Relation monotonic

Description

Given a powerRelation object, make its order monotonic.

Usage

makePowerRelationMonotonic(powerRelation, addMissingCoalitions = TRUE)

Arguments

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
addMissingCoalitions	If TRUE, also include all coalitions in the power set of powerRelation$elements that are not present in the current power relation.

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

...	Any parameter.

Value

No return value.

---

New PowerRelation object

Description

Deprecated. Use as.PowerRelation() instead.

Usage

newPowerRelationFromString(...)

Arguments

...	Any parameter.

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

powerRelation	A PowerRelation object created by PowerRelation() or as.PowerRelation()
elements	Vector of elements of which to calculate their scores. By default, the scores of all elements in powerRelation$elements are considered.

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

---