[EM] SODA properties

[Jameson Quinn]

As a quick reminder, SODA stands for simple optionally-delegated approval.
It's a three-step delegated method: in step 1, each candidate declares a
strict preference order over the other candidates; in step 2, voters submit
approval ballots over candidates plus a dummy "do not delegate" candidate,
with single approvals counting as delegated ballots; and in step 3,
candidates sequentially assign additional approvals on the ballots
delegated to them, consistent with their step 1 preference order, and with
highest approval total assigning first.

So I'm working on a basic citeable paper for arxiv on the properties of
this method. I finally finished proving mono-plump (assuming candidates are
honest in step 1; in practice, dishonesty in step 1 would tend to be
punished in step 2, as well as being revealed in step 3 for possible
punishment in later elections; so this assumption is I think pretty
reasonable). That's really the basis for proving all of the other desirable
properties of this method.

So, the question is, what other properties should I include? The properties
I like are things like "if there is a true Condorcet winner that is
potentially visible in the ballots, then votes which are honestly-delegated
as much as possible without contradicting honest preferences regarding that
winner, will be a strong Nash equilibrium which elects the Condorcet
winner, and one which is preferable to any other strong Nash equilibria for
some coherent majority of voters." Which is a mouthful and a half, but
actually a nice desirable property: in most real-world cases, even perfect
information would not give you any robust strategic reason not to delegate.
(Note that this property does not call for the existence of a majority
Condorcet winner, unlike, say, any roughly similar property you might try
to state for approval or median systems.)

Here's some other properties I think I could prove, in both technical
terms, and practical terms:

"For a zero-information voter, assuming that candidate strategy in step 3
is rationally consistent with their delegation in step 1, the correct
strategy for you as a voter is to delegate if a candidate's predeclaration
agrees with half or more of your preferences, weighted by your preference
strengths. Otherwise, it is to approve of candidates at or above average
utility."... in other words, delegation is a good strategy and you might as
well just delegate to your favorite and go home, especially if you're
moderately lazy about evaluating all the candidates.

"If the probability for each voter of agreeing with any of their
candidate's predeclared preferences is a fixed p>50%, and independent of
the opinions of other voters, then the probability that, if a majority
Condorcet winner exists, that fact will be potentially visible in voted
ballots, and therefore by the first property stated above that candidate
will win in a 'doubly strong' Nash equilibrium with most votes delegated,
approaches 1 as the number of voters goes to infinity"... in other words,
if candidates are representative of the majority of their constituency in
every regard, then the system can consistently find the optimal winner,
with minimal work from the voters.

"If the probability that a candidate will disagree with the majority of
their voters about a given pairwise preference is ε falling to zero, then
the probability that a majority Condorcet winner who exists will not be
visible through delegation (as above) is no greater than nε where n is the
number of candidates; this holds despite the total number of disagreements
rising as n³ε." In other words, the result just above is at least
moderately robust to candidates who disagree with their constituency in a
small number of cases.

The above properties are my attempts at defining Condorcet-like properties
that this passes. As for more-traditional properties, SODA passes:

Majority
Mutual majority¹
Condorcet loser²
Smith²
Cloneproof³
Monotone⁴
Not consistency, but I suspect some consistency-like property which is good
enough in practice
Participation for delegated votes
Rational strategy in stage 3 is NOT to my knowledge polytime, but
pathological cases would take dozens of evenly-balanced candidates with
preference orders that are highly cyclical in general. Also, the system
itself is clearly polytime; it's just that you lose some of the nice
properties above if you don't assume rationality in stage 3.
Summable O(N)
Allows equal-ranking
Allows >2 ranks in some cases (if the desired rank order is available
through delegation)
Not LNHa or LNHe in general, but much closer to both than most systems
which violate them. Not sure if I could state this more rigorously; perhaps
not.
Bayesian Regret likely to be in the neighborhood of honest Condorcet, and
to be very robust under strategic voters.

¹If stage one is honest and stage 3 is rational.
²If it's determinable from the ballots
³Assuming the clone's preference order is also cloned
⁴In at least the half-dozen ways I've been able to check in stage 2; though
it may fail for stage 1.

.....

So, given all the above, I think this is actually an outstandingly good
system. But... if you only had room to state and prove, say, 3 or 4 of the
above properties, which would you focus on?

Cheers,
Jameson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20131021/2c6c880a/attachment-0003.htm>