[EM] River method - a refinement, minor computational evidence, and a generalized IPDA criterion ISDA

[Jobst Heitzig]

Dear Ernie!

you wrote:
> Hi Jobst,
> 
> On Apr 24, 2004, at 5:49 AM, Jobst Heitzig wrote:
> 
>> Def. INDEPENDENCE OF STRONGLY DOMINATED ALTERNATIVES (ISDA):
>> Removing a strongly dominated alternative must not change the winner.
>> X is STRONGLY DOMINATED by an alternative Y if
>> (i) Y beats X
>> and, for all Z distinct from X,Y:
>> (ii)  if Z beats Y, Z beats X even stronger,
>> (iii) if Z beats X, Y beats X even stronger,
>> (iv)  if X beats Z, Y beats Z even stronger, and
>> (v)   if Y beats Z, Y beats X even stronger.
>>
>> In the general case, Pareto-dominated alternatives are also strongly
>> dominated but not vice versa, hence ISDA is then stronger than IPDA. As
>> Steve already pointed out for Pareto-dominated alternatives, such
>> strongly dominated alternatives might be easily be found by a losing
>> party and be added strategically to change the winner, which should not
>> be possible.
> 
> 
> Very impressive.  Just to make sure I understand, are you effectively
> saying that ISDA means that removing -or- adding an SDA shouldn't change
> the results?

I think so -- isn't that the same proposition?

> Also - I didn't know this, perhaps you did - there's now a very nice
> Wiki writeup on MAM:
> 
> http://en.wikipedia.org/wiki/Maximize_Affirmed_Majorities
> 
> I'd love to see a similar article on the River; in fact, if you write
> it, I'd be happy to help Wikify it, if that's a barrier.

Thank you very much for your encouragement. Anyway, I don't think the
River method is elaborated enough yet to be described "officially" in a
Wiki -- I'm sure it needs some weeks of discussion to find out its
advantages and disadvantages.

For example, an open question is how to deal with same-size majorities
-- there are many possibilities: (a) Use a tiebreaker as in MAM or MMV
(which would at least ensure monotonicity), or (b) determine all
lexicographically maximal trees or almost-trees and choose one uniformly
at random, or (c) determine all destinations of lexicographically
maximal trees or almost-trees and choose one uniformly at random, or (d)
simulate the interactive version by successively choosing statements
with a probability proportional to the corresponding majority, and so on...

Jobst