Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Socially Stable Matchings
arXiv.org
23 Feb 2013
Abstract
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 AskalidisNicole ImmorlicaEmmanouil Pountourakis
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991021869108404721