Lull's Rule (COMSOC)

comsoc

Definition

Lull's Rule

In COMSOC, Lull’s Rule is a pairwise-comparison voting rule, named after Ramon Llull, where each alternative receives one point for every head-to-head contest that it wins or ties.

Let $C$ be a set of $m$ alternatives and let

$$R:=({\succ }_1,\dots ,{\succ }_n)$$

be a preference profile. For $x,y\in C$, let $N_R(x,y)$ be the number of voters who rank $x$ above $y$. The Lull score of $x$ is

$${\mathrm{Lull}}_R(x):=\left|\left\{y\in C\setminus \{x\}:N_R(x,y)\ge N_R(y,x)\right\}\right|.$$

A Lull winner is an alternative with maximum Lull score:

$$x\in \arg \underset{y\in C}{\max }{\mathrm{Lull}}_R(y).$$

Majority graph view

In-arcs count losses

In the majority graph of a profile, there is an arc $(x,y)$ when a strict majority of voters prefer $x$ to $y$. The number of in-arcs of an alternative is the number of pairwise contests it loses.

Therefore maximising the Lull score is equivalent to minimising the number of in-arcs. The lecture notes write this equivalent objective as maximising

$$m-\#\text{in-arcs}.$$

Example

Lecture profile

Consider the profile from the lecture notes:

voters	ranking
$2$	$A\succ B\succ C\succ D$
$1$	$B\succ C\succ D\succ A$
$1$	$C\succ D\succ A\succ B$
$1$	$D\succ B\succ C\succ A$

The pairwise majority victories are

$$A{\succ }_{M}B,B{\succ }_{M}C,B{\succ }_{M}D,C{\succ }_{M}A,C{\succ }_{M}D,D{\succ }_{M}A.$$

Hence the Lull scores are

$${\mathrm{Lull}}_R(A)=1,{\mathrm{Lull}}_R(B)=2,{\mathrm{Lull}}_R(C)=2,{\mathrm{Lull}}_R(D)=1.$$

Thus $B$ and $C$ are Lull co-winners.

Properties

Condorcet consistency

Lull’s Rule is a Condorcet consistent voting rule. If a Condorcet winner exists, then it wins all $m-1$ head-to-head contests and has the unique maximum Lull score.

Polynomial-time winner determination

To determine whether a given alternative $c^{\ast }\in C$ is a Lull winner, compute all pairwise majority contests and compare the Lull scores.

Thus Lull winner determination is solvable in polynomial time.