Weighted Majority Graph (COMSOC)

comsoc

Definition

Weighted Majority Graph

In COMSOC, the weighted majority graph of a preference profile is the majority graph together with a weight on each arc equal to the majority margin.

Given a profile

$$P:=(C,V,R),$$

let $G(P):=(U,E)$ be its majority graph. The weighted majority graph is the pair

$$(G(P),\omega )$$

where

$$\omega :E\to \mathbb{N}$$

is defined by

$$\omega (x,y):=N_R(x,y)-N_R(y,x).$$

Here $N_R(x,y)$ is the number of voters who rank $x$ above $y$. The arc direction says who wins the head-to-head contest; the weight says by how many votes.

Example

Lecture profile

For the lecture profile

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 weighted majority graph has arcs

$$A\stackrel{1}{\to }B,B\stackrel{3}{\to }C,B\stackrel{1}{\to }D,C\stackrel{1}{\to }A,C\stackrel{3}{\to }D,D\stackrel{1}{\to }A.$$

For example, $B$ defeats $C$ by margin $3$ because $4$ voters rank $B$ above $C$, while $1$ voter ranks $C$ above $B$.

Properties

Keeps direction and strength

A majority graph records only the direction of each strict majority contest. A weighted majority graph also records the strength of each victory.

Same winners by out-arcs

Adding weights does not change which arcs exist. Thus Condorcet winners and in-arc counts used by Lull’s Rule are read from the same underlying majority graph.