vse_sim.methods

   1import random
   2
   3from numpy import argsort, percentile, sign
   4
   5from .compat import as_builtin_scalar, floor, mean
   6from .data_classes import CandidateWithCount, Method, rememberBallot, rememberBallots
   7from .dataframe import ballots_from_dataframe
   8from .voter_models import DeterministicModel, Voter  # noqa: F401 - used by doctests
   9
  10
  11####EMs themselves
  12class Borda(Method):
  13    candScore = staticmethod(mean)
  14
  15    nRanks = 999  # infinity
  16
  17    @staticmethod
  18    def fillPrefOrder(
  19        voter,
  20        ballot,
  21        whichCands=None,  # None means "all"; otherwise, an iterable of cand indexes
  22        lowSlot=0,
  23        nSlots=None,  # again, None means "all"
  24        remainderScore=None,  # what to give candidates that don't fit in nSlots
  25    ):
  26
  27        venum = list(enumerate(voter))
  28        if whichCands:
  29            venum = [venum[c] for c in whichCands]
  30        prefOrder = sorted(venum, key=lambda x: -x[1])  # high to low
  31        Borda.fillCands(ballot, prefOrder, lowSlot, nSlots, remainderScore)
  32        # modifies ballot argument, returns nothing.
  33
  34    @staticmethod
  35    def fillCands(
  36        ballot,
  37        whichCands,  # list of tuples starting with cand id, in descending order
  38        lowSlot=0,
  39        nSlots=None,  # again, None means "all"
  40        remainderScore=None,  # what to give candidates that don't fit in nSlots
  41    ):
  42        if nSlots is None:
  43            nSlots = len(whichCands)
  44        cur = lowSlot + nSlots - 1
  45        for i in range(nSlots):
  46            ballot[whichCands[i][0]] = cur
  47            cur -= 1
  48        if remainderScore is not None:
  49            i += 1
  50            while i < len(whichCands):
  51                ballot[whichCands[i][0]] = remainderScore
  52                i += 1
  53        # modifies ballot argument, returns nothing.
  54
  55    @staticmethod  # cls is provided explicitly, not through binding
  56    @rememberBallot
  57    def honBallot(cls, utils):
  58        ballot = [0] * len(utils)
  59        cls.fillPrefOrder(utils, ballot)
  60        return ballot
  61
  62    @classmethod
  63    def fillStratBallot(
  64        cls,
  65        voter,
  66        polls,
  67        places,
  68        n,
  69        stratGap,
  70        ballot,
  71        frontId,
  72        frontResult,
  73        targId,
  74        targResult,
  75    ):
  76        """Mutates the `ballot` argument to be a strategic ballot.
  77
  78        >>> Borda().stratBallotFor([4,5,2,1])(Borda, Voter([-4,-5,-2,-1]))
  79        [3, 0, 1, 2]
  80        """
  81        nRanks = min(cls.nRanks, n)
  82        if stratGap <= 0:
  83            ballot[frontId], ballot[targId] = (nRanks - 1), 0
  84        else:
  85            ballot[frontId], ballot[targId] = 0, (nRanks - 1)
  86        nRanks -= 2
  87        if nRanks > 0:
  88            cls.fillCands(ballot, places[2:][::-1], lowSlot=1, nSlots=nRanks, remainderScore=0)
  89        # (don't) return dict(strat=ballot, isStrat=isStrat, stratGap=stratGap)
  90
  91
  92RankedMethod = Borda  # alias
  93RatedMethod = RankedMethod  # Should have same strategies available, plus more
  94
  95
  96class Plurality(RankedMethod):
  97    nRanks = 2
  98
  99    @staticmethod
 100    def oneVote(utils, forWhom):
 101        ballot = [0] * len(utils)
 102        ballot[forWhom] = 1
 103        return ballot
 104
 105    @staticmethod  # cls is provided explicitly, not through binding
 106    @rememberBallot
 107    def honBallot(cls, utils):
 108        """Takes utilities and returns an honest ballot
 109
 110        >>> Plurality.honBallot(Plurality, Voter([-3,-2,-1]))
 111        [0, 0, 1]
 112        >>> Plurality().stratBallotFor([3,2,1])(Plurality, Voter([-3,-2,-1]))
 113        [0, 1, 0]
 114        """
 115        # return cls.oneVote(utils, cls.winner(utils))
 116        ballot = [0] * len(utils)
 117        cls.fillPrefOrder(utils, ballot, nSlots=1, lowSlot=1, remainderScore=0)
 118        return ballot
 119
 120    #
 121    # @classmethod
 122    # def xxstratBallot(cls, voter, polls, places, n,
 123    #                     frontId, frontResult, targId, targResult):
 124    #     """Takes utilities and returns a strategic ballot
 125    #     for the given "polling" info.
 126    #
 127    #     >>> Plurality().stratBallotFor([4,2,1])(Plurality, Voter([-4,-2,-1]))
 128    #     [0, 1, 0]
 129    #     """
 130    #     stratGap = voter[targId] - voter[frontId]
 131    #     if stratGap <= 0:
 132    #         #winner is preferred; be complacent.
 133    #         isStrat = False
 134    #         strat = cls.oneVote(voter, frontId)
 135    #     else:
 136    #         #runner-up is preferred; be strategic in iss run
 137    #         isStrat = True
 138    #         #sort cuts high to low
 139    #         #cuts = (cuts[1], cuts[0])
 140    #         strat = cls.oneVote(voter, targId)
 141    #     return dict(strat=strat, isStrat=isStrat, stratGap=stratGap)
 142
 143
 144def Score(topRank=10, asClass=False):
 145
 146    class Score0to(Method):
 147        """Score voting, 0-10.
 148
 149
 150        Strategy establishes pivots
 151            >>> Score().stratBallotFor([0,1,2])(Score, Voter([5,6,7]))
 152            [0, 0, 10]
 153            >>> Score().stratBallotFor([2,1,0])(Score, Voter([5,6,7]))
 154            [0, 10, 10]
 155            >>> Score().stratBallotFor([1,0,2])(Score, Voter([5,6,7]))
 156            [0, 5.0, 10]
 157
 158        Strategy (kinda) works for ties
 159            >>> Score().stratBallotFor([1,0,2])(Score, Voter([5,6,6]))
 160            [0, 10, 10]
 161            >>> Score().stratBallotFor([1,0,2])(Score, Voter([6,6,7]))
 162            [0, 0, 10]
 163            >>> Score().stratBallotFor([1,0,2])(Score, Voter([6,7,6]))
 164            [10, 10, 10]
 165            >>> Score().stratBallotFor([1,0,2])(Score, Voter([6,5,6]))
 166            [10, 0, 10]
 167
 168        """
 169
 170        # >>> qs += [Score().resultsFor(PolyaModel()(101,2),Score.honBallot)[0] for i in range(800)]
 171        # >>> std(qs)
 172        # 2.770135393419682
 173        # >>> mean(qs)
 174        # 5.1467202970297032
 175        bias2 = 2.770135393419682
 176        # >>> qs5 = [Score().resultsFor(PolyaModel()(101,5),Score.honBallot)[0] for i in range(400)]
 177        # >>> mean(qs5)
 178        # 4.920247524752476
 179        # >>> std(qs5)
 180        # 2.3536762480634343
 181        bias5 = 2.3536762480634343
 182        candScore = staticmethod(mean)
 183        # """Takes the list of votes for a candidate; returns the candidate's score."""
 184
 185        def __str__(self):
 186            if self.topRank == 1:
 187                return "IdealApproval"
 188            return self.__class__.__name__ + str(self.topRank)
 189
 190        @staticmethod  # cls is provided explicitly, not through binding
 191        @rememberBallot
 192        def honBallot(cls, utils):
 193            """Takes utilities and returns an honest ballot (on 0..10)
 194
 195
 196            honest ballots work as expected
 197                >>> Score().honBallot(Score, Voter([5,6,7]))
 198                [0.0, 5.0, 10.0]
 199                >>> Score().resultsFor(DeterministicModel(3)(5,3),Score().honBallot)["results"]
 200                [4.0, 6.0, 5.0]
 201            """
 202            bot = min(utils)
 203            scale = max(utils) - bot
 204            return [floor((cls.topRank + 0.99) * (util - bot) / scale) for util in utils]
 205
 206        @classmethod
 207        def fillStratBallot(
 208            cls,
 209            voter,
 210            polls,
 211            places,
 212            n,
 213            stratGap,
 214            ballot,
 215            frontId,
 216            frontResult,
 217            targId,
 218            targResult,
 219        ):
 220            """Returns a (function which takes utilities and returns a strategic ballot)
 221            for the given "polling" info."""
 222
 223            cuts = [voter[frontId], voter[targId]]
 224            if stratGap > 0:
 225                # sort cuts high to low
 226                cuts = (cuts[1], cuts[0])
 227            if cuts[0] == cuts[1]:
 228                strat = [(cls.topRank if (util >= cuts[0]) else 0) for util in voter]
 229            else:
 230                strat = [
 231                    max(
 232                        0,
 233                        min(
 234                            cls.topRank,
 235                            floor((cls.topRank + 0.99) * (util - cuts[1]) / (cuts[0] - cuts[1])),
 236                        ),
 237                    )
 238                    for util in voter
 239                ]
 240            for i in range(n):
 241                ballot[i] = strat[i]
 242
 243    Score0to.topRank = topRank
 244    return Score0to if asClass else Score0to()
 245
 246
 247def BulletyApprovalWith(bullets=0.5, asClass=False):
 248
 249    class BulletyApproval((Score(1, True))):
 250        bulletiness = bullets
 251
 252        def __str__(self):
 253            return f"BulletyApproval{str(round(self.bulletiness * 100))}"
 254
 255        @staticmethod  # cls is provided explicitly, not through binding
 256        @rememberBallot
 257        def honBallot(cls, utils):
 258            """Takes utilities and returns an honest ballot (on 0..10)
 259
 260
 261            honest ballots work as expected
 262                >>> Score().honBallot(Score, Voter([5,6,7]))
 263                [0.0, 5.0, 10.0]
 264                >>> Score().resultsFor(DeterministicModel(3)(5,3),Score().honBallot)["results"]
 265                [4.0, 6.0, 5.0]
 266            """
 267            if random.random() > cls.bulletiness:
 268                return cls.__bases__[0].honBallot(cls, utils)
 269            best = max(utils)
 270            return [1 if util == best else 0 for util in utils]
 271
 272    return BulletyApproval if asClass else BulletyApproval()
 273
 274
 275def Srv(topRank=10):
 276    """Score Runoff Voting
 277    >>> Srv().resultsFor(DeterministicModel(3)(5,3),Irv().honBallot)["results"]
 278    [1.2, 0.8, 1.21]
 279    >>> Srv().results([[0,1,2]])[2]
 280    2.0
 281    >>> Srv().results([[0,1,2],[2,1,0]])[1]
 282    1.0
 283    >>> Srv().results([[0,1,2]] * 4 + [[2,1,0]] * 3 + [[1,2,0]] * 2)
 284    [0.8888888888888888, 1.2222222222222223, 0.8888888888888888]
 285    >>> Srv().results([[2,1,0]] * 100 + [[1,0,2]] + [[0,2,1]] * 100)
 286    [1.502537313432836, 1.492537313432836, 0.5074626865671642]
 287    >>> Srv().results([[1,2,0]] * 8 + [[2,0,1]] * 6 + [[0,1,2]] * 5)
 288    [1.0526315789473684, 1.105263157894737, 0.8421052631578947]
 289    >>> Srv().results([[0,4,3,1,2]] * 5 + [[1,4,3,2,1]] * 4 + [[2,3,4,0,1]] * 6)
 290    [1.0666666666666667, 3.6, 3.4, 0.8666666666666667, 1.3333333333333333]
 291    """
 292
 293    score0to = Score(topRank, True)
 294
 295    class Srv0to(score0to):
 296        stratTargetFor = Method.stratTarget3
 297
 298        def results(self, ballots, **kwargs):
 299            """Srv results."""
 300            ballots = ballots_from_dataframe(ballots)
 301            baseResults = super(Srv0to, self).results(ballots, **kwargs)
 302            (runnerUp, top) = sorted(range(len(baseResults)), key=lambda i: baseResults[i])[-2:]
 303            upset = sum(sign(ballot[runnerUp] - ballot[top]) for ballot in ballots)
 304            if upset > 0:
 305                baseResults[runnerUp] = baseResults[top] + 0.01
 306            return baseResults
 307
 308    return Srv0to()
 309
 310
 311def toVote(cutoffs, util):
 312    """maps one util to a vote, using cutoffs.
 313
 314    Used by Mav, but declared outside to avoid method binding overhead."""
 315    for vote in range(len(cutoffs)):
 316        if util <= cutoffs[vote]:
 317            return vote
 318    return vote + 1
 319
 320
 321class Mav(Method):
 322    """Majority Approval Voting"""
 323
 324    # >>> mqs = [Mav().resultsFor(PolyaModel()(101,5),Mav.honBallot)[0] for i in range(400)]
 325    # >>> mean(mqs)
 326    # 1.5360519801980208
 327    # >>> mqs += [Mav().resultsFor(PolyaModel()(101,5),Mav.honBallot)[0] for i in range(1200)]
 328    # >>> mean(mqs)
 329    # 1.5343069306930679
 330    # >>> std(mqs)
 331    # 1.0970202515275356
 332    bias5 = 1.0970202515275356
 333
 334    baseCuts = [-0.8, 0, 0.8, 1.6]
 335    specificCuts = None
 336    specificPercentiles = [25, 50, 75, 90]
 337
 338    def candScore(self, scores):
 339        """For now, only works correctly for odd nvot
 340
 341        Basic tests
 342            >>> Mav().candScore([1,2,3,4,5])
 343            3.0
 344            >>> Mav().candScore([1,2,3,3,3])
 345            2.5
 346            >>> Mav().candScore([1,2,3,4])
 347            2.5
 348            >>> Mav().candScore([1,2,3,3])
 349            2.5
 350            >>> Mav().candScore([1,2,2,2])
 351            1.5
 352            >>> Mav().candScore([1,2,3,3,5])
 353            2.7
 354        """
 355        scores = sorted(scores)
 356        nvot = len(scores)
 357        nGrades = len(self.baseCuts) + 1
 358        i = int((nvot - 1) / 2)
 359        base = scores[i]
 360        while i < nvot and scores[i] == base:
 361            i += 1
 362        upper = (base + 0.5) - (i - nvot / 2) * nGrades / nvot
 363        lower = (base) - (i - nvot / 2) / nvot
 364        return max(upper, lower)
 365
 366    @classmethod
 367    def honBallotFor(cls, voters):
 368        cls.specificCuts = percentile(voters, cls.specificPercentiles)
 369        return cls.honBallot
 370
 371    @staticmethod  # cls is provided explicitly, not through binding
 372    @rememberBallot
 373    def honBallot(cls, voter):
 374        """Takes utilities and returns an honest ballot (on 0..4)
 375
 376        honest ballot works as intended, gives highest grade to highest utility:
 377            >>> Mav().honBallot(Mav, Voter([-1,-0.5,0.5,1,1.1]))
 378            [0, 1, 2, 3, 4]
 379
 380        Even if they don't rate at least an honest "B":
 381            >>> Mav().honBallot(Mav, Voter([-1,-0.5,0.5]))
 382            [0, 1, 4]
 383        """
 384        cuts = cls.specificCuts if (cls.specificCuts is not None) else cls.baseCuts
 385        cuts = [min(cut, max(voter) - 0.001) for cut in cuts]
 386        return [toVote(cuts, util) for util in voter]
 387
 388    def stratBallotFor(self, polls):
 389        """Returns a function which takes utilities and returns a dict(
 390            strat=<ballot in which all grades are exaggerated
 391                             to outside the range of the two honest frontrunners>,
 392            extraStrat=<ballot in which all grades are exaggerated to extremes>,
 393            isStrat=<whether the runner-up is preferred to the frontrunner (for reluctantStrat)>,
 394            stratGap=<utility of runner-up minus that of frontrunner>
 395            )
 396        for the given "polling" info.
 397
 398
 399
 400        Strategic tests:
 401            >>> Mav().stratBallotFor([0,1.1,1.9,0,0])(Mav, Voter([-1,-0.5,0.5,1,2]))
 402            [0, 1, 2, 3, 4]
 403            >>> Mav().stratBallotFor([0,2.1,2.9,0,0])(Mav, Voter([-1,-0.5,0.5,1,2]))
 404            [0, 1, 3, 3, 4]
 405            >>> Mav().stratBallotFor([0,2.1,1.9,0,0])(Mav, Voter([-1,0.4,0.5,1,2]))
 406            [0, 1, 3, 3, 4]
 407            >>> Mav().stratBallotFor([1,0,2])(Mav, Voter([6,7,6]))
 408            [4, 4, 4]
 409            >>> Mav().stratBallotFor([1,0,2])(Mav, Voter([6,5,6]))
 410            [4, 0, 4]
 411            >>> Mav().stratBallotFor([2.1,0,3])(Mav, Voter([6,5,6]))
 412            [4, 0, 4]
 413            >>> Mav().stratBallotFor([2.1,0,3])(Mav, Voter([6,5,6.1]))
 414            [2, 2, 4]
 415        """
 416        places = sorted(enumerate(polls), key=lambda x: -x[1])  # from high to low
 417        # print("places",places)
 418        ((frontId, frontResult), (targId, targResult)) = places[:2]
 419
 420        @rememberBallots
 421        def stratBallot(cls, voter):
 422            frontUtils = [voter[frontId], voter[targId]]  # utils of frontrunners
 423            stratGap = frontUtils[1] - frontUtils[0]
 424            if stratGap == 0:
 425                strat = extraStrat = [(4 if (util >= frontUtils[0]) else 0) for util in voter]
 426                isStrat = True
 427
 428            else:
 429                if stratGap < 0:
 430                    # winner is preferred; be complacent.
 431                    isStrat = False
 432                else:
 433                    # runner-up is preferred; be strategic in iss run
 434                    isStrat = True
 435                    # sort cuts high to low
 436                    frontUtils = (frontUtils[1], frontUtils[0])
 437                top = max(voter)
 438                # print("lll312")
 439                # print(self.baseCuts, front)
 440                cutoffs = [
 441                    (
 442                        (min(frontUtils[0], self.baseCuts[i]))
 443                        if (i < floor(targResult))
 444                        else (
 445                            (frontUtils[1])
 446                            if (i < floor(frontResult) + 1)
 447                            else min(top, self.baseCuts[i])
 448                        )
 449                    )
 450                    for i in range(len(self.baseCuts))
 451                ]
 452                strat = [toVote(cutoffs, util) for util in voter]
 453                extraStrat = [
 454                    max(
 455                        0,
 456                        min(
 457                            10,
 458                            floor(4.99 * (util - frontUtils[1]) / (frontUtils[0] - frontUtils[1])),
 459                        ),
 460                    )
 461                    for util in voter
 462                ]
 463            return dict(strat=strat, extraStrat=extraStrat, isStrat=isStrat, stratGap=stratGap)
 464
 465        return stratBallot
 466
 467
 468class Mj(Mav):
 469    def candScore(self, scores):
 470        """This formula will always give numbers within 0.5 of the raw median.
 471        Unfortunately, with 5 grade levels, these will tend to be within 0.1 of
 472        the raw median, leaving scores further from the integers mostly unused.
 473        This is only a problem aesthetically.
 474
 475        For now, only works correctly for odd nvot
 476
 477        tests:
 478            >>> Mj().candScore([1,2,3,4,5])
 479            3
 480            >>> Mj().candScore([1,2,3,3,5])
 481            2.7
 482            >>> Mj().candScore([1,3,3,3,5])
 483            3
 484            >>> Mj().candScore([1,3,3,4,5])
 485            3.3
 486            >>> Mj().candScore([1,3,3,3,3])
 487            2.9
 488            >>> Mj().candScore([3] * 24 + [1])
 489            2.98
 490            >>> Mj().candScore([3] * 24 + [4])
 491            3.02
 492            >>> Mj().candScore([3] * 13 + [4] * 12)
 493            3.46
 494        """
 495        scores = sorted(scores)
 496        nvot = len(scores)
 497        lo = hi = mid = nvot // 2
 498        base = scores[mid]
 499        while hi < nvot and scores[hi] == base:
 500            hi += 1
 501        while lo >= 0 and scores[lo] == base:
 502            lo -= 1
 503
 504        if (hi - mid) == (mid - lo):
 505            return base
 506        elif (hi - mid) < (mid - lo):
 507            return base + 0.5 - (hi - mid) / nvot
 508        else:
 509            return base - 0.5 + (mid - lo) / nvot
 510
 511
 512class Irv(Method):
 513    """
 514    IRV.
 515
 516    Ballots are ordered candidate rankings, from most to least preferred.
 517    Results are candidate-indexed elimination ranks, with higher numbers better.
 518    """
 519
 520    stratTargetFor = Method.stratTarget3
 521
 522    def buildPreferenceSchedule(self, ballots):
 523        """Gets a dictionary of the form {ranking as tuple, vote count}"""
 524
 525        prefs = {}
 526        for b in ballots:
 527            key = tuple(b)
 528            if key in prefs:
 529                prefs[key] += 1
 530            else:
 531                prefs[key] = 1
 532        return prefs
 533
 534    def eliminateCandidate(self, inputPrefs, toEliminate):
 535        """Gets a dictionary of the form {ranking as tuple, vote count} with toEliminate removed"""
 536
 537        if not isinstance(toEliminate, CandidateWithCount):
 538            return inputPrefs
 539
 540        prefs = {}
 541        for ranking, votes in inputPrefs.items():
 542            newranking = [candidate for candidate in ranking if candidate != toEliminate.candidate]
 543
 544            if not newranking:
 545                continue
 546            newkey = tuple(newranking)
 547            if newkey in prefs:
 548                prefs[newkey] += votes
 549            else:
 550                prefs[newkey] = votes
 551        return prefs
 552
 553    def candidateVotes(self, prefSchedule):
 554        """Gets a list of CandidateWithCount, from highest to lowest"""
 555        candidates = {}
 556        for ranking, votes in prefSchedule.items():
 557            candidate = ranking[0]
 558            if candidate in candidates:
 559                candidates[candidate].votes += votes
 560            else:
 561                candidates[candidate] = CandidateWithCount(candidate, votes)
 562
 563        # Simply for VSE which requires ranking of non-winners; in real election we don't really
 564        # care
 565        alternates = []
 566        trackedalt = set()
 567        for ranking, votes in prefSchedule.items():
 568            for alternate in ranking[1:]:
 569                if (alternate not in candidates) and alternate not in trackedalt:
 570                    alternates.append(CandidateWithCount(alternate, 0))
 571                    trackedalt.add(alternate)
 572
 573        return (
 574            sorted(candidates.values(), key=lambda c: (c.votes, c.candidate), reverse=True)
 575            + alternates
 576        )
 577
 578    def getLeast(self, voteRanking, keep=None):
 579        if keep is None:
 580            keep = {}
 581        for candidate in reversed(voteRanking):
 582            if candidate.candidate not in keep:
 583                return candidate
 584        return None
 585
 586    @staticmethod
 587    def scoresFromEliminations(eliminated, ncand):
 588        """Convert an IRV elimination order to candidate-indexed scores."""
 589        results = [-1] * ncand
 590        for score, candidate in enumerate(eliminated):
 591            results[candidate] = score
 592        return results
 593
 594    def runIrv(self, remaining, ncand):
 595        """IRV results."""
 596        eliminated = []
 597        for _ in range(ncand):
 598            votes = self.candidateVotes(remaining)
 599            toEliminate = self.getLeast(votes)
 600            if not isinstance(toEliminate, CandidateWithCount):
 601                break
 602            eliminated.append(toEliminate.candidate)
 603            remaining = self.eliminateCandidate(remaining, toEliminate)
 604        return self.scoresFromEliminations(eliminated, ncand)
 605
 606    def results(self, ballots, **kwargs):
 607        """IRV results.
 608
 609        >>> Irv().resultsFor(DeterministicModel(3)(5,3),Irv().honBallot)["results"]
 610        [0, 1, 2]
 611        >>> Irv().results([[0,1,2]])[2]
 612        0
 613        >>> Irv().results([[0,1,2],[2,1,0]])[1]
 614        0
 615        >>> Irv().results([[0,1,2]] * 4 + [[2,1,0]] * 3 + [[1,2,0]] * 2)
 616        [1, 0, 2]
 617        """
 618        ballots = ballots_from_dataframe(ballots)
 619        return self.runIrv(self.buildPreferenceSchedule(ballots), len(ballots[0]))
 620
 621    @staticmethod  # cls is provided explicitly, not through binding
 622    @rememberBallot
 623    def honBallot(cls, voter):
 624        """Takes utilities and returns an honest ballot
 625
 626        >>> Irv.honBallot(Irv,Voter([4,1,6,3]))
 627        [2, 0, 3, 1]
 628        >>> Irv.honBallot(Irv,Voter([0,1,2]))
 629        [2, 1, 0]
 630        """
 631        order = sorted(enumerate(voter), key=lambda x: (-x[1], x[0]))
 632        return [candidate for candidate, _utility in order]
 633
 634    @classmethod
 635    def fillStratBallot(
 636        cls,
 637        voter,
 638        polls,
 639        places,
 640        n,
 641        stratGap,
 642        ballot,
 643        frontId,
 644        frontResult,
 645        targId,
 646        targResult,
 647    ):
 648        """
 649        >>> Irv().stratBallotFor([3,2,1,0])(Irv,Voter([3,6,5,2]))
 650        [2, 1, 0, 3]
 651        """
 652        i = n - 1
 653        winnerQ = voter[frontId]
 654        targQ = voter[targId]
 655        placesToFill = list(range(n - 1, 0, -1))
 656        if targQ > winnerQ:
 657            ballot[targId] = i
 658            i -= 1
 659            del placesToFill[-2]
 660        for j in placesToFill:
 661            nextLoser, loserScore = places[j]  # all but winner, low to high
 662            if voter[nextLoser] > winnerQ:
 663                ballot[nextLoser] = i
 664                i -= 1
 665        ballot[frontId] = i
 666        i -= 1
 667        for j in placesToFill:
 668            nextLoser, loserScore = places[j]
 669            if voter[nextLoser] <= winnerQ:
 670                ballot[nextLoser] = i
 671                i -= 1
 672        assert i == -1
 673        ballot[:] = [
 674            candidate for candidate, _rank in sorted(enumerate(ballot), key=lambda x: -x[1])
 675        ]
 676
 677
 678class IrvPrime(Irv):
 679    """
 680    IRV Prime.
 681
 682    See https://electowiki.org/wiki/IRV_Prime
 683    """
 684
 685    stratTargetFor = Method.stratTarget3
 686
 687    def results(self, ballots, **kwargs):
 688        """IRV Prime results.
 689
 690        >>> IrvPrime().results([[0,1,2]])[2]
 691        0
 692        >>> IrvPrime().results([[0,1,2],[2,1,0]])[1]
 693        0
 694        >>> IrvPrime().results([[0,1,2]] * 4 + [[2,1,0]] * 3 + [[1,2,0]] * 2)
 695        [0, 2, 1]
 696        >>> IrvPrime().results([[2,1,0]] * 100 + [[1,0,2]] + [[0,2,1]] * 100)
 697        [1, 2, 0]
 698        >>> # Favorite betrayal example from http://rangevoting.org/IncentToExagg.html
 699        >>> IrvPrime().results([[1,2,0]] * 8 + [[2,0,1]] * 6 + [[0,1,2]] * 5)
 700        [2, 1, 0]
 701        >>> IrvPrime().results([[0,4,3,1,2]] * 5 + [[1,4,3,2,1]] * 4 + [[2,3,4,0,1]] * 6)
 702        [1, 0, 3, 2, 4]
 703        >>> # Elections 3-5 from http://votingmatters.org.uk/ISSUE6/P4.HTM
 704        >>> IrvPrime().results([[0,1,2,3,4,5]] * 12 + [[2,0,1,3,4,5]] * 11 + [[1,2,0,3,4,5]] * 10 +
 705        ...     [[3,4,5]] * 27)
 706        [2, 5, 4, 3, 1, 0]
 707        >>> IrvPrime().results([[0,1]] * 11 + [[1]] * 7 + [[2]] * 12)
 708        [0, 2, 1]
 709        >>> IrvPrime().results([[0,3,2,1]] * 5 + [[1,2,0,3]] * 5 + [[2,0,1,3]] * 8 +
 710        ...    [[3,0,1,2]] * 4 + [[3,1,2,0]] * 8)
 711        [3, 0, 1, 2]
 712        >>> IrvPrime().results([[0,2,1,3]] * 6 + [[0,3,1,2]] * 3 + [[0,3,2,1]] * 3 +
 713        ...     [[1,2,0,3]] * 4 + [[2,0,1,3]] * 4 + [[3,1,2,0]] * 5)
 714        [2, 0, 3, 1]
 715        >>> # Failure of later-no-harm
 716        >>> IrvPrime().results([[0, 1, 2]] * 32 + [[0, 2, 1]] * 20 + [[1,2,0]] * 30 +
 717        ...     [[1,0,2]] * 21 + [[2,0,1]] * 30 + [[2,1,0]] * 20)
 718        [1, 0, 2]
 719        >>> IrvPrime().results([[0, 1, 2]] * 32 + [[0, 2, 1]] * 20 + [[1,2,0]] * 30 +
 720        ...     [[1,0,2]] * 21 + [[2,1,0]] * 30 + [[2,1,0]] * 20)
 721        [1, 2, 0]
 722        """
 723
 724        ballots = ballots_from_dataframe(ballots)
 725
 726        remaining = self.buildPreferenceSchedule(ballots)
 727        ncand = len(self.candidateVotes(remaining))
 728        classic = self.runIrv(remaining, ncand)
 729
 730        # Keep the winner from the classic IRV
 731        winners = {self.winner(classic)}
 732
 733        # Find all candidates that can beat classic IRV winner; this may be a superset
 734        # of schwartz/smith, but it's all that matters
 735        winnersPrime = set()
 736        for possibleWinner in range(ncand):
 737            if possibleWinner in winners:
 738                continue
 739
 740            numWins = 0
 741            numLosses = 0
 742            for ranking, votes in remaining.items():
 743                possibleWinnerRanking = winnerRanking = len(ranking) + 1
 744                for pos in range(len(ranking)):
 745                    if ranking[pos] == possibleWinner:
 746                        possibleWinnerRanking = pos
 747                    # We can change this to a loop if there's > 1 winner
 748                    elif ranking[pos] == next(iter(winners)):
 749                        winnerRanking = pos
 750                if possibleWinnerRanking < winnerRanking:
 751                    numWins += votes
 752                elif winnerRanking < possibleWinnerRanking:
 753                    numLosses += votes
 754            if numWins > numLosses:
 755                winnersPrime.add(possibleWinner)
 756
 757        # Now re-run IRV preserving all winners + winners prime
 758        keepers = winners.union(winnersPrime)
 759        eliminated = []
 760        for _ in range(ncand):
 761            votes = self.candidateVotes(remaining)
 762            toEliminate = self.getLeast(votes, keepers)
 763            if not isinstance(toEliminate, CandidateWithCount):
 764                # Begin "step 4", i.e. continue elimination without preserving anyone
 765                keepers = {}
 766                toEliminate = self.getLeast(votes)
 767            if not isinstance(toEliminate, CandidateWithCount):
 768                break
 769            eliminated.append(toEliminate.candidate)
 770            remaining = self.eliminateCandidate(remaining, toEliminate)
 771
 772        return self.scoresFromEliminations(eliminated, ncand)
 773
 774
 775class V321(Mav):
 776    baseCuts = [-0.1, 0.8]
 777    specificPercentiles = [45, 75]
 778
 779    stratTargetFor = Method.stratTarget3
 780
 781    def results(self, ballots, isHonest=False, **kwargs):
 782        """3-2-1 Voting results.
 783
 784        >>> V321().resultsFor(DeterministicModel(3)(5,3),V321().honBallot)["results"]
 785        [-0.75, 2, 1]
 786        >>> V321().results([[0,1,2]])[2]
 787        2
 788        >>> V321().results([[0,1,2],[2,1,0]])[1]
 789        2.5
 790        >>> V321().results([[0,1,2]] * 4 + [[2,1,0]] * 3 + [[1,2,0]] * 2)
 791        [1, 1.5, -0.25]
 792        >>> V321().results([[0,1,2,1]]*29 + [[1,2,0,1]]*30 + [[2,0,1,1]]*31 + [[1,1,1,2]]*10)
 793        [3, 0.5, 1, 0]
 794        >>> V321().results([[1,0,2,1]]*29 + [[0,2,1,1]]*30 + [[2,1,0,1]]*31 + [[1,1,1,2]]*10)
 795        [3.375, 2.875, 0.25, 0]
 796        """
 797        ballots = ballots_from_dataframe(ballots)
 798        candScores = list(zip(*ballots))
 799        n2s = [sum(1 if s > 1 else 0 for s in c) for c in candScores]
 800        o2s = argsort(n2s)  # order
 801        r2s = [-1] * len(n2s)  # ranks
 802        for r, i in enumerate(o2s):
 803            r2s[i] = r
 804        semifinalists = o2s[-3:]  # [third, second, first] by top ranks
 805        # print(semifinalists)
 806        n1s = [sum(1 if s > 0 else 0 for s in candScores[sf]) for sf in semifinalists]
 807        o1s = argsort(n1s)
 808        # print("n1s",n1s)
 809        # print("o1s",o1s)
 810        # print([semifinalists[o] for o in o1s]) #[third, second, first] by above-bottom
 811        # print("r2s",r2s)
 812        r2s[semifinalists[o1s[0]]] -= (o1s[0] + 1) * 0.75  # non-finalist below finalists
 813
 814        (runnerUp, top) = semifinalists[o1s[1]], semifinalists[o1s[2]]
 815        upset = sum(sign(ballot[runnerUp] - ballot[top]) for ballot in ballots)
 816        if upset > 0:
 817            runnerUp, top = top, runnerUp
 818            r2s[runnerUp], r2s[top] = r2s[top] - 0.125, r2s[runnerUp] + 0.125
 819        r2s[top] = max(r2s[top], r2s[runnerUp] + 0.5)
 820        if isHonest:
 821            upset2 = sum(
 822                sign(ballot[semifinalists[o1s[0]]] - ballot[semifinalists[o1s[2]]])
 823                for ballot in ballots
 824            )
 825            self.__class__.extraEvents["3beats1"] = upset2 > 0
 826            upset3 = sum(
 827                sign(ballot[semifinalists[o1s[0]]] - ballot[semifinalists[o1s[1]]])
 828                for ballot in ballots
 829            )
 830            self.__class__.extraEvents["3beats2"] = upset3 > 0
 831            if len(o2s) > 3:
 832                fourth = o2s[-4]
 833                fourthNotLasts = sum(1 if s > 1 else 0 for s in candScores[fourth])
 834                fourthWin = (
 835                    fourthNotLasts > n1s[o1s[1]]
 836                    and sum(
 837                        sign(ballot[fourth] - ballot[semifinalists[o1s[2]]]) for ballot in ballots
 838                    )
 839                    > 0
 840                )
 841                self.__class__.extraEvents["4beats1"] = fourthWin
 842
 843        return [as_builtin_scalar(score) for score in r2s]
 844
 845    def stratBallotFor(self, polls):
 846        """Returns a function which takes utilities and returns a dict(
 847            isStrat=
 848        for the given "polling" info.
 849
 850
 851        >>> Irv().stratBallotFor([3,2,1,0])(Irv,Voter([3,6,5,2]))
 852        [2, 1, 0, 3]
 853        """
 854        places = sorted(enumerate(polls), key=lambda x: -x[1])  # high to low
 855        top3 = [c for c, r in places[:3]]
 856
 857        # @rememberBallots ... do it later
 858        def stratBallot(cls, voter):
 859            stratGap = voter[top3[1]] - voter[top3[0]]
 860            myPrefs = [c for c, v in sorted(enumerate(voter), key=lambda x: -x[1])]  # high to low
 861            my3order = [myPrefs.index(c) for c in top3]
 862            rating = 2
 863            ballot = [0] * len(voter)
 864            if my3order[0] == min(my3order):  # agree on winner
 865                for i in range(my3order[0] + 1):
 866                    ballot[myPrefs[i]] = 2
 867                if my3order[1] <= my3order[2]:
 868                    for i in range(my3order[0] + 1, my3order[1] + 1):
 869                        ballot[myPrefs[i]] = 1
 870                # print("agree",top3, my3order,ballot,[float('%.1g' % c) for c in voter])
 871                return dict(strat=ballot, isStrat=False, stratGap=stratGap)
 872            for c in myPrefs:
 873                ballot[c] = rating
 874                if rating and (c in top3):
 875                    if c == top3[0]:
 876                        rating = 0
 877                    else:
 878                        rating -= 1
 879
 880            # print("disagree",top3,my3order,ballot,[float('%.1g' % c) for c in voter])
 881            return dict(strat=ballot, isStrat=True, stratGap=stratGap)
 882
 883        if self.extraEvents["3beats1"]:
 884
 885            @rememberBallots
 886            def stratBallo2(cls, voter):
 887                myprefs = sorted(enumerate(voter), key=lambda x: -x[1])  # high to low
 888                rating = 2
 889                ballot = [None] * len(voter)
 890                isStrat = False
 891                stratGap = 0
 892                for c, util in myprefs:
 893                    ballot[c] = rating
 894                    if rating and (c in top3):
 895                        if c == top3[2]:
 896                            rating = 0
 897                        else:
 898                            rating -= 1
 899                isStrat = voter[top3[0]] == max(voter[c] for c in top3)
 900                return dict(strat=ballot, isStrat=isStrat, stratGap=stratGap)
 901
 902            stratBallo2.__name__ = "stratBallot"  # God, that's ugly.
 903            return stratBallo2
 904
 905        if self.extraEvents["4beats1"]:
 906            fourth = places[3][0]
 907            first = top3[1]
 908
 909            @rememberBallots
 910            def stratBallo3(cls, voter):
 911                stratGap = voter[top3[1]] - voter[top3[0]]
 912                myprefs = sorted(enumerate(voter), key=lambda x: -x[1])  # high to low
 913
 914                rating = 2
 915                ballot = [None] * len(voter)
 916                if voter[fourth] > voter[first]:
 917                    for c, util in myprefs:
 918                        ballot[c] = rating
 919                        if rating and (c == fourth):
 920                            rating -= 2
 921                    return dict(strat=ballot, isStrat=True, stratGap=stratGap)
 922
 923                return stratBallot(cls, voter)
 924
 925            stratBallo3.__name__ = "stratBallot"  # God, that's ugly.
 926            return stratBallo3
 927
 928        return rememberBallots(stratBallot)
 929
 930
 931class Schulze(RankedMethod):
 932    def resolveCycle(self, cmat, n):
 933
 934        beatStrength = [[0] * n] * n
 935        numWins = [0] * n
 936        for i in range(n):
 937            for j in range(n):
 938                if i != j:
 939                    beatStrength[i][j] = cmat[i][j] if cmat[i][j] > cmat[j][i] else 0
 940
 941                for pivot in range(n):
 942                    for source in range(n):
 943                        if pivot != source:
 944                            for target in range(n):
 945                                if pivot != target and source != target:
 946                                    beatStrength[source][target] = max(
 947                                        beatStrength[source][target],
 948                                        min(
 949                                            beatStrength[source][pivot],
 950                                            beatStrength[pivot][target],
 951                                        ),
 952                                    )
 953
 954        for i in range(n):
 955            for j in range(n):
 956                if i != j:
 957                    if beatStrength[i][j] > beatStrength[j][i]:
 958                        numWins[i] += 1
 959                    if (
 960                        beatStrength[i][j] == beatStrength[j][i] and i < j
 961                    ):  # break ties deterministically
 962                        numWins[i] += 1
 963
 964        return numWins
 965
 966    def results(self, ballots, isHonest=False, **kwargs):
 967        """Schulze results.
 968
 969        >>> Schulze().resultsFor(DeterministicModel(3)(5,3),Schulze().honBallot,isHonest=True)["results"]
 970        [2, 0, 1]
 971        >>> Schulze.extraEvents
 972        {'scenario': 'cycle'}
 973        >>> Schulze().results([[0,1,2]],isHonest=True)[2]
 974        2
 975        >>> Schulze.extraEvents
 976        {'scenario': 'easy'}
 977        >>> Schulze().results([[0,1,2],[2,1,0]],isHonest=True)[1]
 978        1
 979        >>> Schulze.extraEvents
 980        {'scenario': 'easy'}
 981        >>> Schulze().results([[0,1,2]] * 4 + [[2,1,0]] * 3 + [[1,2,0]] * 2,isHonest=True)
 982        [1, 2, 0]
 983        >>> Schulze.extraEvents
 984        {'scenario': 'chicken'}
 985        >>> Schulze().results([[0,1,2]] * 4 + [[2,1,0]] * 2 + [[1,2,0]] * 3,isHonest=True)
 986        [1, 2, 0]
 987        >>> Schulze.extraEvents
 988        {'scenario': 'squeeze'}
 989        >>> Schulze().results([[3,2,1,0]] * 5 + [[2,3,1,0]] * 2 + [[0,1,0,3]] * 6 + [[0,0,3,0]] * 3,isHonest=True)
 990        [2, 3, 1, 0]
 991        >>> Schulze.extraEvents
 992        {'scenario': 'other'}
 993        >>> Schulze().results([[3,0,0,0]] * 5 + [[2,3,0,0]] * 2 + [[0,0,0,3]] * 6 + [[0,0,3,0]] * 3,isHonest=True)
 994        [3, 0, 1, 2]
 995        >>> Schulze.extraEvents
 996        {'scenario': 'spoiler'}
 997        """
 998        ballots = ballots_from_dataframe(ballots)
 999        n = len(ballots[0])
1000        cmat = [[0 for _ in range(n)] for _ in range(n)]
1001        numWins = [0] * n
1002        for i in range(n):
1003            for j in range(n):
1004                if i != j:
1005                    cmat[i][j] = sum(sign(ballot[i] - ballot[j]) for ballot in ballots)
1006                    if cmat[i][j] > 0:
1007                        numWins[i] += 1
1008                    elif cmat[i][j] == 0 and i < j:
1009                        numWins[i] += 1
1010        condOrder = sorted(enumerate(numWins), key=lambda x: -x[1])
1011        if condOrder[0][1] == n - 1:
1012            cycle = 0
1013            result = numWins
1014        else:  # cycle
1015            cycle = 1
1016            result = self.resolveCycle(cmat, n)
1017
1018        if isHonest:
1019            self.__class__.extraEvents = {}
1020            # check scenarios
1021            plurTally = [0] * n
1022            plur3Tally = [0] * 3
1023            cond3 = [c for c, v in condOrder[:3]]
1024            for b in ballots:
1025                b3 = [b[c] for c in cond3]
1026                plurTally[b.index(max(b))] += 1
1027                plur3Tally[b3.index(max(b3))] += 1
1028            plurOrder = sorted(enumerate(plurTally), key=lambda x: -x[1])
1029            plur3Order = sorted(enumerate(plur3Tally), key=lambda x: -x[1])
1030            if cycle:
1031                self.__class__.extraEvents["scenario"] = "cycle"
1032            elif plurOrder[0][0] == condOrder[0][0]:
1033                self.__class__.extraEvents["scenario"] = "easy"
1034            elif plur3Order[0][0] == condOrder[0][0]:
1035                self.__class__.extraEvents["scenario"] = "spoiler"
1036            elif plur3Order[2][0] == condOrder[0][0]:
1037                self.__class__.extraEvents["scenario"] = "squeeze"
1038            elif plur3Order[0][0] == condOrder[2][0]:
1039                self.__class__.extraEvents["scenario"] = "chicken"
1040            else:
1041                self.__class__.extraEvents["scenario"] = "other"
1042
1043        return result
1044
1045    @classmethod
1046    def fillStratBallot(
1047        cls,
1048        voter,
1049        polls,
1050        places,
1051        n,
1052        stratGap,
1053        ballot,
1054        frontId,
1055        frontResult,
1056        targId,
1057        targResult,
1058    ):
1059
1060        if stratGap > 0:
1061            others = [c for (c, r) in places[2:]]
1062            notTooBad = min(voter[frontId], voter[targId])
1063            decentOnes = [c for c in others if voter[c] >= notTooBad]
1064            cls.fillPrefOrder(voter, ballot, whichCands=decentOnes, lowSlot=n - len(decentOnes))
1065            # ballot[frontId], ballot[targId] = n-len(decentOnes)-1, n-len(decentOnes)-2
1066            ballot[frontId], ballot[targId] = 0, n - len(decentOnes) - 1
1067            cls.fillPrefOrder(
1068                voter,
1069                ballot,
1070                whichCands=[c for c in others if voter[c] < notTooBad],
1071                lowSlot=1,
1072            )
1073        else:
1074            ballot[frontId] = n - 1
1075            cls.fillPrefOrder(voter, ballot, whichCands=[c for (c, r) in places[1:]], lowSlot=0)
1076
1077
1078class Rp(Schulze):
1079    def resolveCycle(self, cmat, n):
1080        """Note: mutates cmat destructively.
1081
1082        >>> Rp().resultsFor(DeterministicModel(3)(5,3),Rp().honBallot,isHonest=True)["results"]
1083        [1, 2, 0]
1084        """
1085        matches = [(i, j, cmat[i][j]) for i in range(n) for j in range(i, n) if i != j]
1086        rps = sorted(matches, key=lambda x: -abs(x[2]))
1087        for i, j, margin in rps:
1088            if margin < 0:
1089                i, j = j, i
1090            if cmat[j][i] is not True:
1091                # print(i,j,cmat)
1092                cmat[i][j] = True
1093                # print("....",i,j,cmat)
1094                for k in range(n):
1095                    if k not in (i, j):
1096                        if cmat[j][k] is True:
1097                            cmat[i][k] = True
1098                        if cmat[k][i] is True:
1099                            cmat[k][j] = True
1100
1101                            # print(".......",i,j,k,cmat)
1102
1103        return [sum(cmat[i][j] is True for j in range(n)) for i in range(n)]
1104
1105
1106class IRNR(RankedMethod):
1107    stratMax = 10
1108
1109    stratTargetFor = Method.stratTarget3  # strategize in favor of third place, because second place is pointless (can't change pairwise)
1110
1111    def results(self, ballots, **kwargs):
1112        ballots = ballots_from_dataframe(ballots)
1113        enabled = [True] * len(ballots[0])
1114        numEnabled = sum(enabled)
1115        results = [None] * len(enabled)
1116        while numEnabled > 1:
1117            tsum = [0.0] * len(enabled)
1118            for bal in ballots:
1119                vsum = 0.0
1120                for i, v in enumerate(bal):
1121                    if enabled[i]:
1122                        vsum += abs(v)
1123                if vsum == 0.0:
1124                    # TODO: count spoiled ballot
1125                    continue
1126                for i, v in enumerate(bal):
1127                    if enabled[i]:
1128                        tsum[i] += v / vsum
1129            mini = None
1130            minv = None
1131            for i, v in enumerate(tsum):
1132                if enabled[i] and ((minv is None) or (tsum[i] < minv)):
1133                    minv = tsum[i]
1134                    mini = i
1135            enabled[mini] = False
1136            results[mini] = minv
1137            numEnabled -= 1
1138        for i, v in enumerate(tsum):
1139            if enabled[i]:
1140                results[i] = tsum[i]
1141        return results
1142
1143    @staticmethod  # cls is provided explicitly, not through binding
1144    @rememberBallot
1145    def honBallot(cls, utils):
1146        """Takes utilities and returns an honest ballot"""
1147        return utils
1148
1149    @classmethod
1150    def fillStratBallot(
1151        cls,
1152        voter,
1153        polls,
1154        places,
1155        n,
1156        stratGap,
1157        ballot,
1158        frontId,
1159        frontResult,
1160        targId,
1161        targResult,
1162    ):
1163        if stratGap <= 0:
1164            ballot[frontId], ballot[targId] = cls.stratMax, 0
1165        else:
1166            ballot[frontId], ballot[targId] = 0, cls.stratMax
1167        cls.fillPrefOrder(
1168            voter,
1169            ballot,
1170            whichCands=[c for (c, r) in places[2:]],
1171            nSlots=1,
1172            lowSlot=1,
1173            remainderScore=0,
1174        )
1175
1176
1177__all__ = [
1178    "Borda",
1179    "BulletyApprovalWith",
1180    "IRNR",
1181    "Irv",
1182    "IrvPrime",
1183    "Mav",
1184    "Mj",
1185    "Plurality",
1186    "RankedMethod",
1187    "RatedMethod",
1188    "Rp",
1189    "Schulze",
1190    "Score",
1191    "Srv",
1192    "V321",
1193    "toVote",
1194]