Thoughts about set methods
Here are some thoughts about methods made by composing sets and base
methods. Could you check if I'm right?
Define a "set" as a method that accepts an election and returns a set of
candidates. E.g. the Smith set is a set by this definition.
And define the method A,B where A is a set and B is a method, as picking
the member of A that's highest ranking according to B's social order (or
members, in case of a tie).
For a set, let the monotone inclusion criterion (or inclusion
monotonicity) be defined like this:
1. For any election where A is in the set, raising A can't insert
anyone else into the set;
2. lowering A can't boot anyone from the set before A is booted out;
3. and raising A can never boot A from the set if he's already in it,
nor can lowering A insert him into it if he's not.
(The Smith set, for instance, passes this criterion.)
First claim: Suppose X and Y inclusion-monotone sets, and Z is their
intersection (i.e. a candidate is in Z iff he's in both X and Y). Then Z
is inclusion-monotone.
1 and 2. If candidate C is in Z, then C is in both X and Y by
definition. Since both X and Y pass monotone inclusion, nobody can be
inserted into either of them by raising C. Thus nobody can be inserted
into Z either. The reasoning is analogous for the second condition.
3. C can't be booted from X by raising nor from Y since they're both
inclusion-monotone. Therefore C will remain in both if raised. (The
reasoning is analogous for the "lowering A" criterion.)
Second: Let A be a set and B be a method. If A is inclusion-monotone and
B passes mono-raise, then A,B passes mono-raise.
Proof idea: Consider an election e where candidate C is the winner
according to A,B. Then raising C could lead someone else to win if:
1a. B's social ordering ranks candidate C2 above C, and raising C
inserts C2 into the A set, or
2a. B's social ordering ranks candidate C right above C2, and raising C
removes C from the A set, or
3a. B is nonmonotone and raising C leads C2, who is also a member of A,
to be ranked ahead of C according to method B.
Lowering C could lead someone C to win if:
1b. B's social ordering ranks C over C2, and lowering C inserts him
into the A set, or
2b. B's social ordering ranks C2 right above C, and lowering C removes
C2 from the set, or
3b. B is nonmonotone (etc.)
In both cases, the first two possibilities are eliminated by the
inclusion monotonicity of A, and the third by B passing monotonicity. In
particular:
- Inclusion monotonicity condition 1 makes 1a impossible,
- Inclusion monotonicity condition 3 makes 2a impossible,
- B passing mono-raise makes 3a impossible,
- Inclusion monotonicity condition 3 makes 1b impossible,
- Inclusion monotonicity condition 2 makes 2b impossible,
- B passing mono-raise makes 3b impossible.
Hence raising C can't make him lose according to method A,B; nor can
lowering C make him win.
Does that seem right?
-km
It looks right ... and a valuable study that should be part of any
systematic exposition of Election Methods ...taking up where Woodall left
off.
On Sat, Nov 4, 2023, 2:47 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Here are some thoughts about methods made by composing sets and base
methods. Could you check if I'm right?
Define a "set" as a method that accepts an election and returns a set of
candidates. E.g. the Smith set is a set by this definition.
And define the method A,B where A is a set and B is a method, as picking
the member of A that's highest ranking according to B's social order (or
members, in case of a tie).
For a set, let the monotone inclusion criterion (or inclusion
monotonicity) be defined like this:
1. For any election where A is in the set, raising A can't insert
anyone else into the set;
2. lowering A can't boot anyone from the set before A is booted
out;
3. and raising A can never boot A from the set if he's already in
it,
nor can lowering A insert him into it if he's not.
(The Smith set, for instance, passes this criterion.)
First claim: Suppose X and Y inclusion-monotone sets, and Z is their
intersection (i.e. a candidate is in Z iff he's in both X and Y). Then Z
is inclusion-monotone.
1 and 2. If candidate C is in Z, then C is in both X and Y by
definition. Since both X and Y pass monotone inclusion, nobody can be
inserted into either of them by raising C. Thus nobody can be inserted
into Z either. The reasoning is analogous for the second condition.
3. C can't be booted from X by raising nor from Y since they're
both
inclusion-monotone. Therefore C will remain in both if raised. (The
reasoning is analogous for the "lowering A" criterion.)
Second: Let A be a set and B be a method. If A is inclusion-monotone and
B passes mono-raise, then A,B passes mono-raise.
Proof idea: Consider an election e where candidate C is the winner
according to A,B. Then raising C could lead someone else to win if:
1a. B's social ordering ranks candidate C2 above C, and raising C
inserts C2 into the A set, or
2a. B's social ordering ranks candidate C right above C2, and
raising C
removes C from the A set, or
3a. B is nonmonotone and raising C leads C2, who is also a member
of A,
to be ranked ahead of C according to method B.
Lowering C could lead someone C to win if:
1b. B's social ordering ranks C over C2, and lowering C inserts
him
into the A set, or
2b. B's social ordering ranks C2 right above C, and lowering C
removes
C2 from the set, or
3b. B is nonmonotone (etc.)
In both cases, the first two possibilities are eliminated by the
inclusion monotonicity of A, and the third by B passing monotonicity. In
particular:
- Inclusion monotonicity condition 1 makes 1a impossible,
- Inclusion monotonicity condition 3 makes 2a impossible,
- B passing mono-raise makes 3a impossible,
- Inclusion monotonicity condition 3 makes 1b impossible,
- Inclusion monotonicity condition 2 makes 2b impossible,
- B passing mono-raise makes 3b impossible.
Hence raising C can't make him lose according to method A,B; nor can
lowering C make him win.
Does that seem right?
-km
Election-Methods mailing list - see https://electorama.com/em for list
info