Serial Approval Vote Election



  • If the particularities of Javascript (JS) are tripping you up for a time, you could inform us about the tallying algorithm by writing it in English-language pseudocode. Or maybe some of us will feel able to grock your Python if you post it.

    Here's an example of English-language pseudocode for first-past-the-post tallying:

    For each candidate, initialize an accumulator to zero. Examine all the ballots. For each ballot, bump up by one the accumulator associated to the candidate named on the ballot. After the scan of the ballots, the candidate whose total in her associated accumulator is greater than the total of each of the other candidates, wins.



  • @Jack-Waugh, @multi_system_fan, here is the text of a JavaScript file with the functions to implement the SAVE focus selection routines. My problems with JavaScript are due more to being highly distractable in addition to the differences between expository code (what this should be), production code (what I would write for an actual system implementing SAVE with users), and exploratory code (what I wrote while developing and exploring different possibilities for SAVE).

    The file is 322 lines, of which about 170 lines are comments and instructions. Please let me know if you have any questions. Thanks.

    /* JavaScript code for SAVE vote tally and Focus Selection
    
       Serial Approval Vote Election
    
       Users of this code are expected to supply a list of "alternatives" to
       "voters" in an electorate, and collect one "ballot" from each voter.
       Said ballot is a list of binary values corresponding to the items in the
       list of alternatives.
    
       This code does not deal with the alternatives list at all.  It is
       focused on the list of ballots, which is the input for each round.
       These ballots determine the entire process.
    
       Data from electorate: Just to show the structure of the data.  This
       particular election apparently starts with 3 voters and 7 alternatives.
       Note: the voters care about the details of the alternatives, but the
       SAVE algorithm only cares about the alternative indices.
    
          alternatives = new Array(7);
          var votera = [0, 1, 1, 0, 0, 0, 1];
          var voterb = [0, 0, 1, 0, 1, 0, 0];
          var voterc = [0, 1, 1, 0, 1, 1, 0];
          ballots = [votera, voterb, voterc];
    
       Running a SAVE procedure:
    
       First, voters are presented with the initial list of alternatives, and
       cast approval votes for some subset of those alternatives.  Those
       ballots are collected into the ballots array.
    
       These operations are then called:
    
         Focus[currentRound] = -1;
         ballotCount[currentRound] = ballots.length;
         historyRecord[currentRound] = saveTally(ballots);
         Focus.push(firstFocusSelection(historyRecord[0]));
    
       This sets up some records for the rest of the run, determines the winner
       of the initial round, and sets that winner to be the focus alternative
       for the next focused approval vote round.
    
       The ballots for subsequent rounds will still have binary responses for
       each alternative, but the questions will be different.  One of the
       alternatives is presented as the focus alternative (or just the focus).
       A vote for the focus is a vote to terminate the loop with the focus as
       the final winner.  A vote for a non-focus alternative indicates the
       voter prefers that alternative over the current focus.
    
       The SAVE loop has the following steps:
           while (true) {
             currentRound = currentRound + 1;
    
         Voters given: alternatives, Focus[currentRound], then
         Election process collects ballots for currentRound.
         The ballot processsing then does:
    
             ballotCount[currentRound] = ballots.length;
             historyRecord[currentRound] = saveTally(ballots);
             if (loopTerminationTest()) {
               // Loop terminated.  Move on to Mandate round.
               break; };
             selectNextFocus();
    
         Check if new alternatives are allowed for next round by doing:
             if (allowNewAlternatives()) {
               // allow voters to propose new alternatives.
             };
           };  // end of while
    
       After loop termination, the last focus alternative has been determined
       to be the overall winner.  The last step is to run a final round under
       AV rules to explicitly measure the mandates of the overall winner and
       all other alternatives.
     */
    
    /*
       Global variables for VT-SAVE-tally
     */
    
    var alternatives = new Array(0); // List of active alternatives
    var ballots = new Array(0);      // Input: cast ballots in a round
    var currentRound = 0;           // The current round.
    // History records, with index corresponding to round.
    var Focus = new Array(1);       // focus alternative index, by round
    var ballotCount = new Array(1); // total ballots, by round
    var historyRecord = new Array(1); // vote tally list, by round
    // Variables shared between functions
    var historyRounds;              // list of rounds in the history period
    var tieCnt = 0;                 // number of votes for a tie
    var maxVotes = 0;               // maximum vote count seen
    var focusOptions = new Array(0); // idx list of potential Focus alternatives
    
    /* Functions:
    
       Total all ballots for a round.
    
       Votes for alternatives are simply added, including the explicit votes
       for the focus alternative.  (AV tally).
     */
    function saveTally() {
        var altCnt = ballots[0].length;
        var voteTotals = new Array(0);
        for (var i=0; i < altCnt; i++) {
            voteTotals.push(0);}
        var voterCnt = ballots.length;
        for (var ballotIdx = 0; ballotIdx < voterCnt;
             ballotIdx ++) {
            for (var altIdx = 0; altIdx < altCnt;
                 altIdx++) {
                if (ballots[ballotIdx][altIdx] != 0) {
                    voteTotals[altIdx]++ ; }; }; };
        return voteTotals; };
    
    /* Select the first Focus alternative
      
       The first focus is simply the AV winner of the first round, which has no
       focus.
     */
    function firstFocusSelection() {
        var tally = historyRecord[0];   // First round tally
        var maxVotesSeen = -1;
        var focusIndex = -1;
        var altcount = tally.length;
        for (var idx = 0; idx < altcount; idx += 1) {
            if (maxVotesSeen < tally[idx]) {
                maxVotesSeen = tally[idx];
                focusIndex = idx; }; };
        return focusIndex; };
    
    /* Test for loop termination
      
       Loop termination happens when the focus alternative has a strict
       majority and more votes than any other alternative.
     */
    function loopTerminationTest() {
        var ballotCnt = ballotCount[currentRound];
        var focusIdx = Focus[currentRound];
        var tally = historyRecord[currentRound];
        var allDone = true;
        var focusVotes = tally[focusIdx];
        if (focusVotes <= ballotCnt / 2.0) {
            allDone = false; }
        else {
            for (var idx = 0; idx < tally.length; idx++) {
                if (idx != focusIdx && tally[idx] >= focusVotes) {
                        allDone = false; }; }; };
        return allDone; };
    
    /* Select Moderate Winner for next focus:
    
       The moderate winner is the alternative that beat the focus by the most
       moderate amount.  This function determines that alternative and sets it
       to be the focus for the next round.  This routine will never identify a
       tied alternative as the moderate winner.
     */
    
    function myAbs (num) {
        if (num >= 0.0) {
            return num; }
        else {
            return 0.0 - num }; };
    
    function selectModerateWinner() {
        var desiredVotes = (maxVotes + tieCnt) / 2.0;
        var bestScore = null;
        var bestVotes = 0;
        var bestIdx = -1;
        var oScore = 0;
        var oVotes = 0;
        for (var oIdx=0; oIdx < focusOptions.length; oIdx++) {
            aIdx = focusOptions[oIdx];
            oVotes = historyRecord[currentRound][aIdx];
            oScore = myAbs(oVotes - desiredVotes);
            if (bestScore == null ||
                oScore < bestScore ||
                (oScore == bestScore && oVotes > bestVotes)) {
                bestScore = oScore;
                bestVotes = oVotes;
                bestIdx = aIdx; }; };
        Focus[currentRound + 1] = bestIdx; };
    
    /* Determine and return the history score for an alternative:
      
       This history score has four components.  The first three are the
       wins+ties count, the vote deficit, and the wins count.  The fourth
       component is the number of rounds the alternative was active during the
       history period, and is used to make sure new alternatives do not get a
       benefit of no vote deficit by simply not being active during the full
       history period.
      
       Prior focuses count has having tied themselves.
     */
    function returnHistoryScoreList (idx) {
        var historyScore = new Array(0, 0.0, 0, 0);
        // historyRounds is a list of rounds
        // each pass should set tally to a list of ballot totals
        // idx (an arg) is the index of an alternative
        // idxVotes should be the votes received by the idx alternative in the tally
        for (var hIdx = 0; hIdx < historyRounds.length; hIdx++) {
            var rIdx = historyRounds[hIdx];
            var tally = historyRecord[rIdx];
            if (tally[idx] ==  undefined) {
                continue; };
            var idxVotes = tally[idx];
            if (idx == Focus[rIdx]) {
                historyScore[0]++
                historyScore[3]++
                continue; };
            tieCnt = ballotCount[rIdx] / 2.0;
            if (idxVotes >= tieCnt) {
                historyScore[0]++; };
            if (idxVotes - tieCnt < 0) {
                historyScore[1] = historyScore[1] + idxVotes - tieCnt; };
            if (idxVotes > tieCnt) {
                historyScore[2]++; };
            historyScore[3]++; };
        return historyScore; };
    
    /* Select the alternative with the best history score for the next focus:
      
       The history score measures an alternatives performance against the
       focuses from the recent history period.  This period is the longest
       continuous series of rounds including the most recent round in which no
       focus alternatives are duplicated.
      
       The history score for an alternative that beats or ties the current
       focus tracks the number of wins, ties, and losing margins during recent
       history.  When comparing two history scores, the most important number
       is the wins+ties count, followed by the vote deficit, then the pure wins
       count.  When two alternatives have been active for a different number of
       rounds during the history period, only the wins+ties count is considered.
      
       All comparisons are done in the order of the alternatives list.  Later
       alternatives must be strictly better to replace an earlier alternative.
      
       Note: this code is run after selectModerateWinner has already set an
       alternative for the next focus.  This code starts with the history score
       for the moderate winner and will only displace the MW if there is an
       alternative with a strictly better history score.
     */
    function selectHistoryScoreWinner() {
        var duplicateCheck = new Object();
        historyRounds = new Array(0);
        for (var rIdx = currentRound; rIdx > 0; rIdx--) {
            var aIdx = Focus[rIdx];
            if (duplicateCheck["a" + aIdx] == undefined) {
                duplicateCheck["a" + aIdx] = 1;
                historyRounds.push(rIdx); }
            else { break; }; };
        // historyRounds is now a list of the round indices for the
        // history period.  Look to replace the moderate Winner.
        // MW is checked against itself but no change occurs.
        var bestIdx = Focus[currentRound + 1];
        var bestHS = returnHistoryScoreList(bestIdx);
        for (var foIdx = 0 ; foIdx < focusOptions.length ; foIdx++) {
            var foHS = returnHistoryScoreList(focusOptions[foIdx]);
            if (foHS[3] != bestHS[3]) {
                if (foHS[0] > bestHS[0]) {
                    bestHS = foHS;
                    bestIdx = focusOptions[foIdx]; };
                continue; };
            if (foHS[0] > bestHS[0] ||
                (foHS[0] == bestHS[0] && foHS[1] > bestHS[1]) ||
                (foHS[0] == bestHS[0] && foHS[1] == bestHS[1] &&
                 foHS[2] > bestHS[2])) {
                bestHS = foHS;
                bestIdx = focusOptions[foIdx]; }; };
        Focus[currentRound + 1] = bestIdx; };
    
    /* Select the next focus
      
       This code selects the next focus during the SAVE focused approval vote
       iteration.  There are four ways this can occur.  If the most recent
       focus is a Condorcet winner, it remains as focus for the next round.  If
       it is not a Condorcet winner, the focus MUST change.  If there is only
       one possible alternative, it is selected immediately as the next focus.
       If there are multiple options, the moderate winner alternative is
       selected first, and then possibly replaced by the alternative with the
       best history score.
      
       This code first determines the options for replacing the focus, which
       includes all alternatives that received votes from at least half the
       electorate.
     */
    function selectNextFocus () {
        var ballotCnt = ballotCount[currentRound];
        var lastFocusIdx = Focus[currentRound];
        var tally = historyRecord[currentRound];
        focusOptions = new Array(0);
        tieCnt = ballotCnt / 2.0;
        maxVotes = 0
        for (var idx = 0; idx < tally.length; idx++) {
            if (idx != lastFocusIdx && tally[idx] >= tieCnt) {
                focusOptions.push(idx);
                if (idx != lastFocusIdx && tally[idx] > maxVotes) {
                    maxVotes = tally[idx]; }; }; };
        var isCondorcetWinner = true;
        for (var idx = 0; idx < focusOptions.length; idx++) {
            if (tally[focusOptions[idx]] > tieCnt) {
                isCondorcetWinner = false; }; };
        if (isCondorcetWinner) {
            Focus[currentRound + 1] = Focus[currentRound]; }
        else if (focusOptions.length == 1) {
            Focus[currentRound + 1] = focusOptions[0]; };
        if (Focus.length == currentRound + 1) {
            selectModerateWinner();
            selectHistoryScoreWinner(); }; };
    
    /* Are new alternatives allowed this round?
      
       New alternatives are allowed to be proposed whenever the focus
       alternative is a repeat.  I.e. whenever the current focus is either a
       Condorcet winner or part of a top majority cycle.
     */
    function allowNewAlternatives() {
        var allow = false;
        for (var idx = 0; idx < currentRound + 1; idx++) {
            if (Focus[idx] == Focus[currentRound + 1]) {
                allow = true; }; };
        return allow; };
    
    // End
    
    


  • So your intent here, right, for the interpretation of this code is the reader is to imagine an interaction between the people and the state of execution of the code, where, between rounds, the people wholly rewrite the global variable ballots to reflect their votes for the new round?



  • @tec at line 290, you have

        tieCnt = ballotCnt / 2.0;
    

    Did you mean

        tieCnt = tally[lastFocusIdx];
    

    ?



  • I bring here just a partial analysis of the code for now, because I am feeling a bit fatigued, and also suspecting you may want to revise.

    At least two rounds of voting are required to elect anyone: the initial round, which has no focus, followed by at least one round based on a focus.

    The first focus is the candidate receiving the most count of approvals in the initial round (i. e., the candidate who would have won under Approval Voting).

    A focus round sums up the votes as in Approval, then applies the termination test.

    The termination test uses two branches, either of which can decide against termination (i. e., for continuation). The first branch tests whether the focus candidate has received, in the current round of voting, approvals from at least half the ballots. If not, the decision is for continuation, and there is no need to test the other branch.

    The second branch tests whether any of the non-focus alternatives has received (in the current round of voting) at least so many approvals as the focus candidate received. If so, the decision is for continuation.

    So in summary, termination happens exactly when the focus candidate has approvals from at least half the ballots and strictly more count of approvals than any other candidate. In this case, there are no more focus rounds, the election is concluded, and the focus candidate wins the election.

    I note that the decision for termination vs. continuation depends solely on the tally of approvals. No other input contributes to it.

    If the decision is for continuation, the algorithm next has to decide who shall be the focus for a subsequent round of voting (selectNextFocus). The next focus will be announced to the voters along with a decision about whether they are allowed to propose new alternatives.

    The first loop in selectNextFocus, which loop occupies lines 292 through 296, collects (as focusOptions) the candidates who received approvals from at least half the ballots and are not the previous focus. Along the way, it remembers (as maxVotes) the max number of approvals any of the focusOptions got.

    It is possible for focusOptions to be empty. In this case, maxVotes will remain at zero. It is also possible to have exactly one candidate in there, and it is also possible to have more than one, and it would be possible for every candidate in the election besides the current focus to be in there.

    Lines 297 through 302 look like this:

        var isCondorcetWinner = true;
        for (var idx = 0; idx < focusOptions.length; idx++) {
            if (tally[focusOptions[idx]] > tieCnt) {
                isCondorcetWinner = false; }; };
        if (isCondorcetWinner) {
            Focus[currentRound + 1] = Focus[currentRound]; }
        else ...
    

    Looking at a breakdown into cases:

    • If focusOptions is empty, isCondorcetWinner will remain at true after the loop completes all zero iterations, so we will keep the same focus for the subsequent round of voting (I am not weighing in right now on whether this has anything to do with the conventional notion of "Condorcet winner" despite your naming of this variable).
    • Otherwise, if we have an odd number of ballots, the code will clear isCondorcetWinner and take the "else", to be analyzed below.
    • Otherwise, if all of the focusOptions received approvals from exactly half of the ballots, isCondorcetWinner remains high and so we keep the focus into the next round.
    • Otherwise, we take the "else".

    ...



  • (This is in reply to the question of the reader imagining an interaction between the people and the code.)

    @Jack-Waugh, basically yes. To test the process, I have simulated electorates using spatial preferences, with varying weights on the various issues. Each voter-agent judges alternatives by the distance from their individual ideal points. That way the agents can both rank and score any proposed alternative. They can also propose new alternatives and decide when to try for something better and when to accept the current focus alternative as good enough for now.

    While the framework I have for creating electorates and running simulated elections for different voting systems is reasonable for doing comparisons under controlled conditions, the voter-agents are strictly mechanical in their actions. That makes it difficult to extrapolate real voter behavior. There are far too many social interactions that come into play once we start working with choice systems with iterative input. Real voters can persuade each other and be persuaded. We can also use more sophisticated methods for proposing new alternatives, and can introduce new issues into the collective, vote-moderated discussion that SAVE enables. SAVE is a tool that may potentially help in uniting us and enabling us to be our collective best. But it can only do that if we use it. Which means a lot of input from voters, i.e. us.



  • (This is in reply to the question about tieCnt.)

    @Jack-Waugh, the code is as I intended, but I can see where there might be some confusion. The tally[lastFocusIdx] value is the number of votes for termination of the process. In early rounds that is usually a very small fraction of the electorate. The ballotCnt / 2.0 value is half of the ballots cast in a round, and when a non-focus alternative A gets that number of votes it means the electorate is equally divided between the number of people who prefer A over the focus F, and those who prefer F over A.



  • I would expect that for a candidate to receive approvals from exactly half the ballots (in a large election) would be as rare as a polling place being struck by lightning. It seems odd that the electoral procedure would be designed to look out for such a case and treat it specially.



  • @Jack-Waugh said in Serial Approval Vote Election:

    I would expect that for a candidate to receive approvals from exactly half the ballots (in a large election) would be as rare as a polling place being struck by lightning. It seems odd that the electoral procedure would be designed to look out for such a case and treat it specially.

    While I was developing SAVE, I intentionally set up electorates with even numbers of agents. In the early rounds, ties are rare. But as the focus moves toward the conceptual middle of the electorate ties and near-ties become very probable.

    Just to provide a general idea of the simulation results, a SAVE run with limited agents would usually have an electorate size of 250, with 10 initial alternatives and would run for an average of 20 rounds. During the run, the number of alternatives would increase by about 60 alternatives, and 4 Condorcet winners would be found and later defeated by newly introduced alternatives. The strategy voter-agents used to create new alternatives is to split the difference between the focus and a losing alternative they prefer over the focus. The idea is to try to pick up half the margin.



  • @Jack-Waugh said in Serial Approval Vote Election:

    I bring here just a partial analysis of the code for now, because I am feeling a bit fatigued, and also suspecting you may want to revise.

    At least two rounds of voting are required to elect anyone: the initial round, which has no focus, followed by at least one round based on a focus.

    This is correct. In simulations the fastest I've seen is 4 rounds, while the slowest was around 50 rounds. The average is around 20 rounds. However, the bulk of the convergence to the center happens in around 10 rounds. The voter-agents are normally set to be slow on voting for termination.

    So in summary, termination happens exactly when the focus candidate has approvals from at least half the ballots and strictly more count of approvals than any other candidate. In this case, there are no more focus rounds, the election is concluded, and the focus candidate wins the election.

    Correct. For termination to occur, there must be at least majority acceptance (approval is not quite the right word), and if there are any other alternatives that are preferred over the focus by a majority, the termination must be by a super-majority. For termination, more voters must vote to accept the focus than vote for any other alternative.

    Looking at a breakdown into cases:

    • If focusOptions is empty, isCondorcetWinner will remain at true after the loop completes all zero iterations, so we will keep the same focus for the subsequent round of voting (I am not weighing in right now on whether this has anything to do with the conventional notion of "Condorcet winner" despite your naming of this variable).
    • Otherwise, if we have an odd number of ballots, the code will clear isCondorcetWinner and take the "else", to be analyzed below.
    • Otherwise, if all of the focusOptions received approvals from exactly half of the ballots, isCondorcetWinner remains high and so we keep the focus into the next round.
    • Otherwise, we take the "else".

    I use the term Condorcet winner because it seems to apply. Voters are asked if they prefer any of the non-focus alternatives over the focus F. Assuming either honesty or strategy, the number of votes for a non-focus alternative A indicates how the vote would be in a simple majority one-on-one race between A and F. If no A gets more than tieCnt votes, that means F is a Condorcet winner for this set of alternatives.

    The goal of changing the focus alternative is to improve the quality of the focus, making it more likely that some future round F will be a Condorcet winner.



  • selectNextFocus uses a test to decide between two branches. I posted some go at analyzing this test, but here I try to restate it more simply.

    The first branch (keeping the same focus) is taken when no alternative other than the focus was ticked by at least half the voters, or there is an even number of voters and every alternative other than the focus receives ticks from half the voters or fewer.

    The opposite of that condition can be stated as: the second branch is taken when some alternative to the focus received nods from at least half of the voters and {either there is an odd number of voters or some alternative to the focus received nods from strictly more than half the voters} (by one of de Morgan's laws).

    Distributing the "and" over the "or", we get that the second branch is taken when some alternative to the focus received nods from at least half of the voters and there is an odd number of voters, or some alternative to the focus received nods from at least half of the voters and some alternative to the focus received nods from strictly more than half the voters.

    There is redundancy in the two conditions of the second alternative, so we can simplify the expression to say that the second branch is taken when some alternative to the focus received nods from at least half of the voters and there is an odd number of voters, or some alternative to the focus received nods from strictly more than half the voters.

    If there is an odd number of voters, it's not possible to receive nods from exactly half of them. It has to be strictly fewer or strictly more-count. So, at least half implies more than half. So the entire condition for the second alternative is that there is at least one alternative to the focus that received nods from more than half.

    And the complement of that, the condition for the first branch, is simply that no alternative to the focus received nods from more than half.

    If the result of the test leads to the first branch, as I have mentioned, the focus remains the same for the subsequent round, and I see that in just that case, we invite the voters to suggest additional alternatives. I guess the rationale is that we have already exhausted the potential of the current field of candidates without success, because we neither found a better focus nor met the termination condition. To repeat a round with the same focus again and the same alternatives again would be nearly pointless.

    The other branch says to call selectModerateWinner and selectHistoryScoreWinner in that order. I have not analyzed either of those yet.

    Now I think to imagine the voters facing a focus round with three alternatives. Let them be G, H, and F, where F has the focus. Voter v0 does not like H and will not give H a nod under any circumstances. I want to examine the effects of the four possibilities of what V0 may do with respect to G and F, on the termination test and on the test in selectNextFocus. If v0 gives:

    • no nod to any alternative: This vote makes the termination less likely, because it withholds a point from the focus. This vote makes the first branch of the next-focus decision more likely, because it withholds score from the alternatives to the focus. So, this vote may be rational for v0 when v0 would prefer to see more alternatives introduced. That is the direction in which this vote is trying to push. This is quite like a "none of the above" vote as proposed in some other systems. It is appropriate when v0 is not favorably impressed with any of the alternatives.
    • G: This vote pushes toward moving on to the selectModerateWinner; selectHistoryScoreWinner sequence.
    • F: This vote pushes toward confirming F as the winner. If, due to the other voters, this doesn't happen, the residual effect of this vote will be to push toward asking for additional alternatives.
    • GF: It's hard to say whether this will help termination or impede termination. Termination requires F > G and F >= half. This vote helps F >= half, but does not help F > G. In case of continuation, this vote works toward selectModerateWinner; selectHistoryScoreWinner. This vote might not be very rational for v0 for any possible combination of attitudes toward F, G, and new alternatives.

    So, it seems as though, by and large, a voter should vote for F and against the other alternatives if she wants F, otherwise should vote against F and for whatever other alternatives she likes. Supporting F and some alternatives doesn't seem very useful. Supporting no-one can be useful, to urge for better candidates. This is very different from doing the same thing in straight Approval. And it is more like what naive people expect. Emotionally, voting against everyone doesn't mean you don't care; it means you don't like any of them and want somebody else or a restructuring of government. But the effect in Approval is the same as though you had sat out the election.



  • Electrowiki has a common example for showing how various voting systems work. This is how SAVE would handle the example.

    The setup is a vote for where to locate the Tennessee state capital. The options are the four cities of Memphis, Nashville, Chattanooga, and Knoxville. In the example, the population is limited to the four cities, with a table showing this preference profile:

    |----------------+----------------+------------------+----------------|
    | 42% of voters  | 26% of voters  | 15% of voters    | 17% of voters  |
    | near Memphis   | near Nashville | near Chattanooga | near Knoxville |
    |----------------+----------------+------------------+----------------|
    | 1. Memphis     | 1. Nashville   | 1. Chattanooga   | 1. Knoxville   |
    | 2. Nashville   | 2. Chattanooga | 2. Knoxville     | 2. Chattanooga |
    | 3. Chattanooga | 3. Knoxville   | 3. Nashville     | 3. Nashville   |
    | 4. Knoxville   | 4. Memphis     | 4. Memphis       | 4. Memphis     |
    |----------------+----------------+------------------+----------------|
    

    The way a SAVE procedure would work with this data would probably be something like this.

    • Round 0: Pre-loop, initial AV round. Voters have no reason to compromise (yet) so all voters only approve their first choice. Memphis gets 42%, Nashville gets 26%, Knoxville gets 17% and Chattanooga gets 15%. Since Memphis won the AV round, it becomes the first focus.

    • Round 1: Memphis is the focus. The voters near Memphis all vote to terminate the loop with Memphis as the final winner, and do not vote for any other, lesser cities. All the voters near any of the other three cities have Memphis as their last choice, so they all vote for all three of the other cities. The vote count is: 42% of the vote for loop termination with Memphis as final winner, 58% for each of Nashville, Knoxville, and Chattanooga. Result. The loop continues because 42% is not a majority. Since the focus was defeated (by all three other alternatives) the focus must change. The three-way tie under both the moderate winner rule and the history score rule is a bit unusual, but the tie-resolution rule is clear.

    The tie resolution rule says the tie goes to the earliest registered alternative, but I did not establish that order. For illustration purposes, I'm just going to show what happens in each of the three cases, starting with Nashville, then Chattanooga, then Knoxville. However, only one of these paths would be taken, based on an original registration order.

    • Round 2, Nashville: With Nashville as the focus, the Memphis voters still just vote for Memphis since Nashville is their second choice, giving Memphis 42% of the vote. The Nashville voters vote to terminate the loop with their 26%, but that is not a majority so the loop is not terminated. Since both Chattanooga and Knoxville are both rated above Nashville (and Memphis) both these voter groups vote for both cities, giving Chattanooga and Knoxville 32% of the vote. Since no alternative defeated Nashville, it is a Condorcet winner and continues as focus.

    We pause here and switch to the Chattanooga branch:

    • Round 2 Chattanooga: With Chattanooga as the focus, the Memphis voters are still the only group voting for Memphis (42% again), but this time they are also voting for Nashville as better than Chattanooga focus, so Nashville gets a total of 68% of the vote. The Chattanooga voters vote to terminate the loop, but with only 15% of the vote, the loop continues. Knoxville is also not getting support from any other group so it also only gets its base support of 17%. Chattanooga has been defeated by Nashville, so the loop continues. There is only one option for the focus, so the next focus will be Nashville.

    • Round 3 Chattanooga: With Nashville following Chattanooga as the focus, the vote counts are the same as with the Nashville branch (just one round later). Memphis gets its 42%, Nashville votes to terminate but only gets its base 26% of the vote. Chattanooga and Knoxville each support both, so they each get 32%. Net result is continuation with Nashville remaining as the focus due to its being a Condorcet winner.

    We pause here to see how Knoxville goes.

    • Round 2 Knoxville: With Knoxville as the focus, Memphis is voting for itself, Nashville and Chattanooga. Memphis still only gets its base of 42%, but Nashville and Chattanooga both do much better. Nashville votes for both itself and Chattanooga, and ends up with 68% of the vote. Chattanooga only votes for itself, but with support from both Memphis and Nashville, its total end up at 83%. Knoxville votes to terminate, but without other support it ends up with 17%. The loop continues. The possible choices for the next focus are Nashville with 68% and Chattanooga with 83%. The moderate winner rule picks Nashville, as closest to the desired vote share of 66.5%. The history period is: 2 (Knoxville) and 1 (Memphis), giving history scores for Nashville: (2,0,2), and Chattanooga: (2,0,2), which are identical and so do not override the moderate winner choice. So the next focus is Nashville.

    • Round 3 Knoxville: With Nashville following Knoxville as the focus we have the exact same situation as the other two branches. Memphis gets 42%, Nashville votes to terminate with 26%, Chattanooga and Knoxville have their mutual support group and each get 32%. The loop continues, with Nashville continuing as the focus due to its being a Condorcet winner.

    At this stage in the process, things can go one of two ways. Nashville is a recognized Condorcet winner so is clearly the best alternative currently proposed. If another 24% plus one voters decide Nashville is good enough, the barest majority will terminate the loop and the capital will be in Nashville. It may not happen in a single round, and there can certainly be efforts to change voter opinions and get another outcome. But Nashville is now confirmed to be the best option among the four initial alternatives.

    Yet SAVE is an iterative process, and one of the most significant opportunity iteration enables is the possibility to add to the choices. The brief for this example social choice includes the explicit statement that "everyone wants to live as near to the capital as possible." It also includes an outline map of Tennessee with the four cities marked in their relative locations. That map encodes data that could change the outcome of this social choice.

    I've recreated the map and drawn three indifference curves, centered in each of Memphis, Chattanooga, and Knoxville, and each passing through Nashville. Any location inside a circle is preferred by the voters near its center over Nashville. I've placed a dot at a location that is preferred over Nashville by all three of the other groups.

    state-TN-modified-1-500x125.png

    The addition of location A results in the revised preference profile shown here:

    |----------------+----------------+------------------+----------------|
    | 42% of voters  | 26% of voters  | 15% of voters    | 17% of voters  |
    | near Memphis   | near Nashville | near Chattanooga | near Knoxville |
    |----------------+----------------+------------------+----------------|
    | 1. Memphis     | 1. Nashville   | 1. Chattanooga   | 1. Knoxville   |
    | 2. Location A  | 2. Location A  | 2. Location A    | 2. Chattanooga |
    | 3. Nashville   | 3. Chattanooga | 3. Knoxville     | 3. Location A  |
    | 4. Chattanooga | 4. Knoxville   | 4. Nashville     | 4. Nashville   |
    | 5. Knoxville   | 5. Memphis     | 5. Memphis       | 5. Memphis     |
    |----------------+----------------+------------------+----------------|
    

    With the addition of location A, we go back to a single flow as round 4.

    • Round 4 rejoined: The focus is Nashville again, but the addition of location A causes a change in the vote counts. Memphis votes for itself an A because both are better than Nashville. Nashville's vote is again 26% for loop termination. Chattanooga votes for itself, A and Knoxville. Knoxville votes for itself, Chattanooga, and A. So we have 26% for loop termination, meaning continue. Memphis gets 42%, Chattanooga gets 32%, Knoxville gets 32%, and the new location A gets 74%. As A has a majority, the focus must change, and as it is the only choice, A will be the next focus.

    • Round 5: With A as the focus, Memphis votes for Memphis, Nashville votes for Nashville, Chattanooga votes for Chattanooga, and Knoxville votes for Knoxville and Chattanooga. Vote counts are Memphis 46%, Nashville 26%, Chattanooga 32%, and Knoxville 17%. No votes for loop termination. A is a Condorcet winner and will remain the focus for round 6.

    Since new alternatives are allowed again, we get another proposal of location B.

    state-TN-modified-2-500x125.png

    Revised preference profile with A and B:

    |----------------+----------------+------------------+----------------|
    | 42% of voters  | 26% of voters  | 15% of voters    | 17% of voters  |
    | near Memphis   | near Nashville | near Chattanooga | near Knoxville |
    |----------------+----------------+------------------+----------------|
    | 1. Memphis     | 1. Nashville   | 1. Chattanooga   | 1. Knoxville   |
    | 2. Location B  | 2. Location B  | 2. Location A    | 2. Chattanooga |
    | 3. Location A  | 3. Location A  | 3. Knoxville     | 3. Location A  |
    | 4. Nashville   | 4. Chattanooga | 4. Nashville     | 4. Nashville   |
    | 5. Chattanooga | 5. Knoxville   | 5. Location B    | 5. Location B  |
    | 6. Knoxville   | 6. Memphis     | 6. Memphis       | 6. Memphis     |
    |----------------+----------------+------------------+----------------|
    
    • Round 6: Focus is A, and the new alternative at B has been proposed. Memphis supports itself and B. Nashville supports itself and B. Chattanooga supports itself. Knoxville supports itself and Chattanooga. No votes for termination (A). Memphis gets 42%. Nashville gets 26%. Chattanooga gets 32%. Knoxville gets 17%. B gets 68%, and the focus. Since B is a new focus, no new proposals are allowed.

    • Round 7: With B as focus, Memphis supports itself. Nashville supports itself. Chattanooga supports itself, A, Knoxville, and Nashville. Knoxville supports itself, Chattanooga, A, and Nashville. No votes for loop termination. Votes are: Memphis: 42%, Nashville: 58%, Chattanooga: 32%, Knoxville: 32%, A: 32%. The loop continues, Nashville gets the focus as the only choice. Since Nashville is a repeat, new proposals are allowed. Note that we now have a cycle: Nashville, A, B, Nashville.

    This time we get a compromise proposal: Location C is the average of Nashville, A and B.

    state-TN-modified-3-500x125.png

    Revised preference profile with A and B:

    |----------------+----------------+------------------+----------------|
    | 42% of voters  | 26% of voters  | 15% of voters    | 17% of voters  |
    | near Memphis   | near Nashville | near Chattanooga | near Knoxville |
    |----------------+----------------+------------------+----------------|
    | 1. Memphis     | 1. Nashville   | 1. Chattanooga   | 1. Knoxville   |
    | 2. Location B  | 2. Location C  | 2. Location A    | 2. Chattanooga |
    | 3. Location C  | 3. Location B  | 3. Knoxville     | 3. Location A  |
    | 4. Location A  | 4. Location A  | 4. Location C    | 4. Nashville   |
    | 5. Nashville   | 5. Chattanooga | 5. Nashville     | 5. Location C  |
    | 6. Chattanooga | 6. Knoxville   | 6. Location B    | 6. Location B  |
    | 7. Knoxville   | 7. Memphis     | 7. Memphis       | 7. Memphis     |
    |----------------+----------------+------------------+----------------|
    
    • Round 8: Nashville is again the focus, and C has been proposed. Memphis supports itself, B, C, and A. Nashville supports loop termination. Chattanooga supports itself, A, Knoxville, and C. Knoxville supports itself, Chattanooga, and A. Votes are: Memphis: 42%, loop termination (Nashville): 26%, Chattanooga: 32%, Knoxville: 32%, A: 74%, B: 42%, and C: 57%. Loop continues. Two choices for next focus. Moderate winner rule selects C. History period is: 8 (Nashville), 7 (B), and 6 (A). A was active through the whole history period, with score is (2,-18,1). C has only been active in one round, so its score is (1,0,1). The history score choice replaces the moderate winner choice, so A will be the next focus. New proposals are allowed, but none are presented.

    • Round 9: A is focus with no new proposals. Memphis supports itself, B, and C. Nashville supports itself, C, and B. Chattanooga supports itself. Knoxville supports itself and Chattanooga. Votes are: Memphis: 42%, Nashville: 26%, Chattanooga: 32%, Knoxville: 17%, A: no votes for loop termination, B: 68%, and C: 68%. Loop continues. Two choices for next focus, both with 68%. Moderate winner rule chooses B under the tie-breaking rules. History period is: 9 (A), 8 (Nashville), 7 (B). B was active for the whole history period with score (2,-8,1). C has only been active for two rounds so its history score of (2,0,2) counts as a tie, so B will be the next focus. New proposals are allowed, but none are presented.

    • Round 10: B is focus with no new proposals. Memphis supports itself. Nashville supports itself, and C. Chattanooga supports itself, A, Knoxville, C, and Nashville. Knoxville supports itself, Chattanooga, A, Nashville, and C. Vote counts are: Memphis: 42%, Nashville: 58%, Chattanooga: 32%, Knoxville: 32%, A: 32%; B: no votes for loop termination, and C: 58%. Loop continues. Two chooses for next focus, both with 58%. Moderate winner rule picks Nashville using the tie-breaking rule. History period is: 10 (B), 9 (A), 8 (Nashville). Nashville's history score is: (2,-31,1), while C's history score is (3,0,3) and fully active. The better history score overrules the moderate winner rule. C is the next focus. Since C is not a repeat, no new proposals are allowed.

    • Round 11: C is focus, no new proposals. Memphis supports itself and B. Nashville supports itself. Chattanooga supports itself, A, and Knoxville. Knoxville supports itself, Chattanooga, A, and Nashville. Votes are: Memphis: 42%, Nashville: 43%, Chattanooga: 32%, Knoxville: 32%, A: 32%, B: 42%, and C: no votes for termination. The loop continues with C remaining the focus as a Condorcet winner.

    I've not terminated the loop because it could easily continue (see below in the region between Memphis and Chattanooga, below C). SAVE will only stop when a supermajority of the voters ask for it. The context of this example does not allow me to fully justify termination. The decision to vote for loop termination is an individual choice, and is a trade-off between the current focus alternative and the potential gain or loss of continuing.

    state-TN-modified-4-500x125.png

    The purpose of this example is simply to run SAVE in the same context as other voting systems to see how it compares. On the plus side, SAVE gets good results when it runs long enough, uses direct voter input to resolve majority cycles (thus handling Arrow's problems with cycles), and does so in a straightforward manner in terms of Gibbard-Satterthwaite. On the minus side, SAVE takes many more rounds.



  • @Jack-Waugh, Thanks for working through all these examples. I, too, had some questions about the GF vote, or the more general instructions regarding always voting for every alternative subjectively preferred over the focus. For a GF vote to be instrumental in impeding termination, the G vote total would have to be at least a strict majority (that is: F > half, because equal to half is not sufficient), and the F vote total would have to be the maximum vote count and exactly equal to the G vote total. Thus it is possible for a GF vote to hinder termination. However, in addition to G blocking termination, G is preferred by the voter over F, so G blocking theloop termination with F as the final winner is also indicating the possibility for G to be a later focus and possibly a better final outcome.

    For testing purposes I wrote voter-agent code for voting to stop the loop. This strictly speaking is not part of SAVE, but it does indicate what I think voters might do. Each voter-agent has a property called indifference, which is a fraction between 0.0 and 1.0. At 0.0 the slightest difference matters, while at 1.0 the voter is totally indifferent to the alternatives. All voters start at 0.0 and increment their indifference value (1) every time the focus is a Condorcet winner (because if we cannot improve upon a Condorcet winner we will eventually accept it), and (2) whenever the focus subjectively improves after having first moved away (when the focus move away, such as when in a majority cycle, we also want to be more accepting, but only as we're coming back). These are the five basic reasons for an agent to vote for the focus:

    • Ideal - the focus is close to the voter's subjective ideal alternative.
    • Cluster - the best and the worst of the most recent focus alternatives are really close together.
    • Top-half - the spread between the best and the worst is moderately close (3x indifference) and the focus is in the top half of that spread.
    • Limited-gain - the focus is close to the upper limit to any potential future gains.
    • Peak - the focus is as good or better than a focus that was followed by a movement away from the agent's idea.
      All of these conditions except Peak use the indifference value. The conditions are ordered from most difficult to satisfy to the easiest to satisfy.

    The reason I bring this up is because I think voters might well vote for loop termination on the off-chance they can get a better result more quickly. Which implies a vote to terminate usually does not mean "I really want to terminate now" but instead is the kinder and gentler "it is okay to terminate now". Under those circumstances, the GF vote is perfectly reasonable, and supports the possibility of termination without foregoing the chance to influence the next focus choice.


Log in to reply