[EM] Landau Winners/Fishburn Set

[Norman Petry]

Here is another message from Markus answering some of my questions about
"Landau Winners".  This issue arose because Markus included the algorithm
for Landau along with his Schwartz algorithm, and I had some questions about
it.

 Again, I thought it might be something of interest to EM generally, so I am
forwarding it to the list for further discussion.

N.

**********

Dear Norman,

you wrote (8 Apr 2000):
> You mentioned the Landau set in your message, but I do not recall that
> Landau has ever been discussed on the EM list.  Does it have any merits or
> uses we should consider?  I did a quick search on the Internet, but turned
> up nothing useful, so if you have any references to Landau I would
> appreciate it.

I should have said that the set of Landau winners is called "uncovered set"
or "Fishburn set." If you search for these words, then you will find some
references.

******

A Landau winner is a candidate, who defeats every other candidate with a
path of length 1 or 2.

Candidate A is a Landau winner iff for every other candidate B at least one
of the following two statements is correct:
(1) A >= B.
(2) There is a candidate C such that A >= C >= B.

******

There must always be at least one Landau winner.

******

Miller demonstrated that if (1) the electorate is 2-dimensional, (2) the
voters are sophisticated and (3) the used election method meets the
majority criterion, then the winner must always be a Landau winner.
Therefore, many scholars consider the Landau winners to be the natural
generalization of the Condorcet winner.

[a] Nicholas R. Miller, "Graph-Theoretical Approaches to the Theory of
Voting," American Journal of Political Science, vol. 21, p. 769-803, 1977,

[b] Nicholas R. Miller, "A New Solution Set for Tournaments and Majority
Voting: Further Graph-Theoretic Approaches to Majority Voting," American
Journal of Political Science, vol. 24, page 68-96, 1980,

[c] Norman J. Schofield, "Social Choice and Democracy," Berlin,
Springer-Verlag, 1985,

[d] Philip D. Straffin, "Spatial Models of Power and Voting Outcomes,"
Applications of Combinatorics and Graph Theory to the Biological and Social
Sciences, edited by Fred S. Roberts, New York-Berlin, Springer, 1989,
page 315-335.

******

I mentioned the Fishburn set only because the calculation of the Fishburn
set is almost identical to the calculation of the Smith set and because
somebody might ask in the future how to calculate the Fishburn set.

******

You wrote (8 Apr 2000):
> Also, I think your message would be a valuable contribution to the EM list
> archives, for anyone trying to implement Smith, Schwartz, etc.  May I have
> your permission to forward the message to the list?

Of course, you may.

Markus Schulze
schulze at sol.physik.tu-berlin.de
schulze at math.tu-berlin.de
markusschulze at planet-interkom.de