On Transversals and Systems of Distinct Representatives

Leonid Hurwicz and Stanley Reiter

No 1176R, Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science

Abstract: 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: 1997-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.kellogg.northwestern.edu/research/math/papers/1176.pdf main text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nwu:cmsems:1176r

Ordering information: This working paper can be ordered from

Access Statistics for this paper

More papers in Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science Center for Mathematical Studies in Economics and Management Science, Northwestern University, 580 Jacobs Center, 2001 Sheridan Road, Evanston, IL 60208-2014. Contact information at EDIRC.
Bibliographic data for series maintained by Fran Walker ( this e-mail address is bad, please contact ).