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.:
- 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.
- 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.
- 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).
- Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, 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.
- 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.
- Bhaskar Dutta & Jean-Francois Laslier, 1999.
"Comparison functions and choice correspondences,"
Social Choice and Welfare,
Springer;The Society for Social Choice and Welfare, vol. 16(4), pages 513-532.
- 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.
- 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.
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: (Shamier, Wendy)
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.