Computer Science - Computer Science and Game Theory
In two-sided matching markets, the agents are partitioned into two sets. Each
agent wishes to be matched to an agent in the other set and has a strict
preference over these potential matches. A matching is stable if there are no
blocking pairs, i.e., no pair of agents that prefer each other to their
assigned matches. In this paper we study a variant of stable matching motivated
by the fact that, in most centralized markets, many agents do not have direct
communication with each other. Hence even if some blocking pairs exist, the
agents involved in those pairs may not be able to coordinate a deviation. We
model communication channels with a bipartite graph between the two sets of
agents which we call the social graph, and we study socially stable matchings.
A matching is socially stable if there are no blocking pairs that are connected
by an edge in the social graph. Socially stable matchings vary in size and so
we look for a maximum socially stable matching. We prove that this problem is
NP-hard and, assuming the unique games conjecture, hard to approximate within a
factor of 3/2-{\epsilon}, for any constant {\epsilon}>0. We complement the
hardness results with a 3/2-approximation algorithm.
Metrics
6 Record Views
Details
Title
Socially Stable Matchings
Creators
Georgios Askalidis
Nicole Immorlica
Emmanouil Pountourakis
Publication Details
arXiv.org
Resource Type
Preprint
Language
English
Academic Unit
Computer Science (Computing)
Other Identifier
991021869108404721
Research Home Page
Browse by research and academic units
Learn about the ETD submission process at Drexel
Learn about the Libraries’ research data management services