IDEAS home Printed from https://ideas.repec.org/p/clt/sswopa/1199.html

Counting Combinatoral Choice Rules

Author

Listed:
  • Echenique, Federico

Abstract

I count the number of combinatorial choice rules that satisfy certain properties: Kelso-Crawford substitutability, and independence of irrelevant alternatives. The results are important for two-sided matching theory, where agents are modeled by combinatorial choice rules with these properties. The rules are a small, and asymtotically vanishing, fraction of all choice rules. But they are still exponentially more than the preference relations over individual agents---which has positive implications for the Gale-Shapley algorithm of matching theory.

Suggested Citation

  • Echenique, Federico, 2004. "Counting Combinatoral Choice Rules," Working Papers 1199, California Institute of Technology, Division of the Humanities and Social Sciences.
    • Handle: RePEc:clt:sswopa:1199
    as

    Download full text from publisher

    File URL: http://www.hss.caltech.edu/SSPapers/sswp1199c.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    Citations

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


    Cited by:

    1. is not listed on IDEAS
    2. Samson Alva & Battal Dou{g}an, 2021. "Choice and Market Design," Papers 2110.15446, arXiv.org, revised Nov 2021.
    3. Doğan, Battal & Imamura, Kenzo & Yenmez, M. Bumin, 2025. "Market design with deferred acceptance: A recipe for characterizations," Journal of Economic Theory, Elsevier, vol. 228(C).
    4. Battal Dou{g}an & Kenzo Imamura & M. Bumin Yenmez, 2022. "Market Design with Deferred Acceptance: A Recipe for Policymaking," Papers 2209.06777, arXiv.org.
    5. M. Bumin Yenmez, 2014. "College Admissions," GSIA Working Papers 2014-E24, Carnegie Mellon University, Tepper School of Business.
    6. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    7. Yenmez, M. Bumin, 2018. "A college admissions clearinghouse," Journal of Economic Theory, Elsevier, vol. 176(C), pages 859-885.
    8. Hans Peters & Panos Protopapas, 2021. "Set and revealed preference axioms for multi-valued choice," Theory and Decision, Springer, vol. 90(1), pages 11-29, February.
    9. Hideo Konishi & M. Utku Ünver, 2003. "Credible Group Stability in Multi-Partner Matching Problems," Working Papers 2003.115, Fondazione Eni Enrico Mattei.
    10. Juan F. Fung & Chia-Ling Hsu, 2021. "A cumulative offer process for supply chain networks," Review of Economic Design, Springer;Society for Economic Design, vol. 25(1), pages 93-109, June.
    11. Orhan Aygün & Tayfun Sönmez, 2012. "The Importance of Irrelevance of Rejected Contracts in Matching under Weakened Substitutes Conditions," Boston College Working Papers in Economics 805, Boston College Department of Economics.
    12. Koji Yokote & Isa E. Hafalir & Fuhito Kojima & M. Bumin Yenmez, 2023. "Rationalizing Path-Independent Choice Rules," Papers 2303.00892, arXiv.org, revised May 2024.
    13. Mehmet Ekmekci & M. Bumin Yenmez, "undated". "Integrating Schools for Centralized Admissions," GSIA Working Papers 2014-E20, Carnegie Mellon University, Tepper School of Business.
    14. Tam'as Fleiner & Zsuzsanna Jank'o & Ildik'o Schlotter & Alexander Teytelboym, 2018. "Complexity of Stability in Trading Networks," Papers 1805.08758, arXiv.org, revised Feb 2019.
    15. Segal, Ilya, 2007. "The communication requirements of social choice rules and supporting budget sets," Journal of Economic Theory, Elsevier, vol. 136(1), pages 341-378, September.
    16. Doğan, Battal & Yenmez, M. Bumin, 2019. "Unified versus divided enrollment in school choice: Improving student welfare in Chicago," Games and Economic Behavior, Elsevier, vol. 118(C), pages 366-373.
    17. Tam'as Fleiner & Zsuzsanna Jank'o & Akihisa Tamura & Alexander Teytelboym, 2015. "Trading Networks with Bilateral Contracts," Papers 1510.01210, arXiv.org, revised May 2018.
    18. Erdil, Aytek & Kumano, Taro, 2019. "Efficiency and stability under substitutable priorities with ties," Journal of Economic Theory, Elsevier, vol. 184(C).
    19. Ilya Segal, 2004. "The Communication Requirements of of Social Choice Rules and Supporting Budget Sets," Economics Working Papers 0039, Institute for Advanced Study, School of Social Science.
    20. Alva, Samson, 2018. "WARP and combinatorial choice," Journal of Economic Theory, Elsevier, vol. 173(C), pages 320-333.
    21. Stefano Vannucci, 2011. "Widwast Choice," Department of Economics University of Siena 629, Department of Economics, University of Siena.
    22. Tamás Fleiner & Zsuzsanna Jankó & Ildikó Schlotter & Alexander Teytelboym, 2023. "Complexity of stability in trading networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 629-648, September.
    23. Christopher En & Yuri Faenza, 2025. "All finite lattices are stable matching lattices," Papers 2504.17916, arXiv.org, revised Aug 2025.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:clt:sswopa:1199. See general information about how to correct material in RePEc.

    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.

    We have no bibliographic references for this item. You can help adding them by using 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Victoria Mason (email available below). General contact details of provider: http://www.hss.caltech.edu/ss .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.