Preference Ranking (COMSOC)

Definition

Preference Ranking ( COMSOC)

In COMSOC, a preference ranking here means a strict preference ranking: it orders all alternatives in $C$ from most to least preferred, without ties. Let

$$\mathcal{L}(C):=\{\succ \subseteq C\times C:\succ \text{ is a strict total order on }C\}$$

denote the set of all such rankings. Here $a\succ b$ means that $a$ is preferred to $b$: the relation is irreflexive and transitive, and for distinct $a,b$, exactly one of $a\succ b$ or $b\succ a$ holds (asymmetry).

Strict and Non-strict Orders

“Strict” means preferred to, not at least as preferred as: $a\nsucc a$. Adding each self-comparison $(a,a)$ gives the corresponding non-strict linear order, without changing the order of distinct alternatives.

From Rankings to Profiles

Each voter contributes one ranking from $\mathcal{L}(C)$. A preference profile collects these rankings into one tuple:

$$\underset{\text{one ranking per voter}}{\underbrace{R=({\succ }_1,\dots ,{\succ }_n)}}\in \underset{n\text{ copies}}{\underbrace{\mathcal{L}(C)\times \cdots \times \mathcal{L}(C)}}=\mathcal{L}(C{)}^n.$$

Thus $\mathcal{L}(C{)}^n$ is the set of all $n$-voter profiles, not a numerical power or a ranking repeated $n$ times. Different voters may have different rankings or the same ranking.

Number of Rankings

For $m=|C|$, each ranking is a permutation of the alternatives:

$$|\mathcal{L}(C)|=\underset{\text{choices from first to last}}{\underbrace{m(m-1)\cdots 1}}=m!\le m^m.$$

Thus $|\mathcal{L}(C)|\in O(m^m)$. A strict order need not be total in general; the rankings in $\mathcal{L}(C)$ compare every pair of distinct alternatives.

Example

All rankings of three alternatives

For $C=\{a,b,c\}$, the $3!=6$ rankings are

$$\begin{array}{ccc}a\succ b\succ c& a\succ c\succ b& b\succ a\succ c\\ b\succ c\succ a& c\succ a\succ b& c\succ b\succ a.\end{array}$$

If voter $v_i$ ranks $a$ above $b$ above $c$, their relation is ${\succ }_i=\{(a,b),(b,c),(a,c)\}$. The pair $(a,c)$ records the comparison implied by transitivity.