[EM] Fwd: Paths of Least Resistance

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[EM] Fwd: Paths of Least Resistance

Forest Simmons
Here's a method similar to but simpler than Beatpath ... it defines the length of a beatpath as the sum of the losing votes along the path ... the total resistance put up by the losing teams along the path.

Enjoy!

---------- Forwarded message ----------
From: Forest Simmons <[hidden email]>
Date: Sunday, December 27, 2020
Subject: Paths of Least Resistance
To: Forest Simmons <[hidden email]>


Start by building a directed graph whose vertices are the alternatives under consideration, and edges are directed from winners to losers. Pairwise ties are represented by double arrows. The edges are weighted with the losing or tied votes. 

The length of a directed path is the sum of the weights of the traversed edges.

Define the directed distance d(x,y) from alternative x to alternative y as the length of the shortest directed path from  x to y, if there is one, else infinity.

The radius R(x, S) from x of a subset S of alternatives is the max (over y in S) of d(x, y). When S is the entire set of alternatives we abbreviate its radius from x as R(x).

Let T(x) be the number of ballots that do not rank x.

The Least Resistance Winner is the candidate that maximizes the sum T(x) + R(x).

Remark: for any uncovered candidate this sum is less than twice the number of ballots.

Comment: the truncation term T(x) in the sum is there to ensure that the method satisfies the Plurality Criterion.






----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Paths of Least Resistance

Forest Simmons
Should be "minimizes"

On Sunday, December 27, 2020, Forest Simmons <[hidden email]> wrote:
Here's a method similar to but simpler than Beatpath ... it defines the length of a beatpath as the sum of the losing votes along the path ... the total resistance put up by the losing teams along the path.

Enjoy!

---------- Forwarded message ----------
From: Forest Simmons <[hidden email]>
Date: Sunday, December 27, 2020
Subject: Paths of Least Resistance
To: Forest Simmons <[hidden email]>


Start by building a directed graph whose vertices are the alternatives under consideration, and edges are directed from winners to losers. Pairwise ties are represented by double arrows. The edges are weighted with the losing or tied votes. 

The length of a directed path is the sum of the weights of the traversed edges.

Define the directed distance d(x,y) from alternative x to alternative y as the length of the shortest directed path from  x to y, if there is one, else infinity.

The radius R(x, S) from x of a subset S of alternatives is the max (over y in S) of d(x, y). When S is the entire set of alternatives we abbreviate its radius from x as R(x).

Let T(x) be the number of ballots that do not rank x.

The Least Resistance Winner is the candidate that maximizes the sum T(x) + R(x).

Remark: for any uncovered candidate this sum is less than twice the number of ballots.

Comment: the truncation term T(x) in the sum is there to ensure that the method satisfies the Plurality Criterion.






----
Election-Methods mailing list - see https://electorama.com/em for list info