Manipulation Resistant Voting
It is well known that there is no incentive for dishonest voting when the method is to elect the candidate indicated on a randomly chosen secret ballot.
Is there also a manipulation free deterministic method?
Here's one that satisfies the Condorcet Criterion when voters are rational and informed about the preferences of other voters.
The ballot is a binary decision tree with the root node at the top and the leaves marked with the names of the candidates at the bottom.
The voters mark each node to indicate their preferred decision, whether left branch or right.
A path is traced from the top to the bottom, choosing left or right at each node according to which choice is supported by by the preponderance of voters at that node.
The name marked on the leaf at the end of the path indicates the winning candidate.
When not sure, voters may copy published recommendations.
There is absolutely zero incentive to vote left at a node where you prefer the likely winner of the right branch.
So what is the catch? The catch is that it is not easy to construct a decision tree that is clone independent. Furthermore, if the tree is constructed on the basis of ballot ratings or rankings, those ballots will be subject to manipulation to secure a more favorable tree.
Is there a neutral process for constructing a clone-free decision tree?
... to be continued ...
Sent from my MetroPCS 4G LTE Android Device
I want to re-iterate that this method is completely immune to Burial, to "Dark Horse 3," to Chicken threats, etc. The only down side is potential clone dependence.
Kemeny-Young, Border, Copeland, and other clone dependent methods are still considered to be respectable methods despite their clone dependence, and various other defects like computational deficiencies (K-Y is NP hard), and vulnerabilities to manipulation, etc.
But we are not going to settle for any of those deficiencies ... if we can banish clone-dependence, then no defects remain ... finally, the holy grail of single winner deterministic election methods!
Sent from my MetroPCS 4G LTE Android Device
-------- Original message --------
From: Susan Simmons suzerainsimmons@outlook.com
Date: 7/16/21 7:58 PM (GMT-08:00)
To: election-methods@lists.electorama.com
Subject: Manipulation Resistant Voting
It is well known that there is no incentive for dishonest voting when the method is to elect the candidate indicated on a randomly chosen secret ballot.
Is there also a manipulation free deterministic method?
Here's one that satisfies the Condorcet Criterion when voters are rational and informed about the preferences of other voters.
The ballot is a binary decision tree with the root node at the top and the leaves marked with the names of the candidates at the bottom.
The voters mark each node to indicate their preferred decision, whether left branch or right.
A path is traced from the top to the bottom, choosing left or right at each node according to which choice is supported by by the preponderance of voters at that node.
The name marked on the leaf at the end of the path indicates the winning candidate.
When not sure, voters may copy published recommendations.
There is absolutely zero incentive to vote left at a node where you prefer the likely winner of the right branch.
So what is the catch? The catch is that it is not easy to construct a decision tree that is clone independent. Furthermore, if the tree is constructed on the basis of ballot ratings or rankings, those ballots will be subject to manipulation to secure a more favorable tree.
Is there a neutral process for constructing a clone-free decision tree?
... to be continued ...
Sent from my MetroPCS 4G LTE Android Device
Dear All,
My system, FAB STV: Four Averages Binomial STV is a statistical count, which all elections are held to be. I mean that there is no determinate election result. All elections are estimates. The more rigorous the statistical averaging of the result, the more proximate or accurate the estimate.
In other words, this view-point does not accept the premise of deterministic theorems, that there is some pre-determined right answer to who is elected.
FAB STV cannot be used strategically. No matter how one shuffles the preferences around, it cannot yield perverse results. It is monotonic.
That owes to its symmetric count for exclusions/eliminations with the election count. There is a symmetric count requirement because there is only one truth (to aspire to) in science.
That's what's wrong with MMP, it has two contradictory counts (both wrong, anyway).
The symmetric count makes a binomial count, subject to the binomial theorem, which means there are higher order counts. Tho, for most elections, the relatively simple first order count should do: one election count and one exclusion count (in reversed order of preferences).
Regards,
Richard Lung.
On 17 Jul 2021, at 3:58 am, Susan Simmons suzerainsimmons@outlook.com wrote:
It is well known that there is no incentive for dishonest voting when the method is to elect the candidate indicated on a randomly chosen secret ballot.
Is there also a manipulation free deterministic method?
Here's one that satisfies the Condorcet Criterion when voters are rational and informed about the preferences of other voters.
The ballot is a binary decision tree with the root node at the top and the leaves marked with the names of the candidates at the bottom.
The voters mark each node to indicate their preferred decision, whether left branch or right.
A path is traced from the top to the bottom, choosing left or right at each node according to which choice is supported by by the preponderance of voters at that node.
The name marked on the leaf at the end of the path indicates the winning candidate.
When not sure, voters may copy published recommendations.
There is absolutely zero incentive to vote left at a node where you prefer the likely winner of the right branch.
So what is the catch? The catch is that it is not easy to construct a decision tree that is clone independent. Furthermore, if the tree is constructed on the basis of ballot ratings or rankings, those ballots will be subject to manipulation to secure a more favorable tree.
Is there a neutral process for constructing a clone-free decision tree?
... to be continued ...
Sent from my MetroPCS 4G LTE Android Device
Election-Methods mailing list - see https://electorama.com/em for list info
On 17.07.2021 04:58, Susan Simmons wrote:
It is well known that there is no incentive for dishonest voting when
the method is to elect the candidate indicated on a randomly chosen
secret ballot.
Is there also a manipulation free deterministic method?
Doesn't Gibbard's theorem answer that in the negative?
-km
I'm sure that Gibbard considers clone dependence a vulnerability to manipulation. In this case, that vulnerability is limited to the possibility of lying on the questionaires eliciting the information for the construction of the decision tree. If the decision tree is generated randomly, then we are leaving determinism behind.
The Gibbard–Satterthwaite theorem states roughly that every deterministic voting rule is manipulable, except possibly in two cases: if there is a distinguished voter who has a dictatorial power, or if the rule limits the possible outcomes to two options only.
Once the decision tree has been constructed all decisions are of this binary type.
It may be true that Gibbard-Satterthwaite applies more or less to any deterministic democratic process that could be used to generate a decision tree.
In that case a proportionally fair stochastic procedure for generating the decision tree might be the best way forward.
At least, in my opinion, we have isolated the potential source of manipulability. What other methods make such a clean divide between voting day decisions and the possibilities of manipulation?
But enough abstract non-sense ... let's consider some practical possibilities for construction of the decision tree.
My best idea is to use standard decision tree software based on a metric (distance relation) on the leaves (candidates) of the tree.
So our problem becomes how to minimize manipulation of the information forming the basis for the metric on the candidates.
Suppose as a first approximation we ask the candidates themselves to estimate the distances between the various candidates on the various issues. They might be tempted to distort the truth to influence the structure of the decision tree to their advantage.
Not to worry ...instead of taking their estimates at face value by averaging them together ... suppose we pay more attention to how similar they are in their responses.
Then it doesn't matter so much if they try to distort the truth to their advantage, the closer they are to each other in candidate space, the more similar their responses, whether sincere or feigned.
So the distance function is not based per se on their distance estimates, but rather on the distance between their patterns of answers.
Their answer patterns are recorded as arrays of numbers called "data vectors." There are many possible "norms" for measuring the "magnitude" of a data vector.
The distance between two candidates is taken to be the magnitude of the difference between their pattern-of-response vectors.
This is the kind of psychometrics used by the NSA and other data miners to map out your precise location in political/consumer space without even listening in on your phone conversations.
The TV series Bull is based on this kind of psychometric analysis of jurors for finding "mirror jurors" that are very close in psychological distance from the actual jurors. Bull is a trial scientist who can predict the reaction of the actual jurors on the basis of the respective mirror juror reactions.
Do you find this to be interesting?
Sent from my MetroPCS 4G LTE Android Device
-------- Original message --------
From: Kristofer Munsterhjelm km_elmet@t-online.de
Date: 7/17/21 10:18 AM (GMT-08:00)
To: Susan Simmons suzerainsimmons@outlook.com, election-methods@lists.electorama.com
Subject: Re: [EM] Manipulation Resistant Voting
On 17.07.2021 04:58, Susan Simmons wrote:
It is well known that there is no incentive for dishonest voting when
the method is to elect the candidate indicated on a randomly chosen
secret ballot.
Is there also a manipulation free deterministic method?
Doesn't Gibbard's theorem answer that in the negative?
-km
On 07/17/2021 5:12 PM Susan Simmons suzerainsimmons@outlook.com wrote:
...
The Gibbard–Satterthwaite theorem states roughly that every deterministic voting rule is manipulable, except possibly in two cases: if there is a distinguished voter who has a dictatorial power, or if the rule limits the possible outcomes to two options only.
Could someone demonstrate here how, well outside a cycle, an insincere vote can bring in a tactical advantage with a Condorcet rule?
Say when would it be advantageous to bump your Number 2 to Number 1? Or when would it be advantageous to bury your Number 2?
And without going anywhere near a cycle.
--
r b-j . _ . _ . _ . _ rbj@audioimagination.com
"Imagination is more important than knowledge."
.
.
.
So far we have an election method that is non-manipulable to the extent that we can construct a clone-independent decision tree by a non-manipulable process, which in turn can be easily done with standard software if we can construct a suitable metric on the candidates via a manipulation free process.
That's where Marissa, an ex-NSA data analyst, fits into Bull's trial science corporation ... she's the one who knows how to find mirror juries.
Amazon, FaceBook, and Google have their counterparts to Marissa in real life, and they share/sell their data with/to the NSA ... in other words, there is no need to invent a psycho/political metric on the candidates ... there already exists such a metric on the psycho/political/consumer space of all Americans (and far more).
Bull the TV series is based partly on work pioneered by Doctor Phil before he became a TV personality. In the series his staff resorts to hacking internet data banks only as a last resort. Absent these hackers we might have to construct our own less elaborate metric on our candidates. But it is good to keep in mind that, at least in principle, the problem is already solved.
Her's one way to construct a binary tree given a suitable metric d(p, q) expessing the distance between p and q in candidate space:
Find two candidates p and q such that the furthest distance that any other candidate X would have to go to reach the closer of them is as small as possible. In other words find the smallest radius r such that neighborhoods of radius r centered at p and q contain (in their union) all of the candidates.
The root node of the tree, branches to the points closest to p and those closest to q.
Now recursively organize these two (Voronoi/Dirichlet) sets into subtrees.
That's it!
Sent from my MetroPCS 4G LTE Android Device
-------- Original message --------
From: Susan Simmons suzerainsimmons@outlook.com
Date: 7/17/21 2:12 PM (GMT-08:00)
To: Kristofer Munsterhjelm km_elmet@t-online.de, election-methods@lists.electorama.com
Subject: Re: [EM] Manipulation Resistant Voting
I'm sure that Gibbard considers clone dependence a vulnerability to manipulation. In this case, that vulnerability is limited to the possibility of lying on the questionaires eliciting the information for the construction of the decision tree. If the decision tree is generated randomly, then we are leaving determinism behind.
The Gibbard–Satterthwaite theorem states roughly that every deterministic voting rule is manipulable, except possibly in two cases: if there is a distinguished voter who has a dictatorial power, or if the rule limits the possible outcomes to two options only.
Once the decision tree has been constructed all decisions are of this binary type.
It may be true that Gibbard-Satterthwaite applies more or less to any deterministic democratic process that could be used to generate a decision tree.
In that case a proportionally fair stochastic procedure for generating the decision tree might be the best way forward.
At least, in my opinion, we have isolated the potential source of manipulability. What other methods make such a clean divide between voting day decisions and the possibilities of manipulation?
But enough abstract non-sense ... let's consider some practical possibilities for construction of the decision tree.
My best idea is to use standard decision tree software based on a metric (distance relation) on the leaves (candidates) of the tree.
So our problem becomes how to minimize manipulation of the information forming the basis for the metric on the candidates.
Suppose as a first approximation we ask the candidates themselves to estimate the distances between the various candidates on the various issues. They might be tempted to distort the truth to influence the structure of the decision tree to their advantage.
Not to worry ...instead of taking their estimates at face value by averaging them together ... suppose we pay more attention to how similar they are in their responses.
Then it doesn't matter so much if they try to distort the truth to their advantage, the closer they are to each other in candidate space, the more similar their responses, whether sincere or feigned.
So the distance function is not based per se on their distance estimates, but rather on the distance between their patterns of answers.
Their answer patterns are recorded as arrays of numbers called "data vectors." There are many possible "norms" for measuring the "magnitude" of a data vector.
The distance between two candidates is taken to be the magnitude of the difference between their pattern-of-response vectors.
This is the kind of psychometrics used by the NSA and other data miners to map out your precise location in political/consumer space without even listening in on your phone conversations.
The TV series Bull is based on this kind of psychometric analysis of jurors for finding "mirror jurors" that are very close in psychological distance from the actual jurors. Bull is a trial scientist who can predict the reaction of the actual jurors on the basis of the respective mirror juror reactions.
Do you find this to be interesting?
Sent from my MetroPCS 4G LTE Android Device
-------- Original message --------
From: Kristofer Munsterhjelm km_elmet@t-online.de
Date: 7/17/21 10:18 AM (GMT-08:00)
To: Susan Simmons suzerainsimmons@outlook.com, election-methods@lists.electorama.com
Subject: Re: [EM] Manipulation Resistant Voting
On 17.07.2021 04:58, Susan Simmons wrote:
It is well known that there is no incentive for dishonest voting when
the method is to elect the candidate indicated on a randomly chosen
secret ballot.
Is there also a manipulation free deterministic method?
Doesn't Gibbard's theorem answer that in the negative?
-km
On 7/17/21 11:12 PM, Susan Simmons wrote:
I'm sure that Gibbard considers clone dependence a vulnerability to
manipulation. In this case, that vulnerability is limited to the
possibility of lying on the questionaires eliciting the information for
the construction of the decision tree. If the decision tree is generated
randomly, then we are leaving determinism behind.
IIRC, it doesn't consider clone dependence to be a vulnerability to
strategy; the alternatives are given and then the voters either submit a
ranking (G-S) or interact with the method in one way or another
(Gibbard's later theorem).
The Gibbard–Satterthwaite theorem states roughly that every
deterministic voting rule is manipulable, except possibly in two cases:
if there is a distinguished voter who has a dictatorial power, or if the
rule limits the possible outcomes to two options only.
Once the decision tree has been constructed all decisions are of this
binary type.
It may be true that Gibbard-Satterthwaite applies more or less to any
deterministic democratic process that could be used to generate a
decision tree.
Gibbard-Satterthwaite probably wouldn't, because the tree construction
would fail universal domain. However, there is a more general theorem
that doesn't require universal domain:
https://en.wikipedia.org/wiki/Gibbard%27s_theorem
And I think not just the tree composition, but the method as a whole
would fail this.
Consider a mix of exhaustive runoff and agenda, where the agenda is set
beforehand, and then there are (n-1) one-on-one elections after which
the candidate standing at the end is the winner.
Now suppose there's a typical Condorcet cycle A>B>C>A and the agenda
ordering is A>B>C; so the method proceeds by matching B and C, and then
matching the winner with A, and then the outcome of this is the final
winner.
Under honesty, B beats C pairwise and then A beats B pairwise. But the
voters whose honest ranking is B>C>A have an incentive to misreport
their B vs C preference in the first round so that C beats B pairwise
and then goes on to beat A pairwise. Even though every round is a duple
(only one of two outcomes are possible), this is not true for the
composite rule, and so it fails Gibbard.
I would suspect your method also is vulnerable to strategy for the same
reason.
In reference to an earlier post of mine, suppose we define honesty as
what a Random Ballot type method would return. In your method, this
would be a trace down the tree that ends at the candidate who the voter
prefers most of the candidates at the bottom level of the tree. Now
suppose say, that the tree is
A
/ \
B C
/ \ /
D E F G
There are some voters whose honest vote is G>C>A>B>D>E>F, so their
honest trace would go down the C branch and end at G. However, they know
that if the C branch is chosen, then a vast majority will go for F. Thus
they falsify their ballots to indicate a preference for the B branch
instead (a compromising strategy) because they prefer both D and E to F.
Suppose as a first approximation we ask the candidates themselves to
estimate the distances between the various candidates on the various
issues. They might be tempted to distort the truth to influence the
structure of the decision tree to their advantage.
Not to worry ...instead of taking their estimates at face value by
averaging them together ... suppose we pay more attention to how similar
they are in their responses.
Then it doesn't matter so much if they try to distort the truth to their
advantage, the closer they are to each other in candidate space, the
more similar their responses, whether sincere or feigned.
I imagine you could end up with "false issues" that don't really matter,
but that the candidates agree to play up. Imagine a country that admits
about a hundred immigrants a year. Both major parties are seeking to
weaken the rule of law, but to distinguish themselves, they make a big
fuss about whether even fewer immigrants should be admitted to the
country or not - even though the number, as is, is insignificant in the
grand scheme of things.
It would be much harder to do so in a ranked voting setup because of the
(relatively) easier entry by newcomers. However, it's possible that
everybody will have an incentive to accept an extra dimension of
differentiation, for the purpose of strategically engineering the tree
structure.
So the distance function is not based per se on their distance
estimates, but rather on the distance between their patterns of answers.
Their answer patterns are recorded as arrays of numbers called "data
vectors." There are many possible "norms" for measuring the "magnitude"
of a data vector.
The distance between two candidates is taken to be the magnitude of the
difference between their pattern-of-response vectors.
This is the kind of psychometrics used by the NSA and other data miners
to map out your precise location in political/consumer space without
even listening in on your phone conversations.
The TV series Bull is based on this kind of psychometric analysis of
jurors for finding "mirror jurors" that are very close in psychological
distance from the actual jurors. Bull is a trial scientist who can
predict the reaction of the actual jurors on the basis of the respective
mirror juror reactions.
Do you find this to be interesting?
Possibly, but if we're going in a jury direction, I think a method like
sortition or even a mixed process like the Venetian Doges' would be more
appropriate. Maybe all this finding flaws in methods have turned me into
a "nah, that won't work" kind of guy :-)
On 7/18/21 5:30 AM, robert bristow-johnson wrote:
On 07/17/2021 5:12 PM Susan Simmons suzerainsimmons@outlook.com wrote:
...
The Gibbard–Satterthwaite theorem states roughly that every
deterministic voting rule is manipulable, except possibly in two cases:
if there is a distinguished voter who has a dictatorial power, or if the
rule limits the possible outcomes to two options only.
Could someone demonstrate here how, well outside a cycle, an
insincere vote can bring in a tactical advantage with a Condorcet rule?
Say when would it be advantageous to bump your Number 2 to Number 1?
Or when would it be advantageous to bury your Number 2?
And without going anywhere near a cycle.
There are two cases where it would be beneficial to do strategy.
Number one is when there is currently a CW, but a faction can alter its
votes to create a cycle. Then it's beneficial if they prefer the cycle
tiebreaker winner to the CW. (Or vice versa, for that matter)
Number two is where there is a cycle and the tiebreaker itself is
vulnerable to strategy.
If the voters are constrained so that they can only submit ballots which
in aggregate makes a CW, then every Condorcet method passes IIA (since
if the CW is removed, it's not an irrelevant candidate, and if someone
else is removed, the CW remains the CW). I think, though I'm not sure,
that this also makes it strategy-proof.
My point, though, is that you don't just have strategy behavior inside
the cycle domain, you also have strategy by deliberately pushing the
method into (or out of) a cycle.
-km
Here's the key: there are two ways to use binary trees for binary decision voting: bottom up and top down.
The meaning of honest/sincere voting is perfectly clear in the bottom up context, but the incentive for insicere voting is generally unavoidable.
Given the same tree, the optimum rational top-down strategy is to always vote for the branch whose expected outcome is greater.
Under perfect information with all rational players this top down optimum strategy solution is unique and sure ... the bottom-down winner will be the same candidate as the sincere bottom-up winner!
This can be proven recursively ... if it is true for both branches from the root node, it will be true for the entire tree. And (initial condition) it is obviously true for a subtree with only two leaves (candidates). These two facts are the only necessary ingredients for an inductive/recursive proof. (Induction on the depth of the sub tree is another form of a recursive proof.)
Sent from my MetroPCS 4G LTE Android Device
-------- Original message --------
From: Kristofer Munsterhjelm km_elmet@t-online.de
Date: 7/18/21 1:48 AM (GMT-08:00)
To: robert bristow-johnson rbj@audioimagination.com, Susan Simmons suzerainsimmons@outlook.com, election-methods@lists.electorama.com
Subject: Re: [EM] Manipulation Resistant Voting
On 7/18/21 5:30 AM, robert bristow-johnson wrote:
On 07/17/2021 5:12 PM Susan Simmons suzerainsimmons@outlook.com wrote:
...
The Gibbard–Satterthwaite theorem states roughly that every
deterministic voting rule is manipulable, except possibly in two cases:
if there is a distinguished voter who has a dictatorial power, or if the
rule limits the possible outcomes to two options only.
Could someone demonstrate here how, well outside a cycle, an
insincere vote can bring in a tactical advantage with a Condorcet rule?
Say when would it be advantageous to bump your Number 2 to Number 1?
Or when would it be advantageous to bury your Number 2?
And without going anywhere near a cycle.
There are two cases where it would be beneficial to do strategy.
Number one is when there is currently a CW, but a faction can alter its
votes to create a cycle. Then it's beneficial if they prefer the cycle
tiebreaker winner to the CW. (Or vice versa, for that matter)
Number two is where there is a cycle and the tiebreaker itself is
vulnerable to strategy.
If the voters are constrained so that they can only submit ballots which
in aggregate makes a CW, then every Condorcet method passes IIA (since
if the CW is removed, it's not an irrelevant candidate, and if someone
else is removed, the CW remains the CW). I think, though I'm not sure,
that this also makes it strategy-proof.
My point, though, is that you don't just have strategy behavior inside
the cycle domain, you also have strategy by deliberately pushing the
method into (or out of) a cycle.
-km