[EM] Unmanipulable majority and Condorcet

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

[EM] Unmanipulable majority and Condorcet

Forest Simmons


On Fri, Jan 3, 2020 at 1:02 PM <[hidden email]> wrote:
Send Election-Methods mailing list submissions to
        [hidden email]

To subscribe or unsubscribe via the World Wide Web, visit
        http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com

or, via email, send a message with subject or body 'help' to
        [hidden email]

Kristofer,

So it seems like UM and Condorcet are almost but not quite compatible ... tantalizingly close but "no banana" as they say.

It reminds me of how tntalizingly close we can get to a method that satisfies both the CC and the FBC:

Consider the method Majority Defeat Disqualification Top (symmetric completion). This method satisfies the CC but not the FBC.

 Now change it so that the symmetric completion does not apply to equal top. After this change it becomes MDDT(symmetric completion below top) and no longer satisfies the CC but does satisfy the FBC.

Any Insights?

Forest

Message: 2
Date: Fri, 3 Jan 2020 08:53:12 +0100
From: Kristofer Munsterhjelm <[hidden email]>
To: EM <[hidden email]>
Subject: [EM] Unmanipulable majority and Condorcet
Message-ID: <[hidden email]>
Content-Type: text/plain; charset=utf-8; format=flowed

A long time ago, I said that my fpA-fpC three-candidate method passed UM
and Condorcet. I've now found out that that's not the case.

Consider this election:

2: A>B>C
2+x: B>A>C
1-x: B>C>A
3: C>A>B

With x=1, A is the CW; with x=0, we have a tie-cycle (A>B, B>C, C=A).
With an x slightly less than zero, the election is a proper ABCA cycle.

The candidate scores are:
        A: fpA - fpC = 2 - 3 = -1
        B: fpB - fpA = 3 - 2 = 1
        C: fpC - fpB = 3 - 3 = 0

so the ordering is B>C>A no matter what x is within the allowed range.

I've been thinking about particular types of three-candidate Condorcet
methods. What I've been doing suggests that for a continuous method to
pass UM and Condorcet, it must return an A=B=C tie for every pairwise
tie election (i.e. where A=B, A=C, B=C). Furthermore, adding ballots to
turn A=B and A=C into A>B and B>C must make A win with certainty.

The reason is that if we're somewhere on the "A is the CW" side of the
(A>B, B>C, A=C) boundary, there exists an election where changing an
epsilon of a B>A>C ballot into B>C>A will get us *onto* that boundary.
Such a change leads to an UM violation if A doesn't win with certainty
afterwards.

(It also looks like the number of elections near the boundary with no
B>A>C ballots is so small compared to the number of elections with, that
any election that makes A win with certainty on the area of the boundary
you can reach by turning B>A>C into B>C>A must make A win with certainty
along the whole boundary. At least if it's continuous, although I've
only properly investigated a form of linear method.)

"Center-squeezy" methods like fpA-fpC fail by not returning an A=B=C tie
on every pairwise tied election. Methods like minmax pass the boundary
condition, but fail inside the ABCA cycle region itself.

What I'd have to show to have an actual impossibility proof is that it's
impossible to construct a method that both respects UM when going from
the "A always wins" region to the ABCA cycle region, and also respects
UM inside the region. I don't have that (yet, at least). But if I were
to guess, I think Condorcet and UM are incompatible. This is unfortunate
because it would otherwise be a good criterion to use to find
manipulation-resistant Condorcet methods.


------------------------------

Subject: Digest Footer

_______________________________________________
Election-Methods mailing list
[hidden email]
http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com


------------------------------

End of Election-Methods Digest, Vol 187, Issue 1
************************************************

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

Re: [EM] Unmanipulable majority and Condorcet

Kristofer Munsterhjelm-3
On 05/01/2020 22.58, Forest Simmons wrote:

>
>
> On Fri, Jan 3, 2020 at 1:02 PM
> <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Send Election-Methods mailing list submissions to
>             [hidden email]
>     <mailto:[hidden email]>
>
>     To subscribe or unsubscribe via the World Wide Web, visit
>            
>     http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com
>
>     or, via email, send a message with subject or body 'help' to
>             [hidden email]
>     <mailto:[hidden email]>
>
>     Kristofer,
>
>
> So it seems like UM and Condorcet are almost but not quite compatible
> ... tantalizingly close but "no banana" as they say.
>
> It reminds me of how tntalizingly close we can get to a method that
> satisfies both the CC and the FBC:
>
> Consider the method Majority Defeat Disqualification Top (symmetric
> completion). This method satisfies the CC but not the FBC.
>
>  Now change it so that the symmetric completion does not apply to equal
> top. After this change it becomes MDDT(symmetric completion below top)
> and no longer satisfies the CC but does satisfy the FBC.
>
> Any Insights?

I can't really analyze non-Condorcet methods with my pairwise approach,
so I can't say much about relaxations that give up (some) CC. I also
don't know if there's some magical nonlinear method that would pass UM
and Condorcet (although I seriously doubt there is).

Do you know of any ways to show that a set of partial differential
inequalities plus boundary conditions has no solution? (Maybe some kind
of trigonometry trick?)

But I can say what my hunches are based on what I've done so far.

I think that Condorcet and UM are most likely incompatible. I also think
that the hard part about Condorcet-complying methods is stitching the
various win regions together (in a transitive manner) so there's no
violation when one passes from one region to another. Compared to this,
making the interior of any given region well-behaved is easy.

More specifically, it's easy to have any two of "transitive,
well-behaved along the boundary, well-behaved on the interior", and it
seems to be easy to make the interior well-behaved with respect to a lot
of criteria at once if that's one of the two you pick, but passing
through a boundary requires a much harder edge condition.

Consider e.g. Smith,Minmax (only complete ballots allowed: no equal rank
or truncation). This would pass mono-add-top in the four-candidate case
if it weren't for counterexamples where adding an A-top ballot gets you
from a region with three Smith set members to four.

I also seem to recall that someone (might be Kevin Venzke) did a
simulation of the frequency of violations of FBC under impartial
culture, and found that Schulze (somehow uniquely among the Condorcet
methods he tested) had a very low rate of incidence. So this might also
suggest that the volume of trajectories given by favorite betrayal and
going from "A wins" through the boundary to "ABCA cycle" ending up at a
failure can be made very small. But my approach doesn't let me construct
methods that minimize the failure rate (over some vote distribution),
just to determine whether there exist methods that have failure rate
zero. And currently only for three candidates with strict rankings :-)
----
Election-Methods mailing list - see https://electorama.com/em for list info