Preference Profile (COMSOC)

Definition

Preference Profile ( COMSOC)

In COMSOC, a preference profile is the tuple of preferences of all voters over a common set of alternatives $C$. For voters $V=\{v_1,\dots ,v_n\}$ reporting strict preference rankings,

$$R=(\underset{\text{voter }{v}_1}{\underbrace{{\succ }_1}},\dots ,\underset{\text{voter }{v}_n}{\underbrace{{\succ }_n}}),$$

where $a{\succ }_{i}b$ means that voter $v_i$ prefers $a$ to $b$. The profile keeps one entry per voter, including repeated rankings; it is not a single collective ranking. Other models replace rankings by approval sets or scores.

Further, for alternatives $x,y\in C$, define $R(x,y)$ as the multiset of indices preferring $x$ over $y$, i.e.,

$$R(x,y):=\{i\mid x{\succ }_{iy}\},\forall x,y\in C.$$

Rankings as Relations

A ranking can be represented by a binary relation $⪰\subseteq C\times C$, where $a⪰b$ means “$a$ is at least as preferred as $b$”. It is complete and transitive:

$$\begin{array}{rl}\text{complete:}& \forall a,b\in C:a⪰b\vee b⪰a,\\ \text{transitive:}& \forall a,b,c\in C:(a⪰b\wedge b⪰c)\Rightarrow a⪰c.\end{array}$$

These conditions allow ties. To exclude them, additionally require antisymmetry:

$$a⪰b\wedge b⪰a\Rightarrow a=b,$$

which gives a total order, whose strict preference relation is

$$a\succ b⟺a⪰b\wedge a\ne b.$$

The notation ${\succ }_i$ above uses this no-ties convention.

Number of Rankings

For $m=|C|$ alternatives, a ranking without ties is a permutation: choose the first alternative in $m$ ways, the second in $m-1$ ways, and so on:

$$\underset{\text{choices for successive positions}}{\underbrace{m(m-1)\cdots 1}}=m!\le \underset{m\text{ factors}}{\underbrace{m\cdot m\cdots m}}=m^m.$$

Thus there are exactly $m!$ rankings, and $m!\in O(m^m)$. This count assumes no ties; completeness and transitivity alone do not imply it. For $n$ labelled voters, independently choosing their rankings gives $(m!{)}^n$ possible profiles.