Counting Combinatoral Choice Rules
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.
|Date of creation:||Apr 2004|
|Date of revision:|
|Publication status:||Published: Published in Games and Economic Behavior 58 (2007) 231-245.|
|Contact details of provider:|| Postal: |
Phone: 626 395-4065
Fax: 626 405-9841
Web page: http://www.hss.caltech.edu/ss
|Order Information:|| Postal: Working Paper Assistant, Division of the Humanities and Social Sciences, 228-77, Caltech, Pasadena CA 91125|
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.:
- Carmen Beviá Baeza & José Angel Silva Reus, 1997.
"Buying several indivisible goods,"
Working Papers. Serie AD
1997-27, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
- Carmen Bevia & Martine Quinzii & JosŽ A. Silva, . "Buying Several Indivisible Goods," Department of Economics 97-20, California Davis - Department of Economics.
- Martine Quinzii & Carmen Bevia & JosÅ A. Silva, 2003. "Buying Several Indivisible Goods," Working Papers 9720, University of California, Davis, Department of Economics.
- Roth, Alvin E, 1984. "Stability and Polarization of Interests in Job Matching," Econometrica, Econometric Society, vol. 52(1), pages 47-57, January.
- repec:cup:cbooks:9780521424585 is not listed on IDEAS
- Kim, Taesung & Richter, Marcel K., 1986. "Nontransitive-nontotal consumer theory," Journal of Economic Theory, Elsevier, vol. 38(2), pages 324-363, April.
- Ralph W. Bailey, 1998. "The number of weak orderings of a finite set," Social Choice and Welfare, Springer, vol. 15(4), pages 559-562.
- Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
- Gul, Faruk & Stacchetti, Ennio, 2000. "The English Auction with Differentiated Commodities," Journal of Economic Theory, Elsevier, vol. 92(1), pages 66-95, May.
- Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
When requesting a correction, please mention this item's handle: RePEc:clt:sswopa:1199. 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: (Victoria Mason)
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.