Majority Graph (COMSOC)

comsoc

Definition

Majority Graph

In COMSOC, the majority graph of a preference profile is the directed graph that records which alternative defeats which other alternative by strict pairwise majority.

Given a profile

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

let

$$N_R(x,y):=\left|\{v_i\in V:x{\succ }_{i}y\}\right|$$

be the number of voters who prefer $x$ to $y$. The majority graph of $P$ is the digraph

$$G(P):=(U,E)$$

with vertex set $U:=C$ and arc set

$$E:=\{(x,y)\in C\times C:N_R(x,y)>N_R(y,x)\}.$$

Thus an arc $(x,y)$ means that $x$ defeats $y$ in their head-to-head majority contest.

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

$$A\to B,B\to C,B\to D,C\to A,C\to D,D\to A.$$

Properties

Condorcet winner as out-degree maximum

An alternative is a Condorcet winner exactly when its vertex has outgoing arcs to every other vertex. If $|C|=m$, this means out-degree $m-1$.

Weighted refinement

The weighted majority graph adds the majority margin to each arc of the majority graph.