[EM] The Unique Winning Alliance method

[Rob Speer]

On Mon, Aug 04, 2003 at 11:38:05AM -0700, Rob LeGrand wrote:
> I'd be happy to incorporate the Nash set into my simulations and test this
> out for you, but I may still be a bit unclear on the algorithm to calculate
> the Nash set.

First of all, I've been doing it with a Python program. If it will be
any help, I've put up my program at:

http://takeneggs.com/files/uwa.tar.gz

It uses the lpsolve library, which is included in that file, but which
is not cross-platform. It'll only work on Linux.

On any other platform (and this is where I begin to admire you for your
determination) you'd have to also install lpsolve, from
http://takeneggs.com/files/lpsolve-3.2-0.3.tar.gz.

Not the easiest thing to use, I'll admit.

> As I understand it:
> 
> Consider each pair of candidates X and Y such that X beats Y pairwise.
> If X does at least as well against every other candidate Z pairwise as Y
> does against Z, exclude Y from the Nash set.
> 
> Or should it be:
> 
> Consider each pair of candidates X and Y such that X beats Y pairwise.
> If X beats every other candidate Z pairwise that Y beats, exclude Y from
> the Nash set.
> 
> Or is it something else?

It would be nice if there were a simple method like that. I discovered
when responding to Markus that this was not the case.

I responded to him (meaning to respond to the list) with this example
where the Nash set is ABC but the Uncovered set is ABCD:

   A  B  C  D  E  F
A  0  5 -5  6  3 -3
B -5  0  5  3 -3  6
C  5 -5  0 -3  6  3
D -6 -3  3  0  1  1
E -3  3 -6 -1  0  1
F  3 -6 -3 -1 -1  0

B does not do better in all pairwise contests than D - D in fact beats
E, while B doesn't - but D is still excluded from the Nash set, which is
ABC.

A criterion I've thought about but haven't tested: the Nash set is the
smallest set such that, for any X outside of the Nash set, there exists
a candidate A in the Nash set, such than for any B in the Nash set A
beats B by more than X beats B.

(This is the "does at least as well" rule, but it only matters how you
do against members of the Nash set.)

But I'm not guaranteeing that that works. The only guaranteed definition
is the mathematical one:

Let P(x,y) be the amount by which candidate x beats candidate y. Call
the candidates C1, C2, ..., Cn. Find the series of values v1, v2, ...,
vn that satisfies the N+1 equations

v1 + v2 + ... + vn = 1
For any i in 1...n:
	v1*P(Ci, C1) + v2*P(Ci, C2) + ... + vn*P(Ci, Cn) <= 0

The UWA is the set of values v1...vn.
The Nash set is the set of candidates Cj such that vj > 0.

--
Rob Speer