Strategy-proof vs Monotone
Hi Kristofer,
Le mercredi 19 janvier 2022, 08:57:59 UTC−6, Kristofer Munsterhjelm km_elmet@t-online.de a écrit :
However, monotone strategy resistant Condorcet methods are very hard to
understand. I'm still trying to devise a method that's Condorcet, DMTBR,
and monotone, but I haven't had much luck yet. I know through (more or
less) exhaustive search that for three candidates, fpA-fpC and
Smith,Carey are close to optimal. But as Craig himself pointed out,
generalizing to more than three candidates is very tough.
I was thinking, with Carey it seems like we should be able to say conclusively
that it can't be expanded to 4+ candidates. What stumps me though is that I'm
not sure how to explain what IFPP's improvement over FPP is supposed to be.
I guess we would have to say it's "more" clone independence, to get as much of
it as you can without sacrificing LNHarm, LNHelp, and Mono-raise. Then perhaps
it might be that 4+ IFPP is actually just FPP.
But I seem to recall that Craig did have an imperfect 4-candidate method
(whose definition was possibly not really expressible) that sacrificed
properties differently than that.
Of course, the same can be said about Smith and mono-add-top. I suspect
that in the case of complete ballots, Smith is not incompatible with
mono-add-top, although the question remains open (and is seemingly very
hard to prove or disprove).
I think it's hard only because we need to see what the actual scenarios and
ballots are which will run you into a contradiction. If you take Mono-add-top
and translate it to its "worst case" demands purely in terms of the graph of
wins/ties/losses, a daunting picture forms.
In the worst case, MATop's operation means leaving all of the winner's pairwise
contests unchanged (directionally), while every other contest is free to
change. In a Smith+MATop method, the MATop operation can't be allowed to remove
the winner from the Smith set. This means that the winner of such a method must
always be in the Smith set without reliance on any contests besides his own.
I think it's safe to say that the Smith set doesn't always have such a
candidate. In that case, this modified version of MATop isn't compatible with
Smith.
So, if Smith and MATop are compatible, it must be that for some reason, MATop is
not actually as demanding as it seems to be. That is, if the winner's Smith
membership depends on two other candidates' contest, for some reason in all such
cases under that method, we are assured that the MATop operation will not
disrupt that contest. Or else, that MATop will necessarily give that winner
additional pairwise wins that manage to keep him in the Smith set.
To me, it's too much to hope, that there is some technicality that will let us
do this.
However, Smith and the plurality criterion
combined are incompatible with mono-add-top. If asked, I would say that
the former is better than the latter, but I couldn't justify this
particular decision. There's ultimately some aspect of value judgement
to all of this.
I suppose, but practical arguments occur to me, even if some of them are based
on what I think other people's value judgments are.
Being a subset of Participation, Mono-add-top failures create complaints for a
specific selection of voters. It may be hard to nail down who exactly may or may
not be in that selection. That reduces the power of the complaint, I think.
I try also to imagine the complaint of a candidate who believes they have been
wronged by a MATop failure. He argues that if you delete a specific selection of
his votes, along with all other info on them, then he would have won. That feels
a bit weak to me as well.
Kevin
On 22.01.2022 20:53, Kevin Venzke wrote:
Hi Kristofer,
Le mercredi 19 janvier 2022, 08:57:59 UTC−6, Kristofer Munsterhjelm km_elmet@t-online.de a écrit :
However, monotone strategy resistant Condorcet methods are very hard to
understand. I'm still trying to devise a method that's Condorcet, DMTBR,
and monotone, but I haven't had much luck yet. I know through (more or
less) exhaustive search that for three candidates, fpA-fpC and
Smith,Carey are close to optimal. But as Craig himself pointed out,
generalizing to more than three candidates is very tough.
I was thinking, with Carey it seems like we should be able to say conclusively
that it can't be expanded to 4+ candidates. What stumps me though is that I'm
not sure how to explain what IFPP's improvement over FPP is supposed to be.
I guess we would have to say it's "more" clone independence, to get as much of
it as you can without sacrificing LNHarm, LNHelp, and Mono-raise. Then perhaps
it might be that 4+ IFPP is actually just FPP.
I'd say that IFPP's improvement for three candidates (and moreso fpA-fpC
or Smith,IFPP) is that it has the kind of strategy resistance that's
only (out of methods commonly discussed here) shared by IRV and
Smith-IRV hybrids respectively; and it does so while being monotone. So
it's evidence that you can have a monotone method that's robust to
strategy, and since every three-candidate minimally strategic method
seems to lie pretty close to it, it would presumably be a good building
block for a fully general such method.
Craig, of course, was not trying to find a Condorcet method and IIRC he
considered the Condorcet criterion to be inexpressible in his framework
(although I think that if I had been around then and had known what I
know now, I could've explained it in terms he'd have understood). He was
trying to find something that could pass as much of LNH and mutual
majority as possible while still being monotone. Fortunately for us, "as
much LNH as possible" ended up giving DMTBR when combined with Condorcet.
I suspect that if you have a base method X that passes DMT and DMTBR,
then Smith,X also passes it. (It'd be nice to have proof of this, and
particularly also Landau,X.)
But I seem to recall that Craig did have an imperfect 4-candidate method
(whose definition was possibly not really expressible) that sacrificed
properties differently than that.
I had the impression he had a number of not quite formed prototypes but
couldn't get where he desired with them.
To me, it's too much to hope, that there is some technicality that
will let us do this.
Right. Perhaps I don't have an intuitive sense of just how restrictive
it is, and so I think it's possible where it's not :-)
But if it's not possible, then there should be a Moulin-style proof of
it. Perhaps there's a relation between the kind of differential
constraint observations I've been doing and such proofs. A good first
step/example of this would be to convert my proof ideas for showing
unmanipulable majority incompatible with Condorcet, into a Moulin-style
exhaustive proof. I'd have to develop my theory a lot more before I
could do that, though!
-km
Hi Kristofer,
I'd say that IFPP's improvement for three candidates (and moreso fpA-fpC
or Smith,IFPP) is that it has the kind of strategy resistance that's
only (out of methods commonly discussed here) shared by IRV and
Smith-IRV hybrids respectively; and it does so while being monotone. So
it's evidence that you can have a monotone method that's robust to
strategy, and since every three-candidate minimally strategic method
seems to lie pretty close to it, it would presumably be a good building
block for a fully general such method.
Sure. Now, for whatever this is worth:
I was looking back and to my surprise, I actually once asked Craig why IFPP was
better than FPP. And specifically why should A lose this election:
49 A
40 B>C
11 C>B
He replied:
- Since all the axioms are relative, he can't make any judgment about an
isolated scenario. - Since IFPP elects B, electing A must violate an axiom, but he "lack[s] an
argument saying which." - "Proportionality" is an objective. This is probably the best answer, because
he seemed hostile to the (rather related) concept of clone independence.
Le samedi 22 janvier 2022, 16:46:38 UTC−6, Kristofer Munsterhjelm km_elmet@t-online.de a écrit :
Craig, of course, was not trying to find a Condorcet method and IIRC he
considered the Condorcet criterion to be inexpressible in his framework
(although I think that if I had been around then and had known what I
know now, I could've explained it in terms he'd have understood).
It was the definition of Schulze that he couldn't adapt, which led him to
criticize Markus for inadequately defining it and writing proofs about it.
Off-list I learned that he needed an equation for each candidate. So I sent him
definitions for 3-candidate MinMax(WV), MMPO, and DSC. However, he was reluctant
to accept from me that MinMax(WV) could stand in for Schulze(WV) with three
candidates.
Craig lays out his final take in this interesting 2005 post:
http://lists.electorama.com/pipermail/election-methods-electorama.com/2005-January/079981.html
Craig Carey wrote:
The main idea here is that a novel way to get answers out of believers in
Condorcet variants, is to ask the wrong people. It seems that they can
undo the problem of methods being fully undefined by using guessing or
soem other technique.
Also, Mr Venkze probably IGNORED the whole PDF article of Mr Schulze since
his "A-wins" expression had only 5 lines. Here is my argument:
The 3 "for loops" of the Schulze thing would lead to an expression that
would be nearer 90 lines long.
That polytope expression should simplify greatly, since it has to simplify
into the "ha2" expression (unless ha2 is wrong).
Anyway, to conclude, the Schulze (1-winner) method is rejected since it fails
Dr D. Woodall's Mono-Raise-Random. Ditto with Mr Heitzig's method etc.
The Alternative Vote is failed too. I guess the Alternative is better than
the Schulze method.
A better looking fairer Condorcet method than the Schulze method, might be
[the] MMPO (1-winner) Condorcet variant, since seeming to not fail
Monotonicity-2 when 3 candidates.
That last paragraph is odd because MMPO certainly doesn't seem to satisfy that
standard. But if MMPO can get a good review (despite Craig being aware that it
was indecisive) I regret that he didn't give the DSC equations a try. Maybe he
would have liked it.
On Mono-add-top:
To me, it's too much to hope, that there is some technicality that
will let us do this.
Right. Perhaps I don't have an intuitive sense of just how restrictive
it is, and so I think it's possible where it's not :-)
But if it's not possible, then there should be a Moulin-style proof of
it. Perhaps there's a relation between the kind of differential
constraint observations I've been doing and such proofs. A good first
step/example of this would be to convert my proof ideas for showing
unmanipulable majority incompatible with Condorcet, into a Moulin-style
exhaustive proof. I'd have to develop my theory a lot more before I
could do that, though!
For sure, a Moulin-style proof must be possible. But it will have a lot of steps
and scenarios. I could imagine that you start with a four-candidate Smith set
and show that each one cannot be the winner.
If one can prove that they are compatible, then that would be the event of the
decade for me. That would be a shock. And this doesn't take a proof, hopefully,
just a method definition. I'd accept results from simulations.
If they are compatible, studying this method might reveal a trick we could use
to squeeze other strategy guarantees out of Smith methods that I would currently
judge to be impossible. (Not sure what those could be, though.)
Kevin