[EM] The Unique Winning Alliance method

[Rob Speer]

On Sun, Aug 03, 2003 at 11:13:32PM +0200, Markus Schulze wrote:
> it has been proven by Prasanta K. Pattanaik and Bezalel Peleg
> ("Distribution of power under stochastic social choice rules,"
> ECONOMETRICA, vol. 54, p. 909-921, 1986) that there is no
> preferential paretian non-dictatorial single-winner method
> that meets regularity.
> [...]

Okay. I hadn't heard of this result - that's actually a more useful
statement than Arrow's Theorem.

Yes, indeed in UWA you can add a candidate that has some share of the
win, and another candidate's share of the win will increase.

> However, I have some questions about Unique Winning Alliance:
> 
> 1) What is the exact definition for the "Nash Set"? (Please don't
> use game theoretical terminology.)

Exact definitions:
An "alliance" is an assignment of scores between 0 and 1 to every
candidate, such that the scores add up to 1.

The Unique Winning Alliance (UWA) is the alliance that beats all other
alliances, pairwise. (See my previous message for how to determine
manually whether one alliance beats another.)

The Nash set is the set of candidates whose scores in the UWA are
greater than 0.

> 2) Could you give an explicite example where the Smith Set differs
> from the Nash Set?

Sure. Consider this pairwise result matrix:

   A  B  C  D
A  0 +1 -1 +1
B -1  0 +1 +1
C +1 -1  0 -1
D -1 -1 +1  0

The UWA is 33% A, 33% B, 33% C, so the Nash set is ABC.
D is not a member of the Nash set because there is a candidate, B, who
is strictly better than D in terms of pairwise results. Therefore, any
alliance with D in it would lose to one which gives D's share to B.

(I'm not sure if this is the reason _every_ time a candidate is excluded
from the Nash set - it would be convenient.)

> 3) What are, in your opinion, the advantages of Unique Winning
> Alliance compared e.g. to Smith//RandomDictatorship? (At least,
> Smith//RandomDictatorship is monotonic.)

[Aside: Where did the // in method names come from, anyway?]

First to be more clear on terminology: The method I described is what my
advisor calls UWA-Random. UWA is a class of methods.

Because it is not monotonic and not deterministic, I don't think
UWA-Random is actually a very viable method. However, the property it
has - which could be called Very Local IIA, but which you point out is
not the same as regularity - is interesting.

I think there is a lot of promise in UWA completion methods, though.
I mentioned UWA-SD (UWA Sequential Dropping) as a particularly appealing
method. Basically, take the definition of Schwartz Sequental Dropping,
and replace "Schwartz set" with "Nash set".

I believe that this would be monotonic and cloneproof, though I haven't
looked into it much.

-- 
Rob Speer