[EM] robustness against single withdrawals in case of 4 candidates

[Jobst Heitzig]

This is an attempt to measure a kind of "robustness against withdrawals"
for the three methods Ranked Pairs, River, and Beatpath.

For any given voting situation, the method gets a score of one for each
candidate whose withdrawal does not change the winner. This score is
added for all the 52 situations with 4 candidates in which the score is
not identical for the three methods, giving a total score of 104 for RP,
81 for River, and 57 for Beatpath. This corresponds to a mean score of

	2    for Ranked Pairs,
	1.55 for River, and
	1.1  for Beatpath, compared to
	3    for Approval (the maximal score possible)

Of course, this is only a very rough indicator so far, but it suggests
that we should perhaps perform some Monte Carlo simulations in order to
estimate for various combinations of methods and candidate numbers the
median number of candidates whose withdrawal doesn't change the winner.

This would give a nice indicator for robustness. My guess is that the
robustness gap between Ranked Pairs and Beatpath will grow with the
number of candidates, and that River will be less robust than Ranked
Pairs only when the number of candidates is small.

Jobst



Here's the detailed list of examples:

Notation: XY is the strength of defeat X>Y.

Situation            Winner Score
                     RP     RP
                     | Riv  | Riv
                     | | BP | | BP
                     | | |  | | |
AB>BD>...
 CD>DA>AC>BC         A A C  2 2 1
 CD>DA>BC>AC         A A C  2 2 1
 DA>CD>AC>BC         A A C  2 2 1
 DA>CD>BC>AC         A A C  2 2 1
AB>CD>...
 BD>DA>AC>BC         A C C  2 1 1
 BD>DA>BC>AC         A C C  2 1 1

AC>BC>DA>...
 CD>AB>BD            D D B  2 2 1
AC>CD>...
 BC>DA>AB>BD         A A B  2 2 1
 DA>BC>AB>BD         A A B  2 2 1
AC>DA>...
 BC>CD>AB>BD         D D B  2 2 1
 CD>BC>AB>BD         D D B  2 2 1

BC>AC>CD>...
 DA>AB>BD            A B B  2 1 1
BC>AC>DA>...
 CD>AB>BD            D B B  2 1 1
BC>CD>...
 AC>DA>AB>BD         A B B  2 1 1
BC>DA>...
 AC>CD>AB>BD         D B B  2 1 1

BD>AB>...
 CD>DA>AC>BC         A A C  2 2 1
 CD>DA>BC>AC         A A C  2 2 1
 DA>CD>AC>BC         A A C  2 2 1
 DA>CD>BC>AC         A A C  2 2 1
BD>CD>AB>...
 DA>AC>BC            A A C  2 2 1
 DA>BC>AC            A A C  2 2 1
BD>CD>DA>...
 AB>AC>BC            B B C  2 2 1
 AB>BC>AC            B B C  2 2 1
BD>DA>...
 AB>CD>AC>BC         B B C  2 2 1
 AB>CD>BC>AC         B B C  2 2 1
 CD>AB>AC>BC         B B C  2 2 1
 CD>AB>BC>AC         B B C  2 2 1

CD>AB>...
 BD>DA>AC>BC         A C C  2 1 1
 BD>DA>BC>AC         A C C  2 1 1
CD>AC>...
 BC>DA>AB>BD         A A B  2 2 1
 DA>BC>AB>BD         A A B  2 2 1
CD>BC>...
 AC>DA>AB>BD         A B B  2 1 1
CD>BD>AB>...
 DA>AC>BC            A C C  2 1 1
 DA>BC>AC            A C C  2 1 1
CD>BD>DA>...
 AB>AC>BC            B C C  2 1 1
 AB>BC>AC            B C C  2 1 1
 AC>AB>BC            B C B  2 1 2
CD>DA>...
 AC>BD>AB>BC         B C B  2 1 2
 BD>AB>AC>BC         B C C  2 1 1
 BD>AB>BC>AC         B C C  2 1 1
 BD>AC>AB>BC         B C B  2 1 2

DA>AC>...
 BC>CD>AB>BD         D D B  2 2 1
 CD>BC>AB>BD         D D B  2 2 1
DA>BC>...
 AC>CD>AB>BD         D B B  2 1 1
DA>BD>...
 AB>CD>AC>BC         B B C  2 2 1
 AB>CD>BC>AC         B B C  2 2 1
 CD>AB>AC>BC         B B C  2 2 1
 CD>AB>BC>AC         B B C  2 2 1
DA>CD>...
 AC>BD>AB>BC         B C B  2 1 2
 BD>AB>AC>BC         B C C  2 1 1
 BD>AB>BC>AC         B C C  2 1 1
 BD>AC>AB>BC         B C B  2 1 2

(END OF LIST)