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.
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.:
- 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.
- 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.
- Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, February.
- 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).
- 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.
- 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.
- 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.
- 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.
- 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.
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 references are entirely missing, you can add them using this form.