[Election-Methods] method design challenge + new method AMP

[Jobst Heitzig]

Hello folks,

over the last months I have again and again tried to find a solution to
a seemingly simple problem:

The Goal
---------
Find a group decision method which will elect C with near certainty in
the following situation:
- There are three options A,B,C
- There are 51 voters who prefer A to B, and 49 who prefer B to A.
- All voters prefer C to a lottery in which their favourite has 51%
probability and the other faction's favourite has 49% probability.
- Both factions are strategic and may coordinate their voting behaviour.


Those of you who like cardinal utilities may assume the following:
51: A 100 > C 52 > B 0
49: B 100 > C 52 > A 0

Note that Range Voting would meet the goal if the voters would be
assumed to vote honestly instead of strategically. With strategic
voters, however, Range Voting will elect A.

As of now, I know of only one method that will solve the problem (and
unfortunately that method is not monotonic): it is called AMP and is
defined below.


*** So, I ask everyone to design some ***
*** method that meets the above goal! ***


Have fun,
Jobst


Method AMP (approval-seeded maximal pairings)
---------------------------------------------

Ballot:

a) Each voter marks one option as her "favourite" option and may name
any number of "offers". An "offer" is an (ordered) pair of options
(y,z). by "offering" (y,z) the voter expresses that she is willing to
transfer "her" share of the winning probability from her favourite x to
the compromise z if a second voter transfers his share of the winning
probability from his favourite y to this compromise z.
    (Usually, a voter would agree to this if she prefers z to tossing a
coin between her favourite and y).

b) Alternatively, a voter may specify cardinal ratings for all options.
Then the highest-rated option x is considered the voter's "favourite",
and each option-pair (y,z) for with z is higher rated that the mean
rating of x and y is considered an "offer" by this voter.

c) As another, simpler alternative, a voter may name only a "favourite"
option x and any number of "also approved" options. Then each
option-pair (y,z) for which z but not y is "also approved" is considered
an "offer" by this voter.


Tally:

1. For each option z, the "approval score" of z is the number of voters
who offered (y,z) with any y.

2. Start with an empty urn and by considering all voters "free for
cooperation".

3. For each option z, in order of descending approval score, do the
following:

3.1. Find the largest set of voters that can be divvied up into disjoint
voter-pairs {v,w} such that v and w are still free for cooperation, v
offered (y,z), and w offered (x,z), where x is v's favourite and y is
w's favourite.

3.2. For each voter v in this largest set, put a ball labelled with the
compromise option z in the urn and consider v no longer free for
cooperation.

4. For each voter who still remains free for cooperation after this was
done for all options, put a ball labelled with the favourite option of
that voter in the urn.

5. Finally, the winning option is determined by drawing a ball from the
urn.

(In rare cases, some tiebreaker may be needed in step 3 or 3.1.)


Why this meets the goal: In the described situation, the only strategic
equilibrium is when all B-voters offer (A,C) and at least 49 of the
A-voters "offer" (B,C). As a result, AMP will elect C with 98%
probability, and A with 2% probability.