[EM] Voting Benchmark

[Kristofer Munsterhjelm]

On 10/05/2015 11:38 AM, Marijn Stollenga wrote:
> 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.

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.

> 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.

What do the numbers in the matrix denote?

> 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