Llull Winner (COMSOC)

Definition

Llull Winner ( COMSOC)

A Llull winner is an alternative with maximal Llull score in a profile $R$ over $C$:

$$x\in {\lambda }_{\mathrm{Llull}}(R)⟺\forall y\in C:{\mathrm{Llull}}_R(x)\ge {\mathrm{Llull}}_R(y).$$

The Llull rule returns all such alternatives. Several may be co-winners; a unique winner has strictly more points than every other alternative. A tie in total score does not imply that the co-winners tie their head-to-head contest.

Majority Graph

In the majority graph $G(R)=(C,E)$, let $m=|C|$ and let $d^{-}(x)$ be the number of incoming arcs at $x$. Each incoming arc records one lost contest. Therefore

$$\begin{array}{rl}{\mathrm{Llull}}_R(x)& =(m-1)-d^{-}(x),\\ {\lambda }_{\mathrm{Llull}}(R)& =\arg \underset{x\in C}{\max }(m-d^{-}(x))=\arg \underset{x\in C}{\min }{d}^{-}(x).\end{array}$$

A Llull winner has the fewest incoming arcs. The lecture expression $m-d^{-}(x)$ is one larger than the Llull score, but adding the same constant to every score leaves the winners unchanged.

Ties have no arc in either direction and earn a point under Llull. Thus maximising outgoing arcs alone is equivalent only when there are no tied contests.