Talk:Landau set

example

Could anybody explain the Landau set by means of an example? Also, I'd like to know what it is important for. Martinwilke1980 (talk) 16:43, 22 October 2008 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Landau set. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20060913022520/http://www.people.fas.harvard.edu/~epenn/covering.pdf to http://www.people.fas.harvard.edu/~epenn/covering.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 16:06, 16 December 2017 (UTC)

name

I searched through every single source listed here and on electowiki, and found only one use of the term "Landau set" (https://www.google.com/books/edition/Applications_of_Combinatorics_and_Graph/7HPSBwAAQBAJ?hl=en&gbpv=1&bsq=landau). Here is a breakdown of how each source used in the Wikipedia article uses each term:

source	"Landau"	"uncovered"	"Fishburn"
Miller, Nicholas R. (1977). "Graph-Theoretical Approaches to the Theory of Voting" (PDF). American Journal of Political Science. 21 (4): 769–803. doi:10.2307/2110736. ISSN 0092-5853. JSTOR 2110736.	not mentioned	not mentioned	for a statement about Pareto optimality, cites Fishburn, Peter C. (1973). The theory of social choice. Princeton: Princeton University Press.
Miller, Nicholas R. (1980). "A New Solution Set for Tournaments and Majority Voting: Further Graph-Theoretical Approaches to the Theory of Voting" (PDF). American Journal of Political Science. 24 (1): 68–96. doi:10.2307/2110925. ISSN 0092-5853. JSTOR 2110925.	defines and discusses Landau's Theorem, which seems related, and cites Landau, H. G. (1953). "On dominance relations and the structure of animal societies: III. The conditions for a score sequence". Bulletin of Mathematical Biophysics. 15: 143–148.	defines and discusses the "uncovered set"	states that "Fishburn's function" C9 outputs the uncovered set, and cites Fishburn, Peter C. (November 1977). "Condorcet social choice functions". SIAM Journal of Applied Mathematics. 33: 469–489.
Schofield, Norman James (1985). Social Choice and Democracy. Springer-Verlag: Berlin. doi:10.1007/978-3-642-70596-0. ISBN 978-3-642-70598-4. LCCN 85-17199.	not mentioned	talks about the "uncovered set", citing "A New Solution Set for Tournaments and Majority Voting: Further Graph-Theoretical Approaches to the Theory of Voting" (full citation above) cites Shepsle, KA; Weingast, BR (1984). "Uncovered sets and sophisticated voting outcomes with implications for agenda institutions". American Journal of Political Science. 28: 49–74.	cites: Ferejohn, JA; Fishburn, PC (1979). "Representations of binary decision rules by generalized decisiveness structures". Behavioral Science. 25: 140–148. Fishburn, PC (1970). "Arrow's impossibility theorem: Concise proof and infinite voters". Journal of Economic Theory. 2: 103–106. Fishburn, PC (1973). The theory of social choice. Princeton: Princeton University Press.
Straffin, Philip D. (1989). "Spatial models of power and voting outcomes". In Roberts, Fred (ed.). Applications of Combinatorics and Graph Theory to the Biological and Social Sciences. New York: Springer-Verlag. pp. 315–335. doi:10.1007/978-1-4684-6381-1_14. ISBN 978-1-4684-6381-1. LCCN 89-11271. OCLC 7322346268. (I don't have full digital access, but it's in my school's library, so I plan to read it there tomorrow.)	on pp. 325-334, mentions "Landau set" a few times, once stating "... Landau set the uncovered set."; also cites Landau, H. G. (1953). "On dominance relations and the structure of animal societies: III. The conditions for a score sequence". Bulletin of Mathematical Biophysics. 15: 143–148.	on pp. 325-332, talks about the "uncovered set"; on p. 335, cites [not shown in preview]. "Uncovered sets and sophisticated voting outcomes with implications for agenda institutions". American Journal of Political Science: 49–74. {{cite journal}}: Unknown parameter |vol= ignored (|volume= suggested) (help)	not mentioned within the chapter of interest
Penn, Elizabeth Maggie (December 20, 2004). "Alternate definitions of the uncovered set and their implications" (PDF). Archived from the original (PDF) on September 13, 2006.	not mentioned	mentioned throughout	not mentioned
Miller, Nicholas R. (Winter 2007). "In Search of the Uncovered Set". Political Analysis. 15 (1). Oxford University Press on behalf of the Society for Political Methodology: 21–45. doi:10.1093/pan/mpl007. ISSN 1047-1987. JSTOR 25791876.	not mentioned	mentioned throughout	not mentioned
Bianco, William T.; Jeliazkov, Ivan; Sened, Itai (Summer 2004). "The Uncovered Set and the Limits of Legislative Action". Political Analysis. 12 (3): 256–276. doi:10.1093/pan/mph018. ISSN 1047-1987. JSTOR 25791775. S2CID 14752732.</ref>	not mentioned	mentioned throughout	not mentioned

Since only one source uses the term "Landau set" and nearly every source uses the term "uncovered set" (including the source that uses the term "Landau set"), I propose renaming this article to "uncovered set". Any objections?

Solomon Ucko (talk) 18:59, 27 October 2023 (UTC)

Here are the parts (except examples, most proofs, and diagrams) that are most relevant to this article, of Straffin, Philip D. (1989). "Spatial models of power and voting outcomes". In Roberts, Fred (ed.). Applications of Combinatorics and Graph Theory to the Biological and Social Sciences. New York: Springer-Verlag. pp. 315–335. doi:10.1007/978-1-4684-6381-1_14. ISBN 978-1-4684-6381-1. LCCN 89-11271. OCLC 7322346268.:

(Formatting modified.)

Landau set: If the top cycle set is too large, we could try to restrict it by including only those alternatives which beat all other alternatives either directly or indirectly by a chain of length two (i beats j, j beats k). This set is called the Landau set after . See for a clear and entertaining exposition. [...] Theorem 1. The Landau set cannot contain a Pareto inferior alternative.

— p. 324

The Landau set has a number of other good properties. For example, it is non empty [...] Moreover, Miller showed it can be characterized game theoretically. Suppose [...] that two politicians P and Q must each choose one of the alternatives [...] as his "platform." P will beat Q and get a payoff +1 precisely if a majority of voters prefers P's platform to Q's platform. [...] Theorem 2. The Landau set is exactly the set of undominated platforms. [...] Miller called the relation of domination covering, and the Landau set the uncovered set. With all these nice properties, it is unfortunately true that the Landau set can still be large. In fact, also proved that in a random tournament of size n, the probability that every alternative is in the Landau set, goes to one as n gets large.

— p. 325

Landau set (Uncovered set): In the spatial context, it is convenient to use Miller's alternative formulation of the Landau set. Definition. For a point x in R^k, DEF(x) is the set of all points which beat x under majority rule. Definition. For points x and y, x covers y if x beats y, and DEF(x) ⊆ DEF(y). See Figure 9. Definition. The uncovered set (Landau set) is the set of all points which are not covered by any other point.

— p. 326

Landau proved that any Copeland winner must be in the Landau set (which is why the Landau set must be non-empty).

— p. 329

If the top cycle set is all of R^k, and in the discrete case the Landau set is not much smaller, one might be pessimistic about the size of the uncovered set in a spatial voting situation. However, it is easy to show that the Landau set cannot be all of R^k. First, in a spatial voting situation the set of non-Pareto-inferior alternatives ("Pareto optimal alternatives") is exactly the convex hull C of the voter ideal points. The argument of Theorem 1 goes through to show that the uncovered set cannot contain any Pareto inferior alternatives, hence must be contained in C. In fact, recent results show that the uncovered set is often considerably smaller than C.

— p. 330

Definition. The yolk of a spatial voting system in R² is the smallest disk B(x, r) which intersects all median lines. Here x is the center of the disk, and r is its radius. See Figure 10. Theorem 5. The uncovered set is contained in B(x, 4r) [...]
One consequence of this theorem is that if a voting situation almost has a Condorcet winner (so the yolk is small), the uncovered set will be small. Hence, the uncovered set looks like an attractive solution concept in spatial voting, although its precise geometry is not yet well understood. The importance of the uncovered set is increased by a beautiful result of which characterizes it as the set of alternatives which can be reached from any other point by a chain of majority votes when the voters vote sophisticatedly (taking into account what other voters will do and adjusting their vote accordingly) rather than sincerely.

— p. 331

A version of Landau's original argument goes through to show that the Copeland winner is in the uncovered set.

— p. 332

Solomon Ucko (talk) 21:38, 31 October 2023 (UTC) Solomon Ucko (talk) 21:38, 31 October 2023 (UTC)

It's my impression as well that uncovered set is the main term used in the literature. (Thanks for doing the research to back that up.) I have no objection to the move. - CRGreathouse (t | c) 01:39, 3 November 2023 (UTC)

Perfect! Since you created the page and contributed most of the content and you say you have no objection, no one else has raised any objection either and it's been 6 days since I proposed the move, and disagreement seems unlikely, I'll go ahead and move the page. If anyone objects, they can initiate a discussion process following Wikipedia:Requested moves/Controversial, and it can be moved back if there is consensus to do so. Solomon Ucko (talk) 01:54, 3 November 2023 (UTC)

References