bramcohen: Weird Elections

Bram Cohen (

bramcohen) wrote,
@ 2005-06-13 01:14:00

Weird Elections
The following is a set of votes for an election where by proportional represention if there is to be one winner then M should win, but if there are to be two winners then A and B should win, and if there are to be three winners then X, Y, and Z should win:

XAMB
XBMA
YAMB
YBMA
ZAMB
ZBMA
MAB

What this demonstrates is that any successive picking strategy which uses information about candidates already picked to affect later picked candidates must under some circumstances pick a set of winners other than the optimal one. I don't think this is actually a problem, since the oddball preferences necessary to make this matter must necessarily not fall along party lines, and I can't see any practical voting strategy which it could lead to. Successive algorithms tend to be vastly simpler and computationally tractable than the more generalized algorithms, which generally require computations to be done across all possible sets of winners. They also tend to be much easier to describe and implement.

(Post a new comment)

ciphergoth
2005-06-13 10:07 am UTC (link)

I take it by more generalized algorithms you mean algorithms like this?

I think I'd still rather pursue generalized algorithms if possible, or perhaps some sort of hybrid. The tricky thing with generalized ones is that if there are enough candidates/winners, you can't properly consider all the possible sets of winners. It's not hard to come up with heuristics for choosing sets worth considering, but for a public election you have to have very well justified heuristics that you can set out in advance and guarantee to stick to when you come to do the calculation...

(Reply to this) (Thread)

	bramcohen 2005-06-26 07:00 pm UTC (link)
	Yeah, my point is that while in principle such strange cases can happen, using successive approaches leads neither towards strategic voting nor particularly objectionable results, so the simplicity and practicality benefits of successive make it worthwile. (Reply to this) (Parent)

	bramcohen 2005-06-26 07:12 pm UTC (link)
	Does that system you link to do proportional representation? It isn't obvious to me how it would. A similar sort of system was proposed by Tidemann years ago, but it suffers from all of the obvious problems. (Reply to this) (Parent)

(Anonymous)
2005-06-13 10:15 pm UTC (link)

How bizarre.

Here is a curious electoral game which may interest you:

In this game, each voter also wants to avoid getting on the wrong side of whoever wins the vote. So, each voter has a 'safety number' S, such that they will vote for their preference if they believe that at least S people will do so. In a two way vote, the voters entire preference can be encoded in S because a 'No' preference with safety number X is the same as a 'Yes' with safety number N-X (N the number of voters). The whole game can be visualised by sorting the voters in order of safety number, then plotting safety number Vs voter index. The result is a monotonic graph. If voter index is on the X axis, we can think of a vote as a point on the x axis, dividing yes votes and no votes (without loss of generality, since voters with the same S are identical). An x-value consistent with all the voters preferences is (I think) any x-value where the graph crosses x=y from below. Obviously, there can be more than one such point!

Of course, most formal voting systems are anonymous. This game is more representative of informal decision procedures.

(Reply to this) (Thread)

	bramcohen 2005-06-26 07:02 pm UTC (link)
	If voters place a premium on going with the majority then then a whole slew of unpleasant phenomena come out. That's part of why it's a good idea to keep tallies secret until after the voting period has finished. (Reply to this) (Parent)

	Sorry! Not a comment to this.. lunaticcalm 2005-06-16 12:26 pm UTC (link)
	Hi.. I was looking for some way to get in touch with you. I was unable to find a contact mail ID or a way to leave a message in LJ. I wanted to talk to you about something. Can u ping me back? Or gimme a mail ID to respond to? (Reply to this)

small groups vs large groups

scotty777
2005-06-18 12:45 am UTC (link)

It seems to me that the strategies of small group votes, like in your example, are impossible to use in large group votes. In a small group, the voter has knowledge certain that his/her vote can be made to count. In a large group, that sense of having influence is best afforded by the proportional representation system. The advantage of the sense of participation is that the voter is more likely to go along with decisions when he/she has a sense that he/she is not a meaningless entity being forced to go along. It's easier to achieve goals requireing lots of participation when everybody works together. In small groups, personalities and other characteristics of the persons involved will come to dominate the willingness to help achieve the common goal. As group size goes down then, in my view, people will look less and less at the voting system when they evaluate the fairness of the group goal.

(Reply to this) (Thread)

	Re: small groups vs large groups bramcohen 2005-06-26 07:03 pm UTC (link)
	On the contrary, strategic voting is much more common in huge elections where there are professional party representatives whose job it is to sit around and figure out how to game stuff. (Reply to this) (Parent)(Thread)

small example groups not so useful

scotty777
2005-06-27 01:55 am UTC (link)

Right Bram, in your reply you pointed out: strategic voting is much more common in huge elections

Yes, and Bram, you make my point for me. Large vote situations are dominated by strategy. On the other hand, we have very small groups such as the seven person example which is cited in the original post.

In small groups, personalities and other characteristics of the persons involved will come to dominate the willingness to help achieve the common goal. As group size goes down then, in my view, people will look less and less at the voting system when they evaluate the fairness of the group goal.(from my previous post)

In some ways, as we all know, small groups are tougher to deal with. No democratic system alleviates this, since petty personal battles can easily overwhelm "actual" issues.

In small groups, personalities and other characteristics of the persons involved will come to dominate the willingness to help achieve the common goal. As group size goes down then, in my view, people will look less and less at the voting system when they evaluate the fairness of the group goal. (from my previous post)

I may be rubbing you the wrong way here. If that's so, I apologize. The point I'm trying to make may be overwhelmed my unpleasant way of writing it. That's the sort of thing that happens in small groups, by the way! Small vote groups are bad for examples, because they're unrealistic. Small groups that vote don't need systems that are "more fair". They need comity. And good humor! Cheers!

(Reply to this) (Parent)

	eharley 2005-06-21 04:02 pm UTC (link)
	Have you seen the work by Ken Arrow or Don Sari? (Reply to this) (Thread)

	alkor 2005-06-21 04:09 pm UTC (link)
	Don Sari came to talk at my college (Carleton) about the very issue of fair voting. To summarize, he claimed the only way to have a fair voting system is based upon preferences, where for N candidates the 1st choice gets N points, the second gets N - 1, and so on, until the last place candidate gets 1 point. (Reply to this) (Parent)(Thread)

	Borda Count (Anonymous) 2005-06-21 06:29 pm UTC (link)
	Borda Count voting, which is what you described, isn't the best method we have. Saari's work shows that Borda Count is significantly better than other positional voting schemes, but it falls short in other ways compared to variants of Condorcet voting. (Reply to this) (Parent)(Thread)

Re: Borda Count

eharley
2005-06-21 07:45 pm UTC (link)

Saari's proofs are also geometrical, which leave much to be desired. My friend Grant did his undergraduate thesis on coming up with an algebraic framework for positional voting schemes.

There is a pdf here

Basically, when you look at the space of outcomes of a positional vote there can be a "paradox" subspace where voter preferences aren't reflected ala Arrow's theorem. And Grant did some work to show why this happened and how big the spaces were in different voting schemes. Sadly, I don't think that he's going to continue with this work.

(Reply to this) (Parent)

	(Anonymous) 2005-06-21 08:11 pm UTC (link)
	if you do this however strategic voting is posible; in other words there is a positive incentive for people to misrepresent their preferences. There is in fact no system under which you can get them to reveal the ordering of their preferences without inducing strategic voting, this is proved in the Gibbard-Satterthwaite theorem. (Reply to this) (Parent)

Instant Runoff Voting
(Anonymous)
2005-06-21 04:14 pm UTC (link)

As an experiment I applied my personal favorite voting algorithm Instant Runoff Voting (http://www.fairvote.org/irv/?page=189) (IRV). It seems to handle this set of votes as well as possible.

Round 1: X gets 2, Y gets 2, Z gets 2, and M gets 1.

In IRV, the lowest vote getter in any round is "voted off the island", and then you recount. If a person's first choice is then missing, their 2nd choice is counted. Rinse and repeat.

In this case there are two canidates that got zero votes, so there is no clear "lowest" vote getter. It doesn't much matter if you drop one or both of them in this round, because the other will be dropped in the next count anyway. After A and B are gone, we carry on.

Penultimate Round: Same count as First Round, and so M is dropped, being the low count of 1.

Last Round: The last, fringe voter, MAB doesn't count, having selected only canidates that were eliminated, and so you end with a three-way tie, which IRV handles as well as any other system: not at all.

(Reply to this) (Thread)

Re: Instant Runoff Voting
(Anonymous)
2005-06-21 07:29 pm UTC (link)

Actually, I'd say this set of ballots is an excellent example to demonstrate what's WRONG with IRV. As Bram pointed out, if there's only one winner, then it should be M, but IRV won't pick M at all.

(Reply to this) (Parent)

Condorcet variation that may handle this
(Anonymous)
2005-06-21 08:45 pm UTC (link)

Bram, here's an approach that may do the "right" thing in all cases. I haven't fully tested it but a few minutes of playing around with a subset of the ballots makes it look like it will work.

The idea is that if you're selecting two or three candidates as winners, why not look at the race as a competition between candidate tuples? If you're selecting two winners, then consider all possible pairs of candidates as the set of candidates for a Condorcet voting system.

It's obvious that if you could ask voters to actually rank all of the n-candidate (n is the number of winners to be selected) combinations, and if they were diligent enough to actually do it, then you could simply tally the votes according to any of the systems we have, with their well-understood strengths and weaknesses.

But you can't ask voters to rank all of those n-tuples. If you can find a reasonable way, however, to deduce how the voters would rank the n-tuples based on how they ranked the individuals, then you can use a standard ranked ballot to select the best tuple. You can't do that perfectly, of course, but it seems to me that a simple Borda Count-like heuristic provides a good approximation.

With this scheme, the ballot XAMB would be transformed into (if I didn't make a mistake):

AX; MX; AM, BX; AB; BM, XY, XZ; AY, AZ; MY, MZ; BY, BZ; YZ

Comma-separated pairs are tied, semi-colons indicate a preference. I gave 5 points to X, 4 to A, 3 to M, 2 to B and 0 to Y and Z.

Looking at that list and at the original vote shows that it does seem to be a reasonable expression of that voter's preferences. Perhaps the voter would rank BM over XY and XZ, rather that placing those pairs in a three-way tie. If the voter were to assign point values and more fully express his or her preferences, then those sorts of issues could be addressed as well. But since the point values would only be used to transform the ranked individuals into ranked n-tuples, there's no advantage to be gained by "strategically" allocating your points -- except insofar as proper point allocation assures that your true preferences with respect to the ranked tuples are better expressed.

Anyway, the point is that if you can separate the issue of determining the voter's preference among the tuples from the issue of properly aggregating the voters' preferences, the problem is simpler to think about.

(Reply to this) (Thread)

Re: Condorcet variation that may handle this

bramcohen
2005-06-26 07:09 pm UTC (link)

I believe that to avoid strategic voting any pair containing X would have to be preferred to any pair not containing X in the example you gave.

Such tuple-ranking options have been investigated in the literature, they tend to not have proportional representation though (I think - my intuition may be exactly wrong on that one) and they're very nasty computationally, which makes them unappealing from a practical standpoint.

(Reply to this) (Parent)(Thread)

	Re: Condorcet variation that may handle this (Anonymous) 2005-06-27 05:15 pm UTC (link)
	http://www5.cs.cornell.edu/~andru/civs/proportional.html describes an algorithm to use with the condorcet method of election for proportional representation. Might be worth a look. (Reply to this) (Parent)

Condorcet voting picks M
(Anonymous)
2005-06-21 09:27 pm UTC (link)

If you go to Eric Gorr's Condorcet vote calculator here:
http://condorcet.ericgorr.net/

Then the following is the input you feed it to match Bram's hypothetical vote scenario:
X>A>M>B>Y=Z
X>B>M>A>Y=Z
Y>A>M>B>X=Z
Y>B>M>A>X=Z
Z>A>M>B>X=Y
Z>B>M>A>X=Y
M>A>B>X=Y=Z

It will show you the voting results (including intermediate results, if you ask it) of a few variants of Condorcet Voting and a few variants of Instant Runoff Voting.

For those that aren't familiar with Condorcet voting, try the Wikipedia page about it:
http://en.wikipedia.org/wiki/Condorcet_method

And here's an interesting page that shows some of the mathematical vote evaluation criteria, and how various vote system stack up:
http://electionmethods.org/evaluation.htm

For those that have ever supported Instant Runoff Voting, I highly encourage you to read these links. You probably won't support Instant Runoff Voting after you read more about voting systems. Other systems work far, far better.

(Reply to this) (Thread)

	Question _scorp 2005-06-22 08:05 am UTC (link)
	Better as in less injustice (dissatisfaction) or more prone to fraud (manipulation) ? (Reply to this) (Parent)(Thread)

	Re: Question bramcohen 2005-06-26 07:11 pm UTC (link)
	Generally when evaluating voting the main criterion is resistance to manipulation, because that causes huge problems in practice, while in the absence of any gaming the different systems tend to all give the same answers, or close enough to not be seriously problematic. (Reply to this) (Parent)(Thread)

	Re: Question _scorp 2005-06-27 05:37 pm UTC (link)
	well - even if you do not have "gamers" the classical voting with more than two candidates has its problems, as Borda pointed out ... (Reply to this) (Parent)

	(Anonymous) 2005-07-02 10:08 pm UTC (link)
	I believe this is the 'Borda Count' method...check out instant run-off voting...many in the 'left' community feel its the next best thing to allow for a 3rd party to have a say in local elections (Reply to this)

	range voting wdsmith 2006-07-09 02:32 pm UTC (link)
	For electing one winner, I recommend "range voting." See the Center for Range Voting web site http://www.RangeVoting.org . That site also has some recommendations for electing more than one winner (and discussion...) in these subpages: http://www.RangeVoting.org/PropRep.html http://www.RangeVoting.org/AdvocatedSystems.html Warren D Smith (CRV founder) (Reply to this)

Username:		Create an Account Forgot your login? Login w/ OpenID
Password:
	Remember Me
	English • Español • Deutsch • Русский…

About

Help

Get Involved

Legal

Store

LJ Labs