[EM] PLEASE consider: More non-deterministic methods

[Jobst Heitzig]

Although there has been only one reply to my previous posting on
non-deterministic methods, I still consider it more and more important
to study such methods.

They seem to be *the only chance* to avoid incentives to produce fake
Condorcet winners by strategic voting!

So here's another couple of methods I ask you to consider:


A non-deterministic method based on Copeland scores
---------------------------------------------------

When no Condorcet winner exists, order the options by descending
Copeland score (= number of options defeated by that option) and, if the
Copeland score is equal, by ascending sum of magnitudes of defeats
against the option at hand, resolving remaining ties at random. Then
choose A as the winner with probability

	 no. of options defeated by A
	 but by no option earlier than A
	---------------------------------
	 no. of all options

Or, equivalenty: Pick an option B uniformly at random. Then choose the
winner uniformly at random from the set of options which have the
smallest sum of magnitudes of defeats against them, among all options
who have the largest Copeland value, among all option defeating B.

Note that the ordering constructed above is monotone in the strong sense
that when A is reinforced against B, only the Copeland scores and sums
for A and B change so that the ordering of the other options remains
unchanged. From this it follows easily that the whole method is
monotonic in the sense that A's probability can only grow in this
situation. Also, only Smith set elements can win since they have always
larger Copeland values than non-Smith elements.

The main advantage of this method is that the set of possible winners
will be quite small on average. This is because the first option in the
ordering beats already at least half of all other options, the next one
will beat an additional quarter on average, the third on will beat an
additional 1/8 of the options on average and so on, so that one would
expect some log(no. of all options) many possible winners only!
	(In contrast, the other monotonic randomized methods I was able to find
always have at least all Banks elements as possible winners, and the
Banks and Smith sets very often equal the whole set of options when the
latter is large.)

The main *dis*advantage, however, is a complete lack of clone
consistency: Cloning an option may increase the Copeland score of one of
the clones arbitrarily far, hence cloning an option which beats a
Copeland winner is a good strategy here...
	Therefore my main question here is that someone please come up with a
different ordering than by Copeland values which is still monotonic in
the strong sense sketched above!


Randomization of methods base on magnitudes
-------------------------------------------

Deterministic methods who use only magnitudes (or, analogously, margins)
of defeats can easily be "randomized" by first adding some random number
to each magnitude. These numbers could for example be drawn from the
uniform distribution on the interval [0,alpha*n] where n is the number
of voters and alpha>=0 is some parameter where alpha=0 means no
randomization.
	When applying this randomization to an immune method such as the river,
beatpath, or Tideman method, say, one will get a probability
distribution whose support is the deterministic winner of the method
when alpha=0 or the whole Smith set when alpha>1, or some set between
the winner and the Smith set when 0<alpha<1. That is, by choice of alpha
we can adjust how widespread the distribution will be.
	Whenever the base method is monotonic, the randomized version will also
be monotonic. Immunity of the (random) outcome is not guaranteed, of
course (since there if often only one immune option), but for immune
base methods and alpha<1, at least the following holds: Any defeat of
strength s against the winner can be countered by a chain of defeats of
strength at least s-alpha*n. The same is true for beatpaths when the
base method is the beatpath method.

Since most methods only use the order and not the actual values of the
magnitudes, one could also replace magnitudes by ranks before adding the
random numbers. This has the advantage that one has a better control
about what can change. For example, when the base method drops weakest
defeats from cycles, and numbers between 0 and 1.5 are added to the
ranks of the defeats, one knows that the randomized method drops only
weakest or second weakest defeats but never drops the strongest defeat
from a cycle! In case of the beatpath method, for instance, an option
can only win in the thus randomized version when its strongest beatpath
to the original beatpath winner is only one rank weaker than the
strongest beatpath back.

My suggestion for further research on such methods is to choose some
base method and then for each number of options to determine the
smallest alpha for which the probability that the resulting set of
winners will be "large enough" is at least, say, 90 percent. By "large
enough" I mean that for every option, there is one possible winner
defeating that option.


Jobst