<?xml version="1.0" encoding="ISO-8859-1"?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
<title></title>
<style type="text/css">
<!--
body{margin-left:10px;margin-right:10px;margin-top:10px;margin-bottom:10px;}
-->
</style>
</head>
<body marginleft="10" marginright="10" margintop="10" marginbottom="10">
<div align="left" style="text-align:left;"><font face="Arial" size="+0" color="#000000" style="font-family:Arial;font-size:10pt;color:#000000;"><b>Chris Benham <<a href="mailto:cbenhamau@yahoo.com.au">cbenhamau@yahoo.com.au</a>> writes:</b></font></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">In Ireland it is used to elect the President. The Irish lower house uses multi-winner</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">STV. UK mayoral elections mostly use the "Supplementary Vote". From Wikipedia:</font></span></div>
<br />
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">Ah, my mistake. Thank you for the corrections. I think that I just tried to copy that information from the wikipedia page on IRV, but perhaps I did a sloppy job (or is that page wrong?).</font></div>
<br />
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">Of course it is equivalent to IRV when there are three candidates, but is otherwise awful.</font></span></div>
<br />
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">Okay; I can point out that these elections use supplementary vote, which can be viewed as a variant on IRV.</font></div>
<br />
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">Regarding MinMax in your paper you wrote:</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">"The winner is the candidate whose worst pairwise loss (if any) is least bad;..."</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">You don't define here how you measure "least bad". Later you give this:</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">"Minimax</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:12pt;color:#000000;"><i>To calculate the winner</i></font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">1. Form a pairwise matrix. Form the </font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:12pt;color:#000000;"><i>N </i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">by 1 vector </font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-BoldItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-BoldItalicMT;font-size:12pt;color:#000000;"><i><b>MAXBEAT</b></i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000"
style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">, where </font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:12pt;color:#000000;"><i>MAXBEAT</i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:10pt;color:#000000;"><i>x </i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">is the</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">greatest number of votes against x in any pairwise contest, i.e. </font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:12pt;color:#000000;"><i>MAXBEAT</i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:10pt;color:#000000;"><i>x</i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">=max(</font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000"
style="font-family:TimesNewRomanPS-ItalicMT;font-size:12pt;color:#000000;"><i>PM</i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:10pt;color:#000000;">:,</font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:10pt;color:#000000;"><i>x</i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">). The</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">candidate with the smallest value in the </font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPS-ItalicMT" size="+0" color="#000000" style="font-family:TimesNewRomanPS-ItalicMT;font-size:12pt;color:#000000;"><i>MAXBEAT </i></font></span><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">vector is the winner."</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;"> </font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">This make no reference to "pairwise losses", so isn't it "MinMax(Pairwise Opposition)" that</font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" color="#000000" style="font-family:TimesNewRomanPSMT;font-size:12pt;color:#000000;">*fails* the Condorcet criterion?</font></span></div>
<div align="left" style="text-align:left;"><a href="http://nodesiege.tripod.com/elections/#methmmpo"><span style="background-color:#d0d0d0;"><font face="TimesNewRomanPSMT" size="+0" style="font-family:TimesNewRomanPSMT;font-size:12pt;">http://nodesiege.tripod.com/elections/#methmmpo</font></span></a></div>
<br />
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">These seem like subtle distinctions, as my program doesn't generate any incomplete ballots or preferences. I'm a little rusty on this, but I do think I see how this algorithm could fail Condorcet given incomplete ballots. I seem to remember thinking, while I wrote the minimax strategy program, that allowing incomplete ballots wouldn't make strategy any harder or easier, but that was about a year ago, and I don't really remember my full logic. But yes, modifying the programs so that they can handle incomplete preferences would be a logical step.</font></div>
<br />
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">Another thing I really would like to do is write programs for beatpath and ranked pairs, but I haven't got around to that yet. The minimax strategy program was the hardest one for me to write, and the one in which the possibility of an error is most real (if you see how I describe the program in the paper, it is rather convoluted). I think that I can eventually write programs for beatpath and ranked pairs, but I expect it to be tricky, so I've put it off while I work on other (unrelated) projects. Cardinal pairwise also seems to be extremely hard to analyze in this way; I can write a program that approximates its vulnerability, but getting it dead on is very challenging. Multiple-winner STV is another hard one; I think I know how the program should work in principle, but writing it may be a bit of a headache.
</font></div>
<br />
<div align="left" style="text-align:left;"><font face="Arial" size="+0" color="#000000" style="font-family:Arial;font-size:10pt;color:#000000;"><b>Kristofer Munsterhjelm <<a href="mailto:km-elmet@broadpark.no">km-elmet@broadpark.no</a>> writes:</b></font></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="Gill Sans" size="+1" color="#000000" style="font-family:Gill Sans;font-size:14pt;color:#000000;">That's interesting, because optimal strategizing in IRV has been found </font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="Gill Sans" size="+1" color="#000000" style="font-family:Gill Sans;font-size:14pt;color:#000000;">to be NP-complete ("The Computational Difficulty of Manipulating an </font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="Gill Sans" size="+1" color="#000000" style="font-family:Gill Sans;font-size:14pt;color:#000000;">Election"). So, in a sense, your simulations reflect this (and that IRV </font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="Gill Sans" size="+1" color="#000000" style="font-family:Gill Sans;font-size:14pt;color:#000000;">strategy is closer to the difficult part/phase transition of the </font></span></div>
<div align="left" style="text-align:left;"><span style="background-color:#d0d0d0;"><font face="Gill Sans" size="+1" color="#000000" style="font-family:Gill Sans;font-size:14pt;color:#000000;">NP-complete domain; that is, it's not just the easy instances).</font></span></div>
<br />
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">Thank you for the reference; this looks like an interesting paper. </font></div>
<br />
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">my best,</font></div>
<div align="left" style="text-align:left;"><font face="Times New Roman" size="+1" color="#000000" style="font-family:Times New Roman;font-size:14pt;color:#000000;">James</font></div>
<br />
</body>
</html>