Graph theory

From Electowiki
Jump to navigation Jump to search

Graph theory is the investigation of graphs, which shows the relationships between every pair of objects while only showing each object once within the same diagram. It is often used in the context of voting theory to discuss Condorcet methods, most of which use pairwise counting to determine which candidates or groups of candidates are better than others.

Definitions[edit | edit source]

Path: Also known as a walk (sometimes synonymous with chain, though not always; see Order theory#Definitions), it is when between any pair of nodes, one can go from the first node to the second by traveling through the nodes that fall "in between" (in other words, you can go from the first node to another node, to another node, to anoth... until you reach the second node). Often used when discussing beatpaths and the Schulze method.

Strongly connected component: A portion of a graph that is strongly connected (a path can be found from any node to any other node). Often used to find the Smith set in a graph of pairwise relations.

Pairwise counting[edit | edit source]

A graph can be used to show which candidates (or winner sets, when discussing proportional or non-proportional multi-winner methods) are pairwise preferred over others. Within such a graph, each candidate is considered to be a node (a point), and when an edge (a line) with an arrow points from one candidate's node towards another candidate's node, that indicates that the former candidate is preferred by more voters than the latter candidate in their pairwise matchup. If the arrow points both ways, this means that both candidates are in a pairwise tie.

One can optionally also indicate on a graph, for each pair of candidates, how many voters prefer one candidate over another and vice versa by putting the two numbers near or in the middle of the edge that connects the two candidates. Sometimes, only the number of voters who prefer the winner of the pairwise matchup (or if there is a tie, how many voters prefer one candidate over the other and also vice versa) is shown. For example, if between candidates A and B, 30 voters prefer A over B, and 20 voters prefer B over A, then on the edge connecting A and B, either the number "30" can be shown, or "30 (20)" can be shown. There are likely other, related ways used as well.

Some common concepts from Condorcet methods interpreted through graph theory:

Condorcet winner - a candidate who has arrows pointing away from them towards every other candidate, and no arrows from any other candidate pointing back to them.

Smith set - the smallest group of candidates such that arrows point away from any of the candidates in the group towards any candidate not in the group, and no arrows from any candidate not in the group point back to any candidate in the group.

Schwartz set - The same as the Smith set except arrows may point back from any candidate not in the group towards any candidate in the group.

Condorcet loser - The opposite of the Condorcet winner: a candidate who has arrows pointing towards them from every other candidate, and no arrows pointing away from them towards any other candidate.

Weak Condorcet winner - The same as the Condorcet winner except arrows may point back from other candidates towards them.

Weak Condorcet loser - The same as the Condorcet loser except arrows may point away from them towards other candidates.

The Schulze method in particular can be thought of in terms of beatpaths, which are defined for an ordered set of candidates such that on a graph representing pairwise preferences, an arrow points from the first candidate to the second, the second to the third, etc. all the way until the last candidate. A beat-or-tie path is the same except an arrow may point both ways between any pair of candidates ordered next to each other in the beatpath.

Also see[edit | edit source]

Set theory