Advanced Search
MyIDEAS: Login

Computing the minimal covering set

Contents:

Author Info

  • Brandt, Felix
  • Fischer, Felix
Registered author(s):

    Abstract

    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.

    Download Info

    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.
    File URL: http://www.sciencedirect.com/science/article/B6V88-4SF301B-1/2/c44c1e2d68ec7e6646dfe1e9ec8e55e7
    Download Restriction: Full text for ScienceDirect subscribers only

    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.

    Bibliographic Info

    Article provided by Elsevier in its journal Mathematical Social Sciences.

    Volume (Year): 56 (2008)
    Issue (Month): 2 (September)
    Pages: 254-268

    as in new window
    Handle: RePEc:eee:matsoc:v:56:y:2008:i:2:p:254-268

    Contact details of provider:
    Web page: http://www.elsevier.com/locate/inca/505565

    Related research

    Keywords: Social choice theory Minimal covering set Essential set Uncovered set Computational complexity;

    References

    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.:
    as in new window
    1. 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.
    2. 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.
    3. Dutta, Bhaskar, 1988. "Covering sets and a new condorcet choice correspondence," Journal of Economic Theory, Elsevier, vol. 44(1), pages 63-80, February.
    4. Bhaskar Dutta & Jean-Francois Laslier, 1999. "Comparison functions and choice correspondences," Social Choice and Welfare, Springer, vol. 16(4), pages 513-532.
    5. Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer, vol. 20(3), pages 523-528, 06.
    6. 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).
    7. 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.
    8. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Felix Brandt & Felix Fischer & Paul Harrenstein & Maximilian Mair, 2010. "A computational analysis of the tournament equilibrium set," Social Choice and Welfare, Springer, vol. 34(4), pages 597-609, April.
    2. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    3. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2013. "Computing tournament solutions using relation algebra and RelView," European Journal of Operational Research, Elsevier, vol. 226(3), pages 636-645.
    4. repec:hal:journl:halshs-00639942 is not listed on IDEAS
    5. Rudolf Berghammer & Agnieszka Rusinowska & Harrie De Swart, 2012. "Computing tournament solutions using relation algebra and RelView," Working Papers hal-00756696, HAL.
    6. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    7. John Duggan, 2013. "Uncovered sets," Social Choice and Welfare, Springer, vol. 41(3), pages 489-535, September.

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    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 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.