Discussion:
[EM] Voting Benchmark
Marijn Stollenga
2015-09-30 09:12:10 UTC
Permalink
Hello,

I am implementing a new election method, after initially playing with
Schulze voting. In the process I really want to compare my method to
Schulze and other methods according to several types of quality. Is
there a good benchmark currently, that I can start from?

Marijn

----
Election-Methods mailing list - see http://electorama.com/em for list info
Juho Laatu
2015-09-30 09:41:49 UTC
Permalink
Good question. My opinion is that there are lots of opinions, targets and criteria, but no agreed benchmark that you could use. You mentioned your intention to compare your method to other well known methods. I think that is the correct approach.

You can find many discussions on this mailing list on what methods and properties are good. You can find also many definitions and criteria that people have collected at electorama.com. You can also send a description of the method to this mailing list. I'm sure people will point out possible benefits and problems of the proposed method, and that way you will quickly find out what properties and criteria people consider most relevant in this case.

Juho
Post by Marijn Stollenga
Hello,
I am implementing a new election method, after initially playing with Schulze voting. In the process I really want to compare my method to Schulze and other methods according to several types of quality. Is there a good benchmark currently, that I can start from?
Marijn
----
Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info
Kevin Venzke
2015-09-30 12:40:46 UTC
Permalink
Hi Marijn,
I think you might start with the criteria that motivated Schulze, or criteria that differentiate popular methods.
For instance:Schulze: clone independence, monotonicity (mono-raise), Condorcet, SchwartzIRV: clone independence, later-no-harm, later-no-helpApproval: participation, favorite betrayal (FBC)
Unfortunately it's not necessarily straightforward to demonstrate that a new method satisfies or doesn't satisfy some criterion.
Some of us have simulations to attempt to gauge the incentives to use specific strategies (e.g. compromise, truncation, burial). But since simulations are based on the programmer's assumptions, nothing is standardized.
My hunch (based on my own experiments from 10+ years ago) is that if Schulze is your original inspiration or standard, and you make your own rank method, you may make something that gives similar results to Schulze, but most likely it won't satisfy all of Schulze's technical criteria.
Kevin
De : Marijn Stollenga <***@gmail.com>
À : "election-***@lists.electorama.com" <election-***@lists.electorama.com>
Envoyé le : Mercredi 30 septembre 2015 4h12
Objet : [EM] Voting Benchmark

Hello,

I am implementing a new election method, after initially playing with
Schulze voting. In the process I really want to compare my method to
Schulze and other methods according to several types of quality. Is
there a good benchmark currently, that I can start from?

Marijn

----
Election-Methods mailing list - see http://electorama.com/em for list info
Marijn Stollenga
2015-10-01 09:21:53 UTC
Permalink
Yes, actually my main motivation was the strange properties in Schulze
that I didn't like.
Firstly, the propagation of votes through beaten path sounds
interesting, but it is also pretty strange. By voting a dominance of A
over B, you might end up voting for C if some large other group votes C
over A a lot, even if you don't like C at all. This leads to some
complex tactical voting.

Secondly, the votes only flow if A over B has more votes than B over A
say. On first sight this sounds good but introduces a sensitivity in the
method that can completely flip results with a small change of votes,
also leading to possible loss of votes and tactical voting. Why can't
votes simply flow both directions? In my implementation I tried it and
it still led to dominant results in my experiments, but I guess it's
needed for certain properties?

Any thoughts?

Marijn
Post by Kevin Venzke
Hi Marijn,
I think you might start with the criteria that motivated Schulze, or
criteria that differentiate popular methods.
Schulze: clone independence, monotonicity (mono-raise), Condorcet,
Schwartz
IRV: clone independence, later-no-harm, later-no-help
Approval: participation, favorite betrayal (FBC)
Unfortunately it's not necessarily straightforward to demonstrate that
a new method satisfies or doesn't satisfy some criterion.
Some of us have simulations to attempt to gauge the incentives to use
specific strategies (e.g. compromise, truncation, burial). But since
simulations are based on the programmer's assumptions, nothing is
standardized.
My hunch (based on my own experiments from 10+ years ago) is that if
Schulze is your original inspiration or standard, and you make your
own rank method, you may make something that gives similar results to
Schulze, but most likely it won't satisfy all of Schulze's technical
criteria.
Kevin
------------------------------------------------------------------------
*Envoyé le :* Mercredi 30 septembre 2015 4h12
*Objet :* [EM] Voting Benchmark
Hello,
I am implementing a new election method, after initially playing with
Schulze voting. In the process I really want to compare my method to
Schulze and other methods according to several types of quality. Is
there a good benchmark currently, that I can start from?
Marijn
----
Election-Methods mailing list - see http://electorama.com/em
<http://electorama.com/em>for list info
Kevin Venzke
2015-10-01 13:18:49 UTC
Permalink
Hi Marijn,
Yes, a few thoughts:1. The path tracing (propagation of votes through paths) may seem odd, and it does create problems if you want to create guarantees about the effect of a given ballot (like LNHarm or FBC). But path tracing can provide a useful framework for resolving clone situations or Condorcet cycles. I'd note also that the problem of "voting A>B can help C" is a problem common to many or most election methods.2. Regarding sensitivity to a small change in votes: I would suggest that this is true even with a two-way FPP election: a contest's win vs. loss is the most important thing, and considering the strength of the win at all is a novelty. But it's an interesting question, whether the single-direction flow of votes creates more tactical voting opportunities.3. I call Schulze with votes flowing in both directions "Schulze(pairwise opposition)." The results can be less decisive. For example, suppose that candidate A has 45% of the vote (bullet votes, no lower preferences), and the rest of the votes are some combination of B, C, B>C, and C>B votes. Say there is an A>C>B>A cycle. It's likely that B and C will tie for the win because each received their greatest opposition from A. Whatever tiebreaker rule is used, if it elects C, and C has fewer preferences in total than A's 45% in first preferences, that would violate the Plurality criterion. Some of us would find that to be a bad outcome (i.e. hard to defend), so you may want to consider it.
Kevin

De : Marijn Stollenga <***@gmail.com>
À : Kevin Venzke <***@yahoo.fr>; "election-***@lists.electorama.com" <election-***@lists.electorama.com>
Envoyé le : Jeudi 1 octobre 2015 4h21
Objet : Re: [EM] Voting Benchmark

Yes, actually my main motivation was the strange properties in Schulze that I didn't like.
Firstly, the propagation of votes through beaten path sounds interesting, but it is also pretty strange. By voting a dominance of A over B, you might end up voting for C if some large other group votes C over A a lot, even if you don't like C at all. This leads to some complex tactical voting.

Secondly, the votes only flow if A over B has more votes than B over A say. On first sight this sounds good but introduces a sensitivity in the method that can completely flip results with a small change of votes, also leading to possible loss of votes and tactical voting. Why can't votes simply flow both directions? In my implementation I tried it and it still led to dominant results in my experiments, but I guess it's needed for certain properties?

Any thoughts?

Marijn

On 30/09/15 14:40, Kevin Venzke wrote:



Hi Marijn,
I think you might start with the criteria that motivated Schulze, or criteria that differentiate popular methods.
For instance: Schulze: clone independence, monotonicity (mono-raise), Condorcet, Schwartz IRV: clone independence, later-no-harm, later-no-help Approval: participation, favorite betrayal (FBC)
Unfortunately it's not necessarily straightforward to demonstrate that a new method satisfies or doesn't satisfy some criterion.
Some of us have simulations to attempt to gauge the incentives to use specific strategies (e.g. compromise, truncation, burial). But since simulations are based on the programmer's assumptions, nothing is standardized.
My hunch (based on my own experiments from 10+ years ago) is that if Schulze is your original inspiration or standard, and you make your own rank method, you may make something that gives similar results to Schulze, but most likely it won't satisfy all of Schulze's technical criteria.
Kevin
De : Marijn Stollenga <***@gmail.com>
À : "election-***@lists.electorama.com" <election-***@lists.electorama.com>
Envoyé le : Mercredi 30 septembre 2015 4h12
Objet : [EM] Voting Benchmark

Hello,

I am implementing a new election method, after initially playing with
Schulze voting. In the process I really want to compare my method to
Schulze and other methods according to several types of quality. Is
there a good benchmark currently, that I can start from?

Marijn

----
Election-Methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2015-10-01 11:27:09 UTC
Permalink
Hallo,
The votes only flow if A over B has more votes than B over A
say. On first sight this sounds good but introduces a sensitivity in the
method that can completely flip results with a small change of votes,
also leading to possible loss of votes and tactical voting. Why can't
votes simply flow both directions? In my implementation I tried it and
it still led to dominant results in my experiments, but I guess it's
needed for certain properties?
Here is my paper:

http://m-schulze.9mail.de/schulze1.pdf

The presumption that wins are always stronger that losses is
presumption (2.1.2).

Presumption (2.1.2) is needed to prove compliance with the
Schwartz criterion, the Smith criterion, and independence
of Smith-dominated alternatives.

Presumption (2.1.2) is not needed to prove transitivity,
resolvability, Pareto, monotonicity, reversal symmetry,
or independence of clones.

Markus Schulze


----
Election-Methods mailing list - see http://electorama.com/em for list info
Marijn Stollenga
2015-10-01 17:10:46 UTC
Permalink
Thank you for the reply. So it seems pretty essential to get these nice
properties. I wonder if there are other ways to get them, i.e. it's not
proven to be the only way to get these properties I guess?

Marijn
Post by Markus Schulze
Hallo,
The votes only flow if A over B has more votes than B over A
say. On first sight this sounds good but introduces a sensitivity in the
method that can completely flip results with a small change of votes,
also leading to possible loss of votes and tactical voting. Why can't
votes simply flow both directions? In my implementation I tried it and
it still led to dominant results in my experiments, but I guess it's
needed for certain properties?
http://m-schulze.9mail.de/schulze1.pdf
The presumption that wins are always stronger that losses is
presumption (2.1.2).
Presumption (2.1.2) is needed to prove compliance with the
Schwartz criterion, the Smith criterion, and independence
of Smith-dominated alternatives.
Presumption (2.1.2) is not needed to prove transitivity,
resolvability, Pareto, monotonicity, reversal symmetry,
or independence of clones.
Markus Schulze
----
Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2015-10-01 20:14:25 UTC
Permalink
Hallo,
Post by Marijn Stollenga
Thank you for the reply. So it seems pretty essential
to get these nice properties. I wonder if there are
other ways to get them, i.e. it's not proven to be
the only way to get these properties I guess?
Well, you could calculate the Schwartz set and then
eliminate all those candidates who are not in the
Schwartz set and then apply the Schulze method with
"pairwise opposition" to the remaining candidates.
But this would violate monotonicity because it could
happen that, by ranking the candidate A higher, some
other candidate B, who was in the strongest path from
candidate A to some other candidate C, is kicked out
of the Schwartz set.

You could use the Schulze method with "pairwise
opposition" to calculate a complete ranking of all
candidates and then declare the highest ranked
candidate elected who is in the Schwartz set.
This would satisfy monotonicity, but violate
independence of Smith-dominated alternatives.

Markus Schulze

----
Election-Methods mailing list - see http://electorama.com/em for list info
Marijn Stollenga
2015-10-05 09:38:01 UTC
Permalink
Thanks for all the suggestions. I'll briefly describe my method to make
my goal clear:

I want to avoid aggregating all votes in a tally, because I think that
loses information. Specifically, I would like a method that can find a
representative ranking. I.e. if I want the top 10 songs, it should
reflect the preferences of everyone, but not only contain electronic
music because a majority likes that.
When I you do the simple Schulze ranking (not STV) I find it
over-represents certain groups because they essentially can vote more
than once.
I think once their preference is (partially) included their voting
strength should lessen, but with a tally their vote can not be removed
(reduced) since it's all agglomerated.

My idea is to combine Quadratic Voting with ranking. The setup is this:
- Everyone has a voting budget of 1.0
- They spread their budget over their preferences: So if you have A > B
C you spread your budget over three preferences A > B, B > C and A >
C. With quadratic voting this means spending .333 on each preference,
each gets a voting strength of sqrt(.333)
- All votes are averaged.
- Everyone has a policy, which is to have an equal avg. voting strength
for their preference, and taking the resulting average into account,
they adjust their votes (using a simple gradient step).
- This is repeated until convergence.

The result is a preference matrix, which has to be turned into a
ranking. I think this is possible by eliminating the weakest preference,
and re-vote and rebalance, until a ranking is obtained. But it is not
clear that this works, it could result in a broken graph, so I'm not
sure about what to do there.

The advantage would be that no structure is lost by tallying. It also
avoids the problem of Quadratic Voting where it assumes people have an
adequate estimate of what others will vote (unrealistic in my opinion),
instead the policy is enacted by the algorithm and the user just
presents a ranking.

I'm not sure if the 'averaging policy' is the best approach, maybe there
are other policies that are more fair. Also, instead of voting on
preferences, the votes can be done directly on candidates, but it is
unclear to me how to take ranking preferences into account there.

Any thoughts?

Marijn Stollenga
Hallo,
Post by Marijn Stollenga
Thank you for the reply. So it seems pretty essential
to get these nice properties. I wonder if there are
other ways to get them, i.e. it's not proven to be
the only way to get these properties I guess?
Well, you could calculate the Schwartz set and then
eliminate all those candidates who are not in the
Schwartz set and then apply the Schulze method with
"pairwise opposition" to the remaining candidates.
But this would violate monotonicity because it could
happen that, by ranking the candidate A higher, some
other candidate B, who was in the strongest path from
candidate A to some other candidate C, is kicked out
of the Schwartz set.
You could use the Schulze method with "pairwise
opposition" to calculate a complete ranking of all
candidates and then declare the highest ranked
candidate elected who is in the Schwartz set.
This would satisfy monotonicity, but violate
independence of Smith-dominated alternatives.
Markus Schulze
----
Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info
Toby Pereira
2015-10-05 21:52:52 UTC
Permalink
Couldn't you just use a proportional method that elects sequentially? That sounds like the sort of thing you're after.
 
From: Marijn Stollenga <***@gmail.com>
To: election-***@lists.electorama.com
Sent: Monday, 5 October 2015, 10:38
Subject: Re: [EM] Voting Benchmark

Thanks for all the suggestions. I'll briefly describe my method to make
my goal clear:

I want to avoid aggregating all votes in a tally, because I think that
loses information. Specifically, I would like a method that can find a
representative ranking. I.e. if I want the top 10 songs, it should
reflect the preferences of everyone, but not only contain electronic
music because a majority likes that.
When I you do the simple Schulze ranking (not STV) I find it
over-represents certain groups because they essentially can vote more
than once.
I think once their preference is (partially) included their voting
strength should lessen, but with a tally their vote can not be removed
(reduced) since it's all agglomerated.
Marijn Stollenga
2015-10-06 13:40:33 UTC
Permalink
Hmm, how do you envision that? You start by selecting the strongest one
and fill a list like that?
How would you prevent people from reusing their voting budget in that case?

Marijn
Post by Toby Pereira
Couldn't you just use a proportional method that elects sequentially?
That sounds like the sort of thing you're after.
------------------------------------------------------------------------
*Sent:* Monday, 5 October 2015, 10:38
*Subject:* Re: [EM] Voting Benchmark
Thanks for all the suggestions. I'll briefly describe my method to make
I want to avoid aggregating all votes in a tally, because I think that
loses information. Specifically, I would like a method that can find a
representative ranking. I.e. if I want the top 10 songs, it should
reflect the preferences of everyone, but not only contain electronic
music because a majority likes that.
When I you do the simple Schulze ranking (not STV) I find it
over-represents certain groups because they essentially can vote more
than once.
I think once their preference is (partially) included their voting
strength should lessen, but with a tally their vote can not be removed
(reduced) since it's all agglomerated.
Kevin Venzke
2015-10-06 13:58:50 UTC
Permalink
As you say, "once their preference is (partially) included their voting strength should lessen." Like (multi-seat) STV.

Kevin

De : Marijn Stollenga <***@gmail.com>
À : Toby Pereira <***@yahoo.co.uk>; "election-***@lists.electorama.com" <election-***@lists.electorama.com>
Envoyé le : Mardi 6 octobre 2015 8h40
Objet : Re: [EM] Voting Benchmark

Hmm, how do you envision that? You start by selecting the strongest one and fill a list like that?
How would you prevent people from reusing their voting budget in that case?

Marijn

On 05/10/15 23:52, Toby Pereira wrote:



Couldn't you just use a proportional method that elects sequentially? That sounds like the sort of thing you're after.
 
From: Marijn Stollenga <***@gmail.com>
To: election-***@lists.electorama.com
Sent: Monday, 5 October 2015, 10:38
Subject: Re: [EM] Voting Benchmark

Thanks for all the suggestions. I'll briefly describe my method to make
my goal clear:

I want to avoid aggregating all votes in a tally, because I think that
loses information. Specifically, I would like a method that can find a
representative ranking. I.e. if I want the top 10 songs, it should
reflect the preferences of everyone, but not only contain electronic
music because a majority likes that.
When I you do the simple Schulze ranking (not STV) I find it
over-represents certain groups because they essentially can vote more
than once.
I think once their preference is (partially) included their voting
strength should lessen, but with a tally their vote can not be removed
(reduced) since it's all agglomerated.






----
Election-Methods mailing list - see http://electorama.com/em for list info
Kristofer Munsterhjelm
2015-10-09 10:44:22 UTC
Permalink
Post by Marijn Stollenga
Thanks for all the suggestions. I'll briefly describe my method to make
I want to avoid aggregating all votes in a tally, because I think that
loses information. Specifically, I would like a method that can find a
representative ranking. I.e. if I want the top 10 songs, it should
reflect the preferences of everyone, but not only contain electronic
music because a majority likes that.
When I you do the simple Schulze ranking (not STV) I find it
over-represents certain groups because they essentially can vote more
than once.
I think once their preference is (partially) included their voting
strength should lessen, but with a tally their vote can not be removed
(reduced) since it's all agglomerated.
Schulze, like other single-winner Condorcet methods, is intended for
determining a best single choice given the preferences of the
electorate. This means that if a majority all place the candidates in a
particular preference order, then that order will show up as the social
order. Clearly, that's not a good outcome if you want proportional
representation.

For that, you could use STV or Schulze STV. Or, if you have continuous
ratings (like it seems you have), I would suggest Monroe's method:

- Let each ballot be fractionally or fully assignable to a candidate.
When the ballot is assigned to a candidate, that candidate gets a number
of points equal to his rating on the ballot.
- Let the system assign ballots to candidates so that the sum of scores
is maximized, subject to that each candidate either gets zero ballots or
v/s ballots, where v is the number of voters and s is the number of seats.

For small elections, this can be solved by integer programming. For
larger elections, approximations exist: see
http://arxiv.org/pdf/1301.6400.pdf for example.

I would prefer no quadratic constraint, but it should be relatively easy
to fit it to Monroe if you want it. When the voter submits his (rated)
ballot, just check that the sum of the squares of the ratings is less
than or equal to his budget.

Of course, that suggests a DSV approach where the system rescales the
ratings so that the voters don't waste budget points on candidates they
can't get elected anyway. Doing that might be trickier; you could
probably make a quadratically constrained programming version of
Monroe's method to handle it, but finding a PTAS for that is... well,
harder.
Post by Marijn Stollenga
- Everyone has a voting budget of 1.0
- They spread their budget over their preferences: So if you have A > B
C you spread your budget over three preferences A > B, B > C and A >
C. With quadratic voting this means spending .333 on each preference,
each gets a voting strength of sqrt(.333)
- All votes are averaged.
- Everyone has a policy, which is to have an equal avg. voting strength
for their preference, and taking the resulting average into account,
they adjust their votes (using a simple gradient step).
- This is repeated until convergence.
The result is a preference matrix, which has to be turned into a
ranking. I think this is possible by eliminating the weakest preference,
and re-vote and rebalance, until a ranking is obtained. But it is not
clear that this works, it could result in a broken graph, so I'm not
sure about what to do there.
What do the numbers in the matrix denote?
Post by Marijn Stollenga
The advantage would be that no structure is lost by tallying. It also
avoids the problem of Quadratic Voting where it assumes people have an
adequate estimate of what others will vote (unrealistic in my opinion),
instead the policy is enacted by the algorithm and the user just
presents a ranking.
I'm not sure if the 'averaging policy' is the best approach, maybe there
are other policies that are more fair. Also, instead of voting on
preferences, the votes can be done directly on candidates, but it is
unclear to me how to take ranking preferences into account there.
Any thoughts?
Marijn Stollenga
----
Election-Methods mailing list - see http://electorama.com/em for list info
Continue reading on narkive:
Loading...