PowerRelation object

Create a PowerRelation object.

Usage

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

is.PowerRelation(x, ...)

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

Arguments

equivalenceClasses: A nested list of lists, each containing coalitions or groups represented as vectors that are in the same equivalence class.
elements: Vector of elements in power relation. Only set this value if you know what you are doing. See Details for more.
coalitionLookup: A function taking a vector parameter and returning an index. See return value for more details. Only set this value if you know what you are doing.
elementLookup: A function taking an element and returning a list of 2-sized tuples. See return value for more details. Only set this value if you know what you are doing.
x: An R object.
...: Additional arguments to be passed to or from methods.

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.

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

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.

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
# 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} > {} > ({apple, banana, chocolate} ~ {apple, banana} ~ {apple, chocolate})
# {banana, chocolate} > ({apple} ~ {chocolate}) > {banana} > {} > ...