Serial Approval Vote Election



  • I've been bothered for years (actually decades) by the various impossibility results in voting theory and the consequential belief that democracy is therefore impossible. In response I've gone back to first principles and reviewed a lot of what has been done including Arrow, Black, Brams, Condorcet, Copeland, Downs, Gibbard, Hotelling, May, McGarvey, McKelvey, Satterthwaite, Schulze, Shepsley, Sloss, and W.D. Smith, among others.

    One basic thing that works is majority decision between two alternatives. Two things that are problematic are the very real probability of top majority cycles, and ballots where there is a difference between an honest response and a strategic one. Spatial modeling provides insights in to what a good outcome should be that go beyond beating most or all other alternatives, or reversing the closest election results. And spatial models are sufficient to represent any tournament or preference profile in multiple ways.

    The challenges for collective choice of a single, most acceptable option include the various way our political and social structures prevent the introduction of better alternatives and the inability of many voting systems to select the best alternatives presented. We also have political issues in that our representative bodies are not always representative.

    With all that in mind, I'd like to present serial approval vote election (SAVE) as a collective choice procedure that addresses all of these issues, albeit at a cost. That cost is multiple voting rounds, and the number of rounds is neither fixed nor limited in advance. The general procedure is this:

    • Pre-loop: Choose first focus using approval voting.
    • Loop: Start iteration:
      1. Run a focused approval vote round
      2. If the focus alternative is the AV winner and has a majority, go to Post-loop, ending the iteration with this winner.
      3. Otherwise, select the focus alternative for the next round.
      4. If the focus alternative for the next round has previously been a focus, allow the proposal of new alternatives.
      5. Allow time for campaigning or discussion
      6. Back to top of loop for next focused approval vote round.
    • Post-loop:
      1. Declare the overall winner, then
      2. Hold an AV mandate round to explicitly measure the mandate of the winner and all the other alternatives.

    The focused approval vote round differs from the approval vote you are all familiar with in the following ways. First, one of the alternatives is the designated focus alternative for the round. For all the other alternatives, the question is not "do you approve this alternative?" but rather "is this alternative better than the focus?". These are binary choices, and as such the honest response is also the best strategic response. The focus is the only alternative that can win in this round, so voters are asked the question: is this focus good enough? This is again a binary choice between selecting this focus as the final winner and having another round, and thus the honest response is the strategic response.

    There are a few more details I'll be happy to get into in a subsequent post if folks are interested, such as how the next focus is chosen and the guts of my test simulations.

    A few thoughts in closing this post. There are a number of situations in which iterative systems are already in use, such as agendas, straw votes in committees, different types of negotiations, and even candidate elections if you consider multiple primaries. This procedure can be implemented using any manual, mechanical, or software voting system that can process AV ballots. This method is designed for situations where there are a lot of voters and many more possible outcomes, with only a few alternatives initially proposed. Finally, due to voters proposing new alternatives during the process, SAVE can have a VSE of over 100%.



  • Why would you expect voters to change their answer between the pre-iteration round and the first focused round?



  • I expect voters to change their ballots both because the questions change, and because they have more and better information about what is possible. I imagine voters start with limited knowledge about the various alternatives and no information about the other voters. The pre-iteration round lets voters vote for the subjectively best few alternatives and see what happens. My mental model of voters has us maintaining and updating rough judgement about the alternatives we know about. This set of alternatives seem good, those not so much, and the rest haven't been considered yet.

    In the pre-iteration round, voters vote for the alternatives they find acceptable. The result of this round identifies the first focus. Knowing the first focus, and the vote counts for all the other alternatives gives the voters the information they need to be strategic for the next focused round.

    To be specific, let T be the imaginary alternative exactly on my personal threshold as a voter. In the pre-iteration round I would vote for all alternatives A such that AT, and not vote for any A such that TA. In the first focused round, though, the questions change. F is now the focus. For any A different from F, the question is not approval (is AT ?), but rather improvement (is AF ?). And for F itself, the question is: "do I want to stop with F as the final winner?"

    So, if we consider three alternatives B, M, and W such that BT and BF, M is between F and T, and both TW and FW, we have the following ballot entries:

    • In both rounds, vote for B.
    • In both rounds, do not vote for W.
    • If TF, do not vote for M in initial AV round, but do vote for M as better than F in first focus round.
    • If FT, vote for M in initial AV round, but do not vote for M being better than F.

    The above should be the individual voter behavior independently of what other voters do. It is both honest and strategic. (The strategy argument comes from W.D. Smith's comments on strategic aproval voting.)

    The question about when a voter should vote for the focus is a bit more nuanced, and is best addressed after I post the rules for choosing the next focus.



  • SAVE is essentially a hill-climbing algorithm, and the focus selection rules are the way it picks the next step up. Once it reaches the top, meaning the current focus Fc is a Condorcet winner, Fc remains the focus until it is either accepted as the final winner or is defeated by either a new alternative or as a result of voters changing their preferences. Since SAVE runs over multiple rounds, there is time for voters to do so.

    If, on the other hand, Fc is not a Condorcet winner, the next focus must be different. By definition, if Fc is not a Condorcet winner, the set of alternatives that defeated Fc is not the empty set. The set of alternatives to replace Fc contains all alternatives that received at least half the vote.

    Note: the general tie-breaking rule in SAVE is prefer the alternative proposed earlier. (This reduces a problem that came up in simulation in which near-clones delayed the convergence of the focus to the center by a few rounds.)

    When the focus must change, there are two different criteria used to select the next focus that come into play based on the amount of relevant information available. When there is relatively little information, the moderate winner rule is more effective. This rule is based on the one-dimensional spatial insight that when there are many alternatives that beat the focus, the alternative with a moderate margin of victory is more likely to be a Condorcet winner than either an alternative with the maximum possible margin or an alternative that just tied the focus. The moderate winner rule only looks at the most recent round of data, and tends to jump from one side of the center to the other as it converges. But it is fairly good at getting close to the center of the electorate when there is little history.

    To determine the moderate winner alternative Wm, let d be the vote count of the maximum win against Fc, and T be the vote count for an exact tie (possibly including a half-vote). Let t = (d + T)/2 be the target vote count. The moderate winner Wm is the alternative with vote count mv such that |mv-t| is minimal. When two alternatives with different vote counts t+n and t-n equally close to the targer, prefer the alternative with vote count t+n. Otherwise, the standard tie-breaking rule applies.

    When there is more relevant information, the history score rule is more effective. The history score looks at the wins, ties and margins of defeat for the alternatives during the history period. This history period is the longest interval of consective rounds, starting from the most recent round and working backwards, in which all the focuses are unique. The justification for limiting the wins, ties, and losing margins data to the history period is to allow newly proposed alternatives to become quickly relevant. The detection of a majority cycle renders all round data prior to the cycle irrelevant, as does the detection of a Condorcet winner.

    The history score for an alternative consists of three parts: the total of wins and ties against the focuses in the history period, the vote deficit (the sum over all rounds in the history period of min(0, votes receivd - N/2) where N is the number of ballots), and the total number of wins in the history period. (When determining the history score of an alternative that was a focus during the history period, it is considered to have tied itself.)

    To determine the history score winner Wh is the alternative with the highest wins+ties component. If more than one alternative meets this criteria, pick the one with the least negative vote-deficit component. If more than one alternative meets both criteria, pick the one with the most wins component. If there is still duplication, use the general tie-breaking rule. (When comparing alternatives that were not active in the same number of rounds in the history period, such as when one or both were introduced in different rounds in the history period, only the wins+ties component is used.)

    In summary, following a round in which Fc has just been the focus and has not been accepted as the final winner, the focus for the next round will be:

    • Fc if it is a Condorcet winner, or
    • The moderate winner Wm, or
    • The history score winner Wh if it is distinct from Wm and the history score of Wh is strictly better than the history score of Wm.

    For those keeping track, the history score is a hybrid of the Copeland score and the majority cycle breaking method in the Condorcet variation known as the Schulze or beat-path method.



  • @tec said in Serial Approval Vote Election:

    These are binary choices, and as such the honest response is also the best strategic response.

    That's only true if there are only two candidates...



  • @Psephomancy, honesty is certainly the best strategy with two alternatives. (I prefer alternatives over candidates because it's easier to propose a compromise or hybrid for a budget or policy than for a person.) However I think, under SAVE, my statement is true even with multiple alternatives. Or at any rate I have not yet managed to come up with any scenario in which it is not true.

    Here is my reasoning. (The basis of this argument comes from Smith's Range Voting paper from 2000.) The question is one of strategy. If I, as a voter vote for all the alternatives I prefer over the focus, and vote for the focus if I also want the the iteration to end with the focus as the final winner, I will have given honest answers to the questions asked. The strategic question is whether or not I can do better by strategically deviating from my honest ballot.

    So what are my strategic options? Let's consider the focus vote first. My potential strategies are:

    • (1) Not vote for the focus when I do want the iteration to terminate and the current focus to be the final winner, or

    • (2) Vote for the focus when I do not want the loop to terminate with the current focus as the final winner.

    If my strategic vote were to make a difference in (1), I would not get the result I wanted, and there is a possibility that I never would. So this is not a good strategy.

    If my strategic vote were to make a difference in (2), I would be stuck with this current focus as the final winner, and this could not be fixed. So this is a really bad strategy.

    So far, it seems like honesty is the best policy for the focus vote. What about the non-focus votes? My potential strategies are:

    • (3) Vote for an alternative I like less than the focus, or

    • (4) Not vote for an alternative I prefer over the focus.

    If my strategic vote were to make a difference in (3), an alternative I like less than the current focus will be in the group of possible replacements for the focus, which is not a better outcome.

    If my strategic vote were to make a difference in (4), an alternative I preferred over the focus would not be in the group of possible replacements for the focus, which is not likely to be a better outcome.

    So far, any deviation from my honest ballot does not seem strategic.

    There is one situation I'm not certain about. If I want to terminate the loop, the strongest vote for termination is to vote for the focus and not vote for any other alternatives. If this makes a difference and the current focus is the final winner, that's great for me. But if it doesn't, my lack of a vote for the alternatives I prefer might well reduce their chances of being the focus later. So I'm not sure exactly how strategic this action would be.

    It's possible I overlooked something. If anyone can come up with a situation in which an honest ballot is not strategic, I really want to know about it.



  • Maybe it's just me, but I find it hard to comb apart in your presentation, the definition of the tallying procedure, from your analysis of the system. I think you intersperse the analysis with the definition. I might have a chance of understanding if you would post the tallying procedure by itself.



  • @Jack-Waugh, I apologize for my lack of clarity. I don't think it's just you. I have two responses about the tally. Hopefully one or the other will make things clearer.

    • The SAVE tally as parallel pairwise majority decisions.

    The pre-iteration round is just an approval vote among the initial alternatives, with the winner becoming the first focus alternative. In each subsequent focus round the ballot input is tallied exactly like an AV round, but the vote counts are interpreted differently. For each non-focus alternative A, the vote count is considered A's vote in a majority decision between A and the focus F. If A's vote count is at least half the ballots from this round, A is a potential replacement for F (assuming there is a next round and F is not a Condorcet winner). If F's vote count is strictly more votes than any non-focus alternative and is more than half the ballots cast, F becomes the final winner. Otherwise, there will be another round and the focus rules above will be used to determine the next focus.

    • The SAVE tally as a series of strategic approval vote rounds.

    This interpretation of SAVE considers it just a series of AV rounds. The first AV round has no expectations of who the winner might be, so voters set individual thresholds of approval. During the iteration, the applicable focus alternative is treated as the expected winner as if it were determined by a very good poll, and voters fill out their ballots strategically, approving of all alternatives better that the focus, and approving of the focus only when they want the process to terminate. The iteration continues until the current focus both gets a majority decision and is the outright AV winner.

    In both interpretations, once the SAVE winner is determined there is a final AV round with individually determined thresholds to measure the mandates for each alternative.



  • First off: I think you (@tec ) are on to something valuable here and I agree that sometimes the combined cost of:
    1 multiple voting rounds
    2 the allowance of time for deliberation, discussion, campaigning
    3 the proposal of new alternatives
    could lead to:
    1 better collective decisions
    2 more broadly shared feelings of fairness about the process
    3 acceptance of the winning proposal.
    4 sometimes a VSE of over 100%
    What I often see lacking in mathematical models of voting systems and procedures is the recognition that feelings, irrational behaviour, learning and changing once own preferences in and after social communication are not a bug but a feature of humans and groups. So many kudos to you for your proposing Serial Approval Vote Election (SAVE)!

    Then some critical remarks intended to make it clearer and better because I'm having trouble understanding both the general procedure and the tallying-rules:
    a) am I right in understanding that what you call the "focused approval round" is not approval voting at all but a series of pairwise comparisons. Maybe another name for this step would be more clear?
    b) I don't understand the use of Post-loop step 2, can't this be left out?
    c) can you explain what happens during the procedure to the "rest"-category you mention in "My mental model of voters has us maintaining and updating rough judgement about the alternatives we know about. This set of alternatives seem good, those not so much, and the rest haven't been considered yet."
    d) on any subject my preferences change when I hear and consider new arguments including other peoples preferences (and majorities or interesting minority-views) and my views become more nuanced. That would suggest a bigger scoring range would better fit my real-lifepreferences over time. Is it your view that adapting SAVE to use approval in the pre-loop, and for instance range 1..5 in the first round of the loop and range 1..10 in the second round (and keeping increasing the range in each extra round) would introduce unwanted tactical strategies?



  • Thank you, @multi_system_fan, for your response. A good part of why I'm posting here (as opposed to trying to get an article published in a journal), is to get feedback on whether SAVE really could be as transformative as I think it might be. Your kudos are most welcome.

    However, your critical remarks are even more welcome because I am driven to get SAVE out into the real world in active use, and so far my writing has not been up to the task. I welcome any and all question and criticisms because if I'm wrong it gives me the opportunity to correct my thinking and if I'm right but did not express myself clearly, it gives me a chance to correct my writing so the next people who read about SAVE won't stumble over my earlier lack of clarity.

    My next post, prompted by @Jack-Waugh, was going to be the code for the tally process and the selection of the next focus. That is still in the works, but it is delayed because of the desire to write it in JavaScript. (The code started out in NetLogo, then I moved it to Python because the testing environment is better. JavaScript will make it possible to get working examples of the code accessible in a browser without having to over-burden a web-server, so it is a good move.) But since I don't yet know JavaScript, the conversion is taking longer than I had hoped.

    So, while the tally code and logic should be up soon, I'll address your other points now.

    a) The phrase "focused approval" is how I think of the process, but you are correct that it could also be thought of as a series of pairwise comparisons. The difference is a matter of perspective. If you look at the ballot as a series of questions, it is a series of pairwise comparisons.

    However, if you think of the ballot as a way of eliciting voter preferences and you assume that voters could do the work of placing the alternatives in an ordered list, the term "focused approval" makes a bit more sense. Given a preference order, filling out an AV ballot is just a matter of drawing the line between what is approved and what is not approved. Once that line is drawn, every alternative above it is approved, and the rest is not.

    What is happening with a focused approval vote, (and I got the idea from W.D. Smith's range voting paper from 2000), is a strategic AV ballot given a preference order and the assumption that the focus alternative is predicted to win. Under those circumstances, a strategic voter who was okay with that would set their approval threshold so as to approve the focus alternative and everything better. Similarly, a strategic voter who was not okay with the focus alternative would set their approve threshold to just exclude the focus while still voting for everything better because that would maximize the chances of a better outcome even if the voter did not really approve of some of the alternatives they were voting for.

    As to changing the term, the "approval" part comes from AV and is accurate in terms of the way the ballots are aggregated. Any voting technology that can handle AV ballots can be used for SAVE, and I think AV is a very good system if you are limited to one round. I'm currently partial to the "focused" part, but I initially used "targeted approval" and have considered and rejected "front-runner approval". Another option is "strategic approval". My main objection to changing the name is changing the term in all the code and tests, but that's more friction than objection and if there's a better term now is a good time to make the change. Any suggestions?

    b) The mandate round is a direct and personal response to US presidential politics and to statements made by G.W. Bush to the effect that his election (with the support of just a bit over 25% of the electorate in a low-turnout election) constituted an overwhelming mandate for all his policies, including those that were never mentioned by him in his campaign.

    There are certainly elections in which the mandate round is neither needed nor desired, and I generally consider it optional. However, having it there serves two purposes. There are situations in which knowing the strength of the mandate of the final result and that of the other alternatives will make a difference in what happens after the election. For example, a mandate round will differentiate between a common ground that is unifying, and a weak compromise that still needs to be sold to the electorate. For those situations, actually measuring the mandates is important even if it doesn't change the outcome.

    The other purpose is to clearly differentiate between voting for the best collective outcome (the final focus alternative) and actually supporting it. In my mind, this is important during times of social change. I might vote for a compromise I don't fully support, and then continue to work to change hearts and minds so the next time the moderate result is a little closer to my radical position. Under those circumstances, having a mandate round can be very useful. Yet even when knowing the mandates is not useful in itself, having the mandate AV round be separate from the focused rounds emphasizes the difference between finding a working compromise for the whole collective and clearly holding ones own opinions and preferences.

    So yes, the mandate round is optional. But at this time I think it really should be included in the SAVE discussions, even if it isn't going to be used in all SAVE procedures.

    c) In my mental models the "rest" include those alternatives I'm just not familiar with and those I only know a little about. For example, in 2007, my "rest" included both Tommy Thompson and Barak Obama. Over time, Obama left that category, while Thompson remains in it. If we widen the scope to all collective choice processes (for which SAVE is designed), we still start the process with categories of alternatives, some good, some not good, and some not yet known or considered, i.e. the rest. If we are using SAVE (or some SAVE-like system) we have the time to understand our choices, learn about other alternatives, and find or create an alternative that truly reflects our collective preferences. SAVE should also help us identify alternatives whose support is changing, providing some guidance on which of the "rest" alternatives worth further consideration.

    d) I agree with you that over time our preferences do become more nuanced. I disagree with the idea of introducing more finely resolved scoring in SAVE for a few reasons. My issue with anything beyond binary choices is based on Arrow's possibility theorem for two alternatives (yes, we can choose between two alternatives), Arrow's general possibility theorem (a.k.a. Arrow's impossibility theorem, which points out majority cycles are possible when there are three or more alternatives), and the Gibbard-Satterthwaite theorem (stating any system with more than two choices is either manipulable or has a dictator).

    In essence, and this deserves a longer discussion, SAVE is designed to get around the problem in AIT (majority cycles) by exposing them and giving voters choices regarding what to do about them. Those choices include both defeating the cycle by proposing an alternative that is collectively preferred over every member of the cycle thus making it irrelevant, and breaking the cycle through an explicit and overwhelming choice.

    SAVE doesn't exactly get around Gibbard-Satterthwaite, but instead embraces it. SAVE is facilitating a choice from among multiple alternatives. GST declares that is manipulable. SAVE responds iteratively by proposing the focus alternative and guiding voters to vote in the one way that most strongly reflects their individual preferences. If the manipulated vote fails to select this particular focus, SAVE presents another choice: usually with another focus alternative. And again asks voters to manipulate their naive approval vote into a more sophisticated focused approval vote. The iteration continues until the manipulated vote supports the selection of the focus alternative.

    SAVE goes beyond these impossibility results by embracing their truth and working with the underlying reality. But as far as I can tell, this only works with binary choices. I fear that adding multiple levels of support would cause exactly the problem you suggest and introduce unwanted tactical strategies.

    I think this post is long enough (possibly too long), and anything further I might write would probably depend on a better understanding of exactly how SAVE determines the next focus. So for me, it's back to JavaScript. 🙂

    Again, thank you for your kudos and critiques. Please let me know if I've answered your concerns, and more importantly if I haven't.



  • interesting!

    Maybe you can compare to https://electowiki.org/wiki/MARS_voting based on this discussion: https://www.reddit.com/r/EndFPTP/comments/lil4zz/scorebetterbalance_a_proposal_to_fix_some/

    also Smith//Score seems a bit simpler to me, see https://electowiki.org/wiki/Smith//Score



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


Log in to reply