Computing the minimal covering set
We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set-the minimal upward covering set and the minimal downward covering set-unless P equals NP. Finally, we observe a strong relationship between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Laffond G. & Laslier J. F. & Le Breton M., 1993. "The Bipartisan Set of a Tournament Game," Games and Economic Behavior, Elsevier, vol. 5(1), pages 182-201, January.
- Laffond G. & Laslier, J. F. & Le Breton, M., 1996.
"Condorcet choice correspondences: A set-theoretical comparison,"
Mathematical Social Sciences,
Elsevier, vol. 31(1), pages 59-59, February.
- Laffond, Gilbert & Laslier, Jean Francois & Le Breton, Michel, 1995. "Condorcet choice correspondences: A set-theoretical comparison," Mathematical Social Sciences, Elsevier, vol. 30(1), pages 23-35, August.
- B. Dutta & J-F. Laslier, 1998.
"Comparison functions and choice correspondences,"
THEMA Working Papers
98-12, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
- Bordes, Georges, 1983. "On the possibility of reasonable consistent majoritarian choice: Some positive results," Journal of Economic Theory, Elsevier, vol. 31(1), pages 122-132, October.
- Josep E. Peris & BegoÓa Subiza, 1999.
"Condorcet choice correspondences for weak tournaments,"
Social Choice and Welfare,
Springer;The Society for Social Choice and Welfare, vol. 16(2), pages 217-231.
- Josep Enric Peris Ferrando & Begoña Subiza Martínez, 1997. "Condorcet choice correspondences for weak tournaments," Working Papers. Serie AD 1997-05, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
- van Damme, Eric, 1998. "On the State of the Art in Game Theory: An Interview with Robert Aumann," Games and Economic Behavior, Elsevier, vol. 24(1-2), pages 181-210, July.
- Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 523-528, 06.
- Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, February.
When requesting a correction, please mention this item's handle: RePEc:eee:matsoc:v:56:y:2008:i:2:p:254-268. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu)
If references are entirely missing, you can add them using this form.