Instant Runoff Voting and How Safe Movies Win

[Buzz Bloom]

The theorem applies to the case of finding a single winner.

Hi mfb:

I am confused about this quote above, and I hope you can clarify it for me.

As I understand Axiom 1 it says that there must be a match between the final ordering of preferences among any sub-collections of candidates for which all of the ballots indicate the same ordering of this sub-collection. Is this correct? If so, how does this axiom apply to choosing a single winner who has among all the ballots an indication that this winner has at least 50% of all the voters indicating they find the winner acceptable? If the axiom does not apply, then how does the theorem prove without this axiom that this objective is impossible?

I confess I do not understand what "If every voter's preference between X and Y remains unchanged," means. In order to understand this I think I need to understand what it means for a voter to change one or more of his/her preferences. Is this intended to mean a hypothetical change? I just don't get it.

In Tao's presentation of Arrow's theorem, there is the following Axiom:

(Independence of a third alternative) The relative ranking of X and Y is independent of the voters preferences for a third candidate Z.​

Is this intended to mean the same thing as Axiom 2? If so, then perhaps your example shows this is not guaranteed even if Axiom 1 is removed. What do you think about this?

I would also much appreciate your giving me some advice about the Monte-Carlo trials I am working on. I am making progress and nearing a point when I expect to be able to (under some assumptions about the distribution of random numbers) estimate the probability that an outcome like the one in your example would occur. If I understand correctly about the rules of the PF, I am not allowed to discuss the result of this personal project in a thread. However, would it be OK for me to discuss this in an inbox conversation? Would you be interested?

Regards,
Buzz

 

[mfb]

I confess I do not understand what "If every voter's preference between X and Y remains unchanged," means. In order to understand this I think I need to understand what it means for a voter to change one or more of his/her preferences. Is this intended to mean a hypothetical change? I just don't get it.

It is a hypothetical change (we require that it doesn't happen: If you prefer X over Y, then you should do this no matter which other candidates exist).

It doesn't matter if you look at a single winner or a full ranking. If we remove the winner, the group's preference between the second and third (and second and fourth, ...) should not change. If you could construct a voting system that can determine a winner while keeping the other conditions, you could use the same system to create a full ranking by removing the winners step by step.

Is this intended to mean the same thing as Axiom 2?

Yes.

I would also much appreciate your giving me some advice about the Monte-Carlo trials I am working on. I am making progress and nearing a point when I expect to be able to (under some assumptions about the distribution of random numbers) estimate the probability that an outcome like the one in your example would occur. If I understand correctly about the rules of the PF, I am not allowed to discuss the result of this personal project in a thread. However, would it be OK for me to discuss this in an inbox conversation? Would you be interested?

Should be fine here. I wonder how you choose voter preferences.

 

[Buzz Bloom]

The current version of my IRV Monte-Carlo tool is a spreadsheet which calculates results for just one trial, and it is limited to one particuar set of assumptions (see below). I next plan to extend it to simultaneous run a large number of trials. For the present I hit F9 to run a new trial and manually keep track of the results.

The assumptions are:
1. There are three candidates, A, B, and C.
2. Each ballot selects a 1st choice and optionally also a 2nd choice.
3. The candidates have an ordering with respect to politics, for example: A=Liberal, B = Moderate, C=Conservative.
Therefore a voter's 2nd choice will never be C if the first choice is A, and vice versa. This allows for 7 ballot possibilities: A, A>B, B, B>A, B>C, C, C>B.
4. Seven random numbers are generated from a flat distribution [ =rand() ]: T, U, V, W, X, Y, Z. The fraction of ballots for each of the 7 ballot possibilities are calculated as follows:

P(A) = (T/(T+U+V) ) * W
P(A>B) = (T/(T+U+V) ) * (1-W)
P(B) = (U/(T+U+V) ) * X
P(B>A) = (U/(T+U+V) ) * (1-X) * Y
P(B>C) = (U/(T+U+V) ) * (1-X) * (1-Y)
P(C) = (V/(T+U+V) ) * Z
P(C>B) = (V/(T+U+V) ) * (1-Z)​

Note that the sum of these seven probabilities is 1.
5. The "acceptability" E for each candidate is calculated as follows:

E(A) = P(A) + P(A>B) + P(B>A)
E(B) = P(B) + P(B>A) + P(B>C) + P(A>B) + P(C>B)
E(C) = P(C) + P(C>B) + P(B >C)​

6. If the “acceptability” for a candidate is not greater than 50%, then that candidate is removed from consideration.
Note that it is possible for all three candidates to be removed for this reason. At the present time I have no follow-up for choosing a winner if this happens. Early manual trials show that this occurs very roughly about 2% of the time. These results also show that at least one candidate is always eliminated for this reason. (I think I might be able to prove this as a theorem, but my proving skills are much diminished from what they were when I was much younger.) This result makes it unnecessary to eliminate one candidate of three for having the least number of first round votes.
7. It there is only one “acceptable” candidate, then that candidate is the winner. If there are two “acceptable” candidates, the final count of votes is made. This adds the ballots which had the eliminated candidate as 1st choice to the 2nd choice of these ballots. Then the candidate with the resulting greater number of votes is the winner.

The following are some early results based on 120 trials:

A: 28, B: 75, C: 15, NONE: 2.​

Since A and C are symmetrical, it is reasonable to adjust for this as follows

A: 21.5, B: 75, C: 21.5, NONE : 2.​

Some thoughts:
The very high frequency for B is unexpected and suggests that the assumptions are biased away from reality. Perhaps the flat distribution for W, X, and Z, the probabilities for having a 2nd choice, should be adjusted. I have in mind trying a triangular distribution and possibly a mean other than 50%. However, I intend to postpone these changes until I add the feature for running a large number of trials simultaneously.

 

[StoneTemplePython]

The current version of my IRV Monte-Carlo tool is a spreadsheet which calculates results for just one trial, and it is limited to one particuar set of assumptions (see below). I next plan to extend it to simultaneous run a large number of trials. For the present I hit F9 to run a new trial and manually keep track of the results.

1.) I think a couple of us on this thread were hoping you were going to run the simulation in Julia...

2.) If you do choose to stick with spreadsheets, I'm inferring Excel. If so, you may consider using the free module "PopTools" so at a minimum you don't need to keep manually pressing F9. http://www.poptools.org/

 

[Buzz Bloom]

If you do choose to stick with spreadsheets, I'm inferring Excel.

Hi Stone:

I am using LibreOffice Calc. This is more-or-less compatible with Excel. It can input an Excel spreadsheet, and also convert its format to an Excel format. These conversions more-or-less work, although here are a few incompatibilities.

Regards,
Buzz

 

[andrewkirk]

I have never heard of Instant Runoff Voting. The system it describes is called, wherever I have heard it mentioned, Preferential Voting. Of course there is no right or wrong name for a concept, it's just that people from countries where the system is used, such as Australia, would not recognise this thread as talking about their system, since it uses an unfamiliar name.

Preferential Voting is set against the alternative of First Past the Post voting, which is what appears to be used in most countries. Interestingly, in the UK, when they not infrequently have widespread discontent at election results from their First Past the Post system, and public debate arises about alternative methods, Preferential Voting (referred to in this thread as IRV) is referred to as 'The Australian Method', even though there are plenty of other countries that use it.

I greatly prefer Preferential Voting to First Past the Post, because it prevents the phenomenon whereby a popular movement loses out because its vote is split between multiple candidates. Arguably, Al Gore would have easily won the 2000 presidential election if Ralph Nader hadn't stood, and thereby split the 'progressive' vote, which is a fatal outcome under First Past the Post. Again arguably, maybe Ross Perot did the same to the conservative side when he stood in 1992, leading to GHW Bush's loss.

There are a number of variants to Preferential Voting. Compulsory Preferential requires all candidates to be numbered. If any are missing, or if any number is used more than once, the vote is deemed invalid. Optional Preferential allows the voter to number any number of candidates, as long as they use the first n numbers, where n is the number of candidates they have marked. If they only mark one candidate they may use a tick or a cross rather than a '1' if they wish.

I was really interested to read in that link to Arrow's theorem about a system called Cardinality Voting, in which a voter has to give each candidate a score rather than a rank. It would generate a much richer flow of information about voter preference. Arrow did not include it in the systems he considered. I suspect the problem is it may not be very practical, and it would be easy for a vote to become hard to interpret if it was not written in a very clear hand.

 

[andrewkirk]

To expand on the fairness in voting, here's an article on redistricting:

https://priceonomics.com/algorithm-the-unfairness-of-gerrymandering/

and how it can skew elections in favor of one party over another.

I remember there was some work done on making this into a mathematical framework suitable for courts to decide if a redistricting plan would take away voting rights from some groups.

https://www.quantamagazine.org/the-mathematics-behind-gerrymandering-20170404/

I remember reading about this a little while back. The gerrymandering that is done in the US is outrageous. The trouble is that allocation of districts is done by governments, rather than by an independent commission, as is the case in many other countries.

It seems to me that a fairly simple measure of electorate 'bizarreness' is $\frac{P^2}{4\pi A}$ where $P$ is its perimeter and $A$ is its area. The $P$ is squared to make the ratio invariant under expansion - ie it depends only on shape, not size. The lowest possible measure is 1, for a circular electorate, which is why the $4\pi$ factor is in the denominator.

A redistribution should not be allowed if it increased the average Bizarreness Measure of the electorates involved.

There would be some nuances. I have yet to to decide how coastlines, rivers or mountain ranges, which make natural borders, should be allowed for, as they will tend to unavoidably increase the measure. The wiggliness of them could be ameliorated by substituting a smoothed curve for the actual border in the perimeter calc, with the smoothing method (eg a cubic spline) being prescribed in the Electoral Act. But even with smoothed boundaries, a seaside electorate is going to be pushed further away from the circular ideal than an inland one, unless the coastline is a special shape.

 

[Buzz Bloom]

I have never heard of Instant Runoff Voting.

Hi andrewkirk:
Wikipedea has a very good desciption about IRV.
https://en.wikipedia.org/wiki/Instant-runoff_voting

BTW, in the city of Cambridge, Massachusetts, a form of IRV is used to simultaneously elected multiple members for both their city council and school committee.
http://www.voterchoicema.org/history_in_mass

Regards,
Buzz

 

[mfb]

These results also show that at least one candidate is always eliminated for this reason.

As A and C are mutually exclusive, one of them has to be below 50%.

The very high frequency for B is unexpected and suggests that the assumptions are biased away from reality. Perhaps the flat distribution for W, X, and Z, the probabilities for having a 2nd choice, should be adjusted. I have in mind trying a triangular distribution and possibly a mean other than 50%. However, I intend to postpone these changes until I add the feature for running a large number of trials simultaneously.

You have an average 1/3 for B as first choice, and another 1/3 (half of the remaining 2/3) for B as second choice.

This should be possible to implement in some programming language with a few lines of code, then you can run millions of trials.

 

[Buzz Bloom]

This should be possible to implement in some programming language with a few lines of code, then you can run millions of trials.

Hi mfb:

Thank you for your suggestion.

Unfortunately I do not currently have access to any compiler for a programming language of the many that I both know and have used. I do have BASIC both for Excel 97 (on XP) and for LibreOffice (on Windows7). I have downloaded a 200 page Manual for LibraOffice BASIC, a language which has many differences from the Excel BASIC with which I am familiar. I think it will take me quite a while before I can use this effectively. I am also reluctant to use BASIC 97 on XP since I am afraid this antique environment is likely to crash at any time and nor be recoverable.

I also downloaded and installed on the XP computer the poptools software

If so, you may consider using the free module "PopTools" so at a minimum you don't need to keep manually pressing F9. http://www.poptools.org/

,
but I have not yet been able to figure out how to use this tool.

Regards,
Buzz

 

[StoneTemplePython]

Hi mfb:

Thank you for your suggestion.

Unfortunately I do not currently have access to any compiler for a programming language of the many that I both know and have used. I do have BASIC both for Excel 97 (on XP) and for LibreOffice (on Windows7). I have downloaded a 200 page Manual for LibraOffice BASIC, a language which has many differences from the Excel BASIC with which I am familiar. I think it will take me quite a while before I can use this effectively. I am also reluctant to use BASIC 97 on XP since I am afraid this antique environment is likely to crash at any time and nor be recoverable.

I also downloaded and installed on the XP computer the poptools software
,
but I have not yet been able to figure out how to use this tool.

Regards,
Buzz

I seem to think you have a CS background... using spreadsheets feels very unnatural to me here. If you know Matlab or Python, Julia should be easy to pick up. You don't even need a local install, just log in with gmail, etc. here:

http://www.juliabox.com

- - - -

I have some old MC sims in excel using Poptools that I perhaps could share. Some are convoluted though -- again a few lines of code feels very best.

 

[jedishrfu]

Get processing IDE. It can run java, python or javascript. Convert the basic over to java and run it that way.

Processing.org

Its a simple environment for newbies and casual programmers.

 

[Buzz Bloom]

I seem to think you have a CS background

Hi Stone:

I do have a CS background. I have used Java, C++, FORTRAN, and a few others I don't remember now. I think the next plausible step is for me to spend some time trying to use PopTools on XP with my spreadsheet converted to Excel 97. If I run into problems I can't solve with PopTools perhaps you will be able to advise me.

Regards,
Buzz

 

[Buzz Bloom]

Get processing IDE.

Hi jedishrfu:

I looked at https://processing.org/ , and it appears to me that the Processing tool is not the right tool for me.

Processing is a flexible software sketchbook and a language for learning how to code within the context of the visual arts.​

I appreciate your suggestion, but I am not doing visual arts.

Regards,
Buzz

 

[StoneTemplePython]

Hi Stone:

I do have a CS background. I have used Java, C++, FORTRAN, and a few others I don't remember now. I think the next plausible step is for me to spend some time trying to use PopTools on XP with my spreadsheet converted to Excel 97. If I run into problems I can't solve with PopTools perhaps you will be able to advise me.

Regards,
Buzz

First thing to check out is the "Demos" tab -- in particular the one called "Monte Carlo". There is a button on that spreadsheet to run it, but it's broken on my end... there is another way to run it that is more important (so that you can generalize to the task you want to do) -- once you have a simulation sheet up, like the "Monte Carlo" one, use the tab "Simulation tools -> Sensitivity Analysis" and run that. I find having a worked example like this is quite helpful. Good luck.

 

[jedishrfu]

Hi jedishrfu:

I looked at https://processing.org/ , and it appears to me that the Processing tool is not the right tool for me.

Processing is a flexible software sketchbook and a language for learning how to code within the context of the visual arts.​

I appreciate your suggestion, but I am not doing visual arts.

Regards,
Buzz

No, it’s more general purpose than you think. I use it as a test bed for code I’m toying with. There are libraries that come with it to do charting or you can use simple print statements to push your output to the output panel below the editor.

Another one to consider is freemat which uses Matlab like programming language and has charting capability. It’s simple to use too.

 

[Buzz Bloom]

First thing to check out is the "Demos" tab -- in particular the one called "Monte Carlo".

Hi Stone:
When I downloaded poptools325_setup.exe and executed it, the file "POPTOOLS Readme.xls" was displayed in Excel. Here is some of its content.

If you have Excel 97 you should install Microsoft Office Service Release 2b. Last time I looked (Oct 2003), it was available at:
http://office.microsoft.com/assistance/9798/sr2fact.aspx
If you can't find it there, try
http://office.microsoft.com/assistance/​

There is also a button, "Setup", on the "start" line on the bottom of the desktop. When I click on it, or right-click on it, nothing happens.

I sort of remember that I had installed Microsoft Office Service Release 2b a long time ago, but I can't figure out how to confirm this. Neither of the links in the Readme file quote above work.
I also cannot find either the "Demo" tab of or the "Simulation tools -> Sensitivity" tab in Excel.

Any suggestions?

Regards,
Buzz

 

[StoneTemplePython]

Another one to consider is freemat which uses Matlab like programming language and has charting capability. It’s simple to use too.

I was really expecting a Julia endorsement from you at some point here

Hi Stone:
When I downloaded poptools325_setup.exe and executed it, the file "POPTOOLS Readme.xls" was displayed in Excel. Here is some of its content.

If you have Excel 97 you should install Microsoft Office Service Release 2b. Last time I looked (Oct 2003), it was available at:
http://office.microsoft.com/assistance/9798/sr2fact.aspx
If you can't find it there, try
http://office.microsoft.com/assistance/​

There is also a button, "Setup", on the "start" line on the bottom of the desktop. When I click on it, or right-click on it, nothing happens.

I sort of remember that I had installed Microsoft Office Service Release 2b a long time ago, but I can't figure out how to confirm this. Neither of the links in the Readme file quote above work.
I also cannot find either the "Demo" tab of or the "Simulation tools -> Sensitivity" tab in Excel.

Any suggestions?

Regards,
Buzz

I have it on Excel 2007 / 2010 (i.e. when they made Excel look more like an Apple product), I'm afraid I have no clue about the office service releases you are running into. (I didn't know about it back when I used Excel 2003 on XP, and I kind of forgot about Excel 97!)

To be really clear: if you properly install Poptools, there should be a Poptools tab somewhere in excel (possibly under Add-ins). Then, you can find the "Demo" and "Simulation tools" tabs as sub-tabs / dropdowns 'underneath' the Poptools menu from within Excel -- they are not a subset of Poptools and not natively part of Excel.

 

[Buzz Bloom]

The following PNG files show what is availalale to me from the Addins TAB.

 

[StoneTemplePython]

sorry -- I'm just not familiar with installing Poptools under an older windows and excel environment... if you successfully install it, you will have a way of accessing it in Excel, and see the submenus /tabs nested in it and so on

 

[mfb]

Quick and dirty in python, I hope the link works.

Result of 1 million elections: [214,684, 532,961, 215,246, 37,108] for A, B, C, and no winner, respectively, with the rules from post #33.