On Transversals and Systems of Distinct Representatives
A transversal generated by a system of distinct representatives (SDR) for a colection of sets consists of an element from each set (its representative) such that the representative uniquely identifies the set it belongs to. Theorem 1 gives a necessary and sufficient condition that an arbitrary collection, finite or infinite, of sets, finite or infinite, have an SDR. The proof is direct, short, and does not use transfinite induction. A Corollary to Theorem 1 shows explicitly the application to matching problems. In the context of designing decentralized economic mechanisms it turned out to be important to know when one can construct an SDR for a collection of sets that cover the parameter space characterizing a finite number of econbomic agents. The condition of Theorem 1 is readily verifiable in that economic context. Theorems 2-5 give different characterizations of situations in which the collection of sets is a partiton. This is of interest because partitions have special properties of informational efficiency.
|Date of creation:||Jan 1997|
|Date of revision:|
|Contact details of provider:|| Postal: Center for Mathematical Studies in Economics and Management Science, Northwestern University, 580 Jacobs Center, 2001 Sheridan Road, Evanston, IL 60208-2014|
Web page: http://www.kellogg.northwestern.edu/research/math/
More information through EDIRC
|Order Information:|| Email: |
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.:
- Reichelstein, Stefan & Reiter, Stanley, 1988. "Game Forms with Minimal Message Spaces," Econometrica, Econometric Society, vol. 56(3), pages 661-92, May.
- Hurwicz, Leonid & Radner, Roy & Reiter, Stanley, 1975.
"A Stochastic Decentralized Resource Allocation Process: Part I,"
Econometric Society, vol. 43(2), pages 187-221, March.
- Hurwicz, Leonid & Radner, Roy & Reiter, Stanley, 1975. "A Stochastic Decentralized Resource Allocation Process: Part II," Econometrica, Econometric Society, vol. 43(3), pages 363-93, May.
When requesting a correction, please mention this item's handle: RePEc:nwu:cmsems:1176r. 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: (Fran Walker)
If references are entirely missing, you can add them using this form.