Jealousy Graphs: Structure and Complexity of Decentralized Stable Matching

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2013
Accession Number
ADA600700

Entities

People

  • Daniel Moeller
  • Moshe Hoffman
  • Ramamohan Paturi

Organizations

  • University of California, San Diego

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Convergence
  • Decomposition
  • Dynamics
  • Information Operations
  • Jealousy
  • Markov Chains
  • Military Research
  • Polynomials
  • Probability
  • Sequences
  • Social Networks
  • Structural Properties
  • Transitions
  • Universities

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Distributed Systems and Data Platform Development
  • Economics