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.
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, 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.
- 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.
- 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.
- 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.
- Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer, vol. 20(3), pages 523-528, 06.
- 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, vol. 16(2), pages 217-231.
- Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, February.
- 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.
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: (Zhang, Lei)
If references are entirely missing, you can add them using this form.