[EM] Idea for generalizing Resistant set into hopefully always strategyfree system

[Gustav Thorzen]

So I made some progress on understanding the Resistant set better,
and realized it is possible to create a system neatly interpolating
between the signle member strategyfree scenario
and the Random Ballot method,
while also looking like it satisfies Mutual Majority and Clone Independence,
both perfect clones and clone coalitions.


But first some definitions:

N = Total number of voters.
M = Total number of candidates.
m = Number of candidates in the sub-election, when talking about one.
T = The set of candidates to tiebreak with Random Ballots.
t = Number of members of T participating in the sub-election, when talking about one.

Voters have true preferences of complete rankorders, ties allowed.
Every voter is a priori assumed to have the complete rankorder of every candidate tied,
and the ballot format and counting and inference rules allows every voter to change
that to any other complete rankorder of their choice,
and should the ballot be spoiled, e.g. not participating or an invalid ballot is provided,
then their initially assumed rankorder remains unchanged by the system.
This means the number of rankorders are always fixed equal to N.
I will use "lor" as a shorthand for the logical-or, and "xor" for exclusive-or.

For a given rankorder, a candidates rank is defined as
the number of candidates of the same rank lor higher,
including the candidate itself.

For some examples with M=7 and the rankorder
a=b=c>d>f=g>h
a, b, and c, are each ranked both 3:rd
d is ranked 4:th
f, and g, are each ranked 6:th
h is ranked 7:th

In a subelection between b, c, and d,
m = 3
b, and c, are each ranked both 2:nd
d is ranked 3:rd

In a subelection between d, and h,
m=2
d is ranked both 1:st
h is ranked 2:nd


To the method itself.

For a positive integer starting at 1 and up to M, in that order,
check if it possible to create a set T with that many members,
where each member candidates individually satisfies the following condidtion:
In every sub-election where that member candidate participates,
they are ranked t:th lor higher on some number of rankorders
strictly greater then the number N/(m+1-t) (no rounding here).

The first time we can create such a set T,
we send the members of for Random Ballot tiebreaking,
with all candidates not in T marked as disqualified.
Should the Random Ballot tiebreaking fail to disqualify
all but 1 of the members of T (as if, but technically possible),
we tiebreak the remaining members with by picking
one winner at random with each remaining candidate
assigned an equal probability of being picked (I think this is called Sortition).


So about its properties.

First lets go over its 1 big problem (well 2 if it is not strategyfree),
the amounts of computaions scales at an absurdly fast pace
as M increases unless someone can identify a more efficient way.
The naive method seems to take something around O(N*M^M),
which is way to large for practical purposes.
Even with computers this is beyond silly,
only ever feasable for relatively small M.

I also came up with a similar version which I only conjecture
to have full/complete/strict honesty as a strong nash equilibrium
regardless of true preferences (assuming this one is strategyfree)
but even that one is beyond impractical (N*2^M at least, likely much much worse).

Generalizing both to multiwinner scenarios also came naturally,
for the system here, you basically replace the N/(m+1-t) with
N/(m+k-t) where k is the number of winners and use a the
k winners PR Random Ballot version, but I have nothing idicating
it would keep any honesty incentives,
and is so much worse to count I could not get myself to bother trying to
figure out the time and effort it takes to calculate.

Then there is the question if this proposed system actually is strategyfree.
It seems like it could be, and it also looks to satisfy
Mutual Majority and Clone Independences,
but I can only say for certain with M=1 or M=2,
and "looks like it is true" for M=3 is nowhere near "always true".
A number of theorems claim only Random Ballots is strategyfree,
but the ones I found include a bunch of other critera
beyond voter and candidate/outcome symmetry,
so it looks like they would be subverted here.


All in all, I figured it might be worthwhile if anyone finds it interesting.
I am almost finished with my attempt at a good+feasable fully deterministic system
(since no randomness limits to how good they can be),
and this proposed system here was strikingly similar to how it
would generalize if made to include randomness.

Gustav