Weighted Majority Graph (COMSOC)

Definition

Weighted Majority Graph ( COMSOC)

The weighted majority graph of a profile $R$ is its majority graph

$$G(R)=(C,E)$$

together with a weight giving the winning margin of each arc:

$$\begin{array}{rl}(G(R),\omega ),\omega & :E⟶{\mathbb{N}}_{>0},\\ \omega (x,y)& :=N_R(x,y)-N_R(y,x).\end{array}$$

Here $N_R$ is the pairwise support function. The arrow points from winner to loser; its weight counts how many more voters support the winner. Every weight is positive because arcs represent strict victories. A tied pair has no arc, rather than a zero-weight arc.

Example

Margins for the five-voter profile

Each row groups voters with the same complete ranking:

The six arc weights in the definition’s graph are

$$\begin{array}{rlrl}\omega (A,B)& =3-2=1,& \omega (B,C)& =4-1=3,\\ \omega (B,D)& =3-2=1,& \omega (C,A)& =3-2=1,\\ \omega (C,D)& =4-1=3,& \omega (D,A)& =3-2=1.\end{array}$$

For example, the label $3$ on $B\to C$ is the margin $4-1$, not three voters supporting $B$.