CP-Majority relation

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.

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

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.

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

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
# 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)
#> [1]  2 -1
cpMajorityComparisonScore(pr, "b", "a") # c(0,-1)
#> [1]  1 -2