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


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a600700.pdf


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