[EM] Preliminary simulation of fpA-{sum, max} fpC and compromise vs burial incentive

Forest Simmons forest.simmons21 at gmail.com
Fri Nov 25 21:02:24 PST 2022


On Fri, Nov 25, 2022, 8:25 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> Kristofer,
>
> It seems to me that it might be worth the cost of an extra pass through
> the ballots (after the pairwise wins have been ascertained) to fix the
> "no-first-preference" problem: just use, in place of the number (or
> percentage) of the ballots on which candidate X is ranked in first place,
> the number (or percentage) of the ballots on which X
>

is the lowest ranked candidate that

covers every candidate ranked ahead of it.
>
> We could call such a candidate X the minimal prudent compromise (MPC)
> candidate for the ballot, since if X covers all of the candidates ranked
> ahead of it, none of those stand a snowflake's proverbial chance in
> comparison.
>

For ballot B compute the MPC candidate by (1) ordering the rows and columns
of the defeat matrix in the ballot order of the candidates ... (2) fill in
1's down the main diagonal ... (3) square the resulting matrix (4) find the
column furthest to the right with solid zeros above the main diagonal.
This column corresponds to the MPC candidate for this ballot.

-Forest

>
> In any case, for me it would be interesting to see if this MPC
> substitution for First Place Votes preserves the burial resistance of
> fpA-SumfpC, while lessening the need for actual voter favorite betrayal on
> the ballots ... i.e. alleviating the tension between compromise and burial
> resistance.
>
> -Forest
>
> On Tue, Nov 22, 2022, 4:02 PM Kristofer Munsterhjelm <km_elmet at t-online.de>
> wrote:
>
>> So I finally wrote something quick (and hopefully less messy than my
>> previous manipulability checker) to determine strategy susceptibility
>> for a few voting methods. It's still very unoptimized and thus quite
>> slow, but I've attached the Python source to my post. PDFs showing
>> results can be found here:
>> https://munsterhjelm.no/km/python_vote_strats/ and the Python source is
>> available there as well.
>>
>> This should both give some ideas as to where to take fpA-fpC, as well as
>> the relative proportion of compromise vs burial for some Condorcet
>> methods. (However, as my figures seem somewhat different from Daniel
>> Carrera's, there may still be bugs. So take this with a pinch.)
>>
>> I'll first note some observations, then explain how to use the Python
>> code, and then how to read the bar charts.
>>
>> For impartial culture, the observations seem to be:
>>
>> - The two simple fpA-fpC generalizations are not robustly strategy
>> resistant the way IRV is. While they do well with three candidates, as
>> the number of candidates increases, the susceptibility increases; and at
>> 10 candidates, it's up at Minmax level.
>>
>> - That said, even Contingent vote (which is a quick proxy for IRV) gets
>> more susceptible to strategy as the number of candidates increases. I
>> suspect that for any voting method in impartial culture, and any
>> susceptibility level, there exists a sufficiently large number of voters
>> and candidates where that method is vulnerable to strategy at least that
>> often.
>>
>> - The simple generalizations also lose strategy resistance when the
>> number of voters is increased for more than four candidates, whereas
>> Contingent vote and its Smith,Plurality version both seem to level off
>> for a fixed number of candidates. See e.g. the contingent 99 voters 5
>> candidates graph.
>>
>> - fpA-max fpC is more resistant than fpA-sum fpC, both in terms of total
>> susceptibility and in how much can be accomplished by just burial or
>> compromise vs having to do both at once.
>>
>> - There seems to be a baseline compromise level that all the depicted
>> Condorcet methods follow -- see the sum of the blue plus purple bars for
>> Copeland, Minmax, and the two fpA-fpC methods. If this really is
>> universal, it might be possible to derive results about what that level
>> is for *any* Condorcet method as number of voters approaches infinity.
>> But I'd need to implement something known to be strategy resistant and
>> Condorcet, e.g. Smith//IRV, to know whether the pattern is real or just
>> a fluke.
>>
>> - On some of the graphs, Contingent has a lower susceptibility than
>> Smith-Contingent, even for three candidates. On the face of it, this
>> shouldn't be possible since there's a proof that "Condorcet else X" is
>> never less resistant than X alone, assuming certain majority-based
>> criteria hold for X. I think the answer is that my simulation doesn't
>> take more complex strategies into account, which means that Contingent
>> has quite a few strategies that are neither full compromise nor full
>> burial nor both at the same time.
>>
>> - Smith-Contingent vote is both summable and robust to strategy with the
>> number of candidates fixed in IC. This shows that summability and
>> robustness is compatible. Furthermore, the method is vulnerable to my
>> "nobodies ranked first" problem: if every voter ranked himself first, it
>> would be unable to call a winner. So neither ISDA nor (the weaker)
>> immunity to the nobodies ranked first problem is required for a method
>> to be strategically robust in IC.
>>
>> ("Strategically robust" here would probably mean something close to: 1.
>> the method starts at a low susceptibility level for modest number of
>> candidates in IC. 2. With not too many candidates, the limit of
>> strategic susceptibility as number of voters goes to infinity is not one.)
>>
>> Note that this is all under impartial culture, which in a sense is the
>> most tie-prone of them all. Spatial models might show much less
>> potential for strategy.
>>
>> ---
>>
>> Usage:
>>
>> The Python code can be used by starting an interactive interpreter (e.g.
>> python3 or ipython3), importing the strategy and generators modules, and
>> then calling plot_MC_proportions, for instance like this:
>>
>> strategy.plot_MC_proportions(election_space=generators.strict_ordinal_elections(99,
>>
>> 5))
>>
>> Note that burial doesn't yet work with the truncated ballot generators,
>> as the burial function doesn't check if the candidate is unranked. And,
>> as mentioned, it is very slow. Implementing a cache (for things like the
>> current election's Condorcet matrix) would help a lot, as would reusing
>> elections, e.g. drawing just 1000 and testing the same 1000 on each
>> method instead of drawing 1000 * num methods elections in the
>> Monte-Carlo simulator.
>>
>> The code may understate nonmonotone methods' strategic susceptibility
>> because it's possible that e.g. upranking a compromise all the way to
>> first may not work but upranking it to second place does, as a
>> consequence of pushover. But I don't have any nonmonotone methods
>> implemented yet, so that shouldn't be a problem :-)
>>
>> ----
>>
>> Reading the bar charts:
>>
>> These are stacked charts, so the total height of a method's bar gives
>> how often simple (compromise, burial, or minmaxing/two-sided
>> maipulation) strategies work. It doesn't check for more complex
>> strategies or coordinated arbitrary-ballot ones, so the total bar may
>> still understate susceptibility slightly. But as Daniel Carrera noted
>> back in January, most methods' strategy vulnerability can be exploited
>> with simple strategies.
>>
>> The "burial only" bar corresponds to elections where burial worked, but
>> compromising didn't. The "compromise only" bar similarly corresponds to
>> elections where compromising worked but burial didn't. The "burial and
>> compromise" bar is for elections where either strategy worked, and
>> "two-sided only" is for elections where two-sided strategy worked but
>> neither burial nor compromising worked.
>>
>> Two-sided strategy is simply putting the candidate you're trying to win
>> first and the candidate who used to win last, i.e. doing both burial and
>> compromising at once. Burial is putting the winner last, and
>> compromising is putting a favored candidate first.
>>
>> When an election is tested, it's tested for the possibility that the
>> group that prefers A to the current winner W can get A elected by
>> employing strategy, for any other candidate A. If there exists any such
>> A, then the strategy is considered to be successful. In the case of
>> ties, what is counted is whether the A>W voters are able to insert A
>> into the set of winners.
>>
>> -km----
>> Election-Methods mailing list - see https://electorama.com/em for list
>> info
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221125/068ba4b5/attachment-0001.htm>


More information about the Election-Methods mailing list