I think you are on to something with your DSV remarks.

You can do DSV where the voters' input is anything from their Von
Morgenstern- Neumann utilities to their ranked preference ballots.

The DSV is supposed to relieve the strategic burden from the voters because
of their lack of .... what?

Lack of information?

Lack of sophistication?

Not really ... when evaluating the theoretical effectiveness of a DSV
method, don't you assume worst case cleverness of potential rational voters
with complete information?

The voters are the potential manipulators ... theoritically (if not
practically) with just as much information about the other voters'
utilities or preferences as the DSV input provides.

Any theorem about the limitations or advantages of a DSV method, would have
to make some assumptions distinguishing unsophisticated voters from
sophisticated voters ... which really must include all voters ... at least
in the worst case scenarion.

I think the analysis is based on all rational voters with complete
information, but the reality in public elections is near complete
disinformation ... along with high levels of irrationality.

Which makes DSV design more of an art than a science.

We're talking of DSV in a general sense that is broad enough to treat
Instant Runoff as a DSV method for transferring votes in a  runoff, which
is already a DSV system for deciding where their one and only Plurality
vote will go, for example.

One takeaway for me is that Condorcet, M is a mild constraint on method M
manipulators, because under complete information, they supposedly already
know all of the sincere preferences including who the sincere CW is if
there is one. The constrained system pins them down to some deterministic
CW that (under game theoretic omniscience) is known to all of the
sophisticated players ... taking away from the advantage of stochastic
strategies with  less constrained entropy ... strategies that would
otherwise be open to them to get a little more advantage over their
unsophisticated compatriots.

Thanks for your thought provoking insights!

fws

On Sat, Jun 24, 2023, 12:08 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

On 6/26/23 01:33, Forest Simmons wrote:

Here are a few more:

Suppose that honest election E (without truncation or equal rank) has a
CW and the method elects him. Then there shouldn't be any compromise
incentive, right?

Argue like this: Suppose some manipulators want to make X instead of the
CW, W, win. By the definition of a CW, a majority prefers W to X. Even
if the people remaining who prefer X to W were to raise X, this wouldn't
affect the magnitude of W>A for any A: not A != X because only X is
being raised, and not W>X because they all vote for X>W already.

So if compromising consists of raising someone you prefer to the current
winner to make that someone win, then when there's a CW, Condorcet
methods are immune to compromising.

We already know that every InfMC method is vulnerable to compromising
when there's a cycle.

So this means that, ties and equal-rank/truncation notwithstanding,
Condorcet methods are vulnerable to compromising iff the honest election
is a cycle.

And that would explain why the compromise vulnerability rate for all
Condorcet methods seem to be so similar! I'm still getting somewhat
different results for different Condorcet methods in my simulator, but
after a more thorough investigation, I found out that's due to different
methods tying in different scenarios, and I don't yet handle ties.

Let's take that a bit further. As usual, I'm considering only full
ranked methods; allowing equal-rank and truncation may make matters more
complex:

Every InfMC method is susceptible to strategy (namely compromising) when
there's a Condorcet cycle. If the InfMC method doesn't pass Condorcet,
it's also susceptible to compromising when it fails to elect the CW. A
method that passes Condorcet may still be vulnerable to some strategy
when it elects the CW, but that strategy isn't compromising.

Thus, among InfMC methods, Condorcet methods minimize the susceptibility
to compromising strategy.

Weak FBC methods seem to do better than this by explicitly failing
Condorcet (since Condorcet and FBC are incompatible). However, these use
equal rank and truncation (MMPO, implicit approval methods), go beyond
universal domain (Range) or fail InfMC (Antiplurality and other methods
considering the first two ranks equal).

Strong FBC methods fail InfMC. This seems to square with Alex Small's
results (https://arxiv.org/abs/1008.4331). (Following this line of
thought may suggest ideas of something that implies Absolute Condorcet,
but that allows for FBC with equal rank etc.)

Now consider a designer trying to create an InfMC method minimizing the
number of strategically manipulable elections. He can't lock himself out
of a minimal solution by requiring Condorcet, so suppose the method
always elects CWs.

Then elections with cycles are already lost - they're manipulable no
matter what. Hence if all that counts is the number of manipulable
elections (and not, say, how many ways an election can be manipulated),
then he only needs to look at the cases where:

• There was a CW
• but then after manipulation, there's a cycle, and the strategists'
  preferred candidate wins.

This because a faction preferring X to the honest Condorcet winner W
can't unliaterally make X a new CW; and elections with honest cycles are
already manipulable.

This might make designing a >3 candidate strategy resistant method
easier, as we only need to consider the faces separating the CW regions
from the cycle regions, not the internal behavior in the cycle regions
or the faces between them.

I agree. The DSV interpretation of Condorcet,M is essentially "in the
very worst case, the strategists know how everybody else will vote; how
can the method make it pointless for them to strategize?"

Chess engines don't do opponent modeling since they can beat players
even without it. Similarly, this maximally pessimal type of DSV idea
says that if we can make something immune to a particular strategy even
under omniscience, then we don't need to care about imperfect
information, game dynamics, etc.

A more realistic way of looking at omniscience strategy might be regret
after the election. If everybody votes, then X wins, then the voting
data is published and people who preferred Y find out they could've won
if they had all compromised for Y instead... they might feel like they
were cheated out of the result. Or they might defensively compromise all
the time, leading to Duverger-type dynamics.

-km

Hi Kristofer,

Le lundi 26 juin 2023 à 11:44:39 UTC−5, Kristofer Munsterhjelm km_elmet@t-online.de a écrit :

Right, if the sincere CW was also voted CW and that's why the method elects him.

By "honest election" you mean the sincere preferences? What about the scenario where only
the cast ballots have a cycle?

To my surprise, I can mostly confirm this result in this setting, that all the rankings are
complete. Condorcet methods have similar compromise performance and beat all methods that
aren't identical to a Condorcet method. With three candidates, Condorcet methods hardly
differ at all.

With four candidates, I see a few tiers. Repeatedly excluding the candidates with the most
last preferences (on the original ballots) until there is a CW, seems to be the best by a
small amount. MinMax-likes come second. Then there's everything else, with the Stensholt
generalizations placing last. (The best non-Condorcet method is my CdlA method, but we can't
call it competitive here.)

Understood, though I would say that the latter definitely seems true. If the defeats in a
Condorcet cycle aren't all backed by a full majority, it's not clear whether it's actually
possible to have an unending process of voters using compromise strategy to make each
candidate win in turn. There may be resolutions to scenarios that don't open up any new
compromise opportunity. (This is the idea behind my /cce calculator, basically.)

Consequently, with truncation allowed, I don't see that all Condorcet methods do just as
well, or are better than all other methods, in regard to compromise incentive.

Sounds right.

I didn't know that paper was there. I think I'll link to it given the MDDA discussion.

I would note in passing that methods that satisfy weak FBC aren't necessarily great at
strong FBC, which is what I normally understand by compromise incentive. The most egregious
example is MaxMin(PS): it satisfies weak FBC but is one of the worst methods at strong FBC.

It's an interesting question. I start to feel that the challenge is completely different
based on whether or not truncation is allowed.

Kevin
votingmethods.net

On 6/27/23 05:30, Kevin Venzke wrote:

The strategy model I had in mind is like this:

Suppose that election E is honest, i.e. is the result of sincere
preferences. If one or more voters can change the outcome according to
election M to something they prefer, then E is manipulable under M.

So we just assume that E is the result of sincere preferences, then see
if anyone can benefit from deviating from their hypothetical sincere
preferences.

When method M is used to call elections, if E is manipulable, the method
might never see E at all, just the manipulated ballot (if E is
manipulable under M and the strategy is actually possible to pull off).
The idea is that if we minimize the number of elections where some kind
of strategy can work, that would discourage people from trying that
strategy as there would be little to gain.

If the sincere preferences don't have a cycle but the cast ballots do,
then (if the method is Condorcet) whatever strategy the manipulators
made use of to create a cycle was probably not compromising. That's all
that I was saying here, really :-)

"If the manipulated election has a cycle then either there was no
compromising strategy or the corresponding election before any strategy
was done had a cycle too" would be another way to put it.

That's surprising. When the methods have no ties, I tend to get similar
results even with a higher number of candidates. Here's an example with
5 candidates and 97 voters, impartial culture, and 50 000 honest
elections tested for each method:

Smith,IRV:

Ties: 0 (0)
Of the non-ties:

(Fraction of elections with incentive for...)
Burial, no compromise: 0.06968
Compromise, no burial: 0.24974
Burial and compromise: 0.00062 (either strategy works)
Two-sided: 6e-05 (neither alone, but doing both works)
Other coalitional strategy: 0.03006

I.e. the total fraction with compromise incentive is 0.25036; 25% of the
elections tested. I'm roughly guessing the c.i. is around 1%.

Ranked pairs(wv):

Ties: 0 (0)
Of the non-ties:

Burial, no compromise: 0.55816
Compromise, no burial: 0.05254
Burial and compromise: 0.19468
Two-sided: 0.18942
Other coalitional strategy: 0.00072

(i.e. total compromise incentive: 0.24722; rounding off to 1% gives 25%
again.)

Strictly speaking, the tiebreakers I use are not anonymous, but I don't
think that it should have an effect. But when ties exist, they can cause
a non-uniform sampling effect, e.g. here is Schulze:

Ties: 0.0774 (3870)
Of the non-ties:

Burial, no compromise: 0.388251
Compromise, no burial: 0.0898764
Burial and compromise: 0.0943421
Two-sided: 0.423369
Other coalitional strategy: 2.16779e-05

Here it seems like the total is 18%. However, this is, as far as I
understand from my program, due to the vast majority of Schulze's ties
happening when there's a cycle, thus depressing the numbers.

Suppose that every tie is a cycle, and that cycles are subject to
compromise. There are 3870 of them. In addition there are (0.0898764 +
0.0943421)*(50000-3870) = 8498 elections we already know are vulnerable
to compromise. The total is 12368, and 12368/50000 = 0.247, which is
again 25% when rounding off to 1%. There may be some true ties that are
actual true ties, not cycles, but this rough calculation seems to get us
in the right ballpark.

(A simple way of checking this is to add some code to print out if
there's both compromise incentive and a CW, or neither. It should never
print anything if the assumption above holds.)

Maybe this isn't really fair. I discard ties because I first wrote the
strategy code to find methods that weren't susceptible to strategy, and
it would otherwise just find the trivial method that ties all the time.
But one could argue that I can't just assume what I'm trying to prove
and say "it seems right" when assuming all ties are cycles and cycles
are all subject to compromise. So to do this properly I probably should
update my code to handle ties, but what educated guesses I could make
seem to already point in the right direction.

That makes sense. I think I recall Warren saying that wv is more
strategy resistant than margins.

There are three possible ways to explore this further; any for which it
would be pretty nice to get some systematic results:

• Try to find a general pattern for methods that pass absolute Condorcet
  but pass e.g. weak FBC when truncation and equal rank are allowed
  (things like MMPO, but without its bad-example). A /cce based on
  absolute Condorcet instead of just plain Condorcet, sort of. This might
  require some property about when equal-first compromising works for
  methods (similar to what InfMC does wrt absolute Condorcet), and then
  similarly extending the Condorcet relation to do a DSV-like automatic
  election like in the InfMC proof.

• Generalize InfMC, e.g. something like "If all voters not in set V are
  indifferent to A and B, and the method elects one of them, then a
  majority of the voters in V can decide which one it will be by modifying
  their ballots". (I think fractional IRV passes this?? At least Range
  does) Then perhaps an analogous proof could construct a condition that's
  sufficient for minimal compromising incentive among all methods passing
  this criterion.

• Find out if such an endeavor is bound to fail (e.g. cyclical
  compromising that you mentioned).

That's a good point. Maybe requiring that the method passes (absolute)
Condorcet when everybody fully ranks would keep strong FBC violations in
check, as we'd then be building on a foundation we know works.

I've kind of been hoping that the optimal for full rank would give some
hints to what shape the optimal with truncation and equal rank would
have. Kind of how looking at part of a picture lets you find out what
the rest is. But it's definitely possible that you can't have it both
ways and that something that's good at dealing with equal-rank and
truncation has to sacrifice some full-rank resistance to do so ... in
which case it's the best method with equal rank and truncation that we'd
want to find. Or at least a good one.

-km

Hi Kristofer,

Le mercredi 28 juin 2023 à 19:42:00 UTC−5, Kristofer Munsterhjelm km_elmet@t-online.de a écrit :

Ok, I see.

[omitting results]

This is an interesting argument. I think my result may be an artifact of the fact
that I require the improvement in the result to be achieved by a single bloc of
like-minded voters. This should mean that the compromise incentive will appear to
be lower if it's less likely that a single bloc can effect the change.

In my simulation code, ties are handled by issuing a sort of die roll outcome to
each candidate, and any ties (during the method or at the very end, however
needed) are broken with this. Then, when checking for changes in the winner
resulting from vote changes, the die rolls must stay the same, so that we can be
sure that result changes are due to the vote change.

(This approach isn't clone-proof, and has the implication that no tie rate can be
reported, short of adding debug code to a specific method, or cloning the method
into a copy that uses a different tiebreaker.)

I think Warren did express such an opinion, though I don't think it was based on
any simulations.

One can interpret WV as a heuristic to gauge which voters are capable of changing
the outcome if they aren't happy with it.

If I understand these requirements:

1. absolute Condorcet = Condorcet(gross) = must elect a candidate with a full
   majority over every other candidate
2. weak FBC
3. Plurality (the arguable problem with MMPO bad examples)

MAMPO, ICA, and MaxMin(PS) satisfy these off the top of my head. If some
Plurality failures are actually allowed, then MDDA too.

Over the past decade I've thought about other ways of doing CCE. An advantage of
basing it on plain Condorcet is that it's relatively decisive. An FBC-compatible
version would be interesting though.

What's completely missing is a weak FBC method that satisfies Plurality and
doesn't have much truncation incentive.

That criterion sounds like it would inherently create compromise incentive,
because if A is an unviable trash candidate who pairwise beats B, then B also
cannot be allowed to win. So A>B>? voters could have compromise incentive.

Well, without ER or truncation, a cyclical compromise incentive is what we
expect from any cycle. So you've identified the limit of how good a Condorcet
method can be in that environment, I guess. But with ER or truncation, we can
definitely do better, because the cyclical compromising isn't always inevitable.
So I guess the endeavor only fails to the extent that we can't figure out how
good a method can be.

Possibly I misunderstand what the endeavor is.

But MaxMin(PS) does satisfy that, so that's not a very demanding standard.

I think the situation is not that full-rank resistance is being sacrificed, but
that full-rank resistance, at its best that can be achieved, is not really that
good.

Yes, I would think so in that case.

Kevin
votingmethods.net