Accession Number : ADA600700
Title : Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching
Descriptive Note : Technical rept.
Corporate Author : CALIFORNIA UNIV SAN DIEGO LA JOLLA
Personal Author(s) : Moeller, Daniel ; Paturi, Ramamohan ; Hoffman, Moshe
Report Date : Jan 2013
Pagination or Media Count : 18
Abstract : The stable matching problem has many applications to real world markets and e cient centralized algorithms are known. However, little is known about the decentralized case. Several natural randomized algorithmic models for this setting have been proposed but they have worst case exponential time in expectation. We present a novel structure associated with a stable matching on a matching market. Using this structure, we are able to provide a ner analysis of the complexity of a subclass of decentralized matching markets.
Descriptors : *ALGORITHMS , DECENTRALIZATION , DECOMPOSITION , GRAPHS , MARKETING , MATCHING , STABILITY
Subject Categories : Numerical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE