Order theory

From Electowiki
(Redirected from Transitivity)
Jump to navigation Jump to search

Order theory looks at orderings of objects, based on various objects being "better" than or "before" others based on some metric. In the context of voting theory, ordering is generally used to understand the quality of candidates i.e. which candidates should win or come in 2nd place |, and to understand preferences in general i.e. a voter's 1st choice, 2nd choice, etc. can be thought of as an ordering.

It is quite common to represent orderings using ranking i.e. A>B=C>D means A is better than B, B is equal to C, and C is better than D. Depending on certain qualities that are implied in different contexts (discussed below), this may or may not imply that, for example, A is also better than D, or that A is even comparable to D.

Definitions[edit | edit source]

Transitivity: Broadly speaking, the concept that if between three objects (usually in the voting context, candidates. It could be more than three as well), the first object is better than the second object and the second object is better than the third object, then the first object must be better than the third object. See the Condorcet paradox for an example of how majority rule is intransitive.

Antisymmetry: If between two objects, First>=Second and Second>=First, then First=Second (if the first is better or equal to the second, and the second is better or equal to the first, then the two objects must be equal).

Connexity: Between two objects, either the first object is better than or equal to the second object, or the second object is better than or equal to the first object. (Either one candidate must beat or tie the other, or vice versa).

Chain: Similar to a beatpath, but satisfying transitivity, antisymmetry, and connexity.

Strength of preference[edit | edit source]

Regarding strength of preference (which is used in rated methods), there is likely an even stricter transitive property that can be thought of: if between three objects, the first object is (x amount) better than the second object, and the second object is better than the third object by any amount, then the first object must be at least (x amount) better than the third object as well (and if there are more than three objects, must be at least (x amount) better than all objects worse than the third object).

Another property that can be considered is that if the best object is better than the second-best object by any amount, and the second-best object is (y amount) better than the third-best object, then the best object must be at least (y amount) better than the third-best object as well (and all objects worse than the third-best object, in general).

To summarize, if between two objects A and B, A is better than B, then for any object that B is better than by some amount, A must be better than that object by at least the higher of that amount and the amount A is better than B, and likewise for any object A is better than by some amount, B may only be better (if at all) than that object by at most that amount.

Example: Suppose only the following pairwise comparison (margin) values are known for a single voter, with the table organized to show ranked preference (which is found by assuming transitivity of preference; suppose the maximum score is 1, with decimal scores allowed. Under this model, a positive number in a cell "First candidate over Second candidate" indicates a pairwise victory for the first candidate):

A B C D E
A --- 0.8
B --- 0.4
C --- 0.3
D --- 1.0
E ---

Then the following minimum or maximum margin values can be inferred for all of the other pairwise comparisons:

A B C D E
A --- 0.8 >=0.8 >=0.8 1.0
B 0 --- 0.4 >=0.4 1.0
C 0 0 --- 0.3 1.0
D 0 0 0 --- 1.0
E 0 0 0 0 ---

Informally speaking, because the voter expressed that D was "way better" than (i.e. maximally preferred to) E, it would only make sense that anyone the voter thought was better than D should also be "way better" than E, thus requiring they have the same maximal preference in their matchups against E. Also, for example, since the voter thought A was 0.8 points better than their 2nd choice B, who they thought was better than everyone else except for A, it only made sense that A was at least 0.8 points better than all the candidates B was better than as well, etc.

One of the ways to treat equal preferences (i.e. when a voter scores two candidates the same in their pairwise matchup) in this framework is to require that all pairwise preferences each of the equally preferred candidates have are the same i.e. if A pairwise ties B, then if A is 0.5 points better than C, B must also be 0.5 points better than C, etc.

One could instead argue that based on Score voting's way of looking at pairwise matchups (the strength of A>C is equal to A>B plus B>C) that transitivity of strength of preference should instead add up each transitive pairwise preference to decide the minimal score (or, if this would result in more than the max allowed differentiation, cap it at that). Using that approach, the above table is instead:

A B C D E
A --- 0.8 1.0 1.0 1.0
B 0 --- 0.4 >=0.7 1.0
C 0 0 --- 0.3 1.0
D 0 0 0 --- 1.0
E 0 0 0 0 ---

If there had been, say, an A>B:0.6 and B>C:0.3, a Score-based approach would treat that as being A>C:(>=0.9), whereas the first approach mentioned would simply require A>C:(>=0.6).

See Pairwise counting#Cardinal methods for an example of pairwise matchups between candidates done based on strength of preference. Note that intransitivity can be created in Condorcet methods even when they use strength of preference for their pairwise matchups; single-winner example:

1 A>B>C

1 B>C>A

1 C>A>B

If each voter indicates that their 1st choice is "maximally better" than their 2nd choice (meaning they put their preferred candidate at the highest score and the less-preferred candidate at the lowest score in that pairwise matchup) and that their 2nd choice is maximally better than their 3rd choice, then a Condorcet paradox occurs. If, however, every voter's strength of preference in each pairwise matchup is limited so that they can indicate only up to one maximally better pairwise matchup between consecutive preferences (meaning that they can say their 1st choice is maximally better than their 2nd choice, but must then not have a preference between their 2nd choice and 3rd choice, for example), then there is always a transitive societal ordering of the candidates (an ordering such that if between three candidates, the first is better than the second, and the second is better than the third, then the first is better than the third) based on the pairwise matchups.

Notes[edit | edit source]

For more information on using strength of preference in pairwise matchups, look for sources covering "fuzzy preferences" or "fuzzy sets" (which are compared to the regular Score voting scale, which is called "direct rating"). https://www.sciencedirect.com/science/article/pii/S0952197617300246 and https://link.springer.com/chapter/10.1007/978-3-642-36981-0_50 are examples.