Majority Graph (COMSOC)

Definition

Majority Graph ( COMSOC)

The majority graph of a profile $R$ of $n$ complete, strict rankings over alternatives $C$ is the digraph

$$\begin{array}{rl}G(R)& :=(C,E),\\ E& :=\{(x,y)\in C\times C:N_R(x,y)>n/2\},\end{array}$$

where $N_R$ is the pairwise support function. Each vertex is an alternative; an arc $x\to y$ exists exactly when a strict majority of voters prefers $x$ to $y$. The arrow points from the head-to-head winner to the loser. A tied pair has no arc in either direction.

The diagram uses the five-voter lecture profile; its weighted variant records the margins on these same arcs.