Llull Rule (COMSOC)

Definition

Llull Rule ( COMSOC)

The Llull rule, named after Ramon Llull, is a voting rule awarding one point for each head-to-head contest an alternative wins or ties. For a profile $R=({\succ }_1,\dots ,{\succ }_n)$ of $n$ complete, strict rankings over $C$, let $N_R$ be its pairwise support function. Then

$$\begin{array}{rl}{\mathrm{Llull}}_R(x)& :=\underset{\text{opponents beaten or tied}}{\underbrace{|\{y\in C\setminus \{x\}:N_R(x,y)\ge N_R(y,x)\}|}},\\ {\lambda }_{\mathrm{Llull}}(R)& :=\arg \underset{x\in C}{\max }{\mathrm{Llull}}_R(x).\end{array}$$

Alternatives with the highest Llull score are Llull winners. A tied contest awards one point to each participant; a loss awards none. An alternative is not compared with itself.

Intuition

Compare an alternative with each opponent, then count how many contests it does not lose. A narrow victory and a large victory each contribute one point. Unlike Borda count, Llull counts favourable contest outcomes rather than summing the number of voters supporting the alternative across contests.

Condorcet Consistency

Suppose $c$ is the Condorcet winner. It defeats every opponent, while every other alternative loses at least its contest against $c$:

$$\begin{array}{rl}{\mathrm{Llull}}_R(c)& =m-1,\\ {\mathrm{Llull}}_R(x)& \le m-2(x\ne c).\end{array}$$

Therefore $c$ is the unique Llull winner. The rule is Condorcet consistent, even though it can also return winners when no Condorcet winner exists.

Winner Determination

For $n$ voters and $m$ alternatives, store each alternative’s position in each ballot. For each of the $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ pairs, inspect all $n$ voters to count who prefers which alternative. Award the points, then find the largest total. This takes $O(n{m}^2+m)$ time under unit-cost arithmetic and is polynomial.

Example

The same five-voter profile

Each row groups voters with the same complete ranking. The majority cycle shown below prevents a Condorcet winner, but Llull still returns a non-empty winner set.

Count one point per victory, not one point per supporting voter. There are no tied contests here because all five voters submit complete, strict rankings.

contest	majority winner	votes for winner–loser	point awarded to
$A$ vs. $B$	$A$	$3:2$	$A$
$A$ vs. $C$	$C$	$3:2$	$C$
$A$ vs. $D$	$D$	$3:2$	$D$
$B$ vs. $C$	$B$	$4:1$	$B$
$B$ vs. $D$	$B$	$3:2$	$B$
$C$ vs. $D$	$C$	$4:1$	$C$

Thus

$$\begin{array}{rlrl}{\mathrm{Llull}}_R(A)& =1& & \text{beats }B,\\ {\mathrm{Llull}}_R(B)& =2& & \text{beats }C,D,\\ {\mathrm{Llull}}_R(C)& =2& & \text{beats }A,D,\\ {\mathrm{Llull}}_R(D)& =1& & \text{beats }A.\end{array}$$

Hence ${\lambda }_{\mathrm{Llull}}(R)=\{B,C\}$. They are tied for the highest total, even though their contest against each other is not tied: $B$ defeats $C$ by $4:1$.