Boolean d-Attribute Stable Matching (Stable Matching Problem)

From Algorithm Wiki
Revision as of 08:23, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


SMP in the d-attribute model. In the d-attribute model, we assume that there are d different attributes (e.g. income, height, sense of humor, etc.) with a fixed, possibly objective, ranking of the men for each attribute. Each woman’s preference list is based on a linear combination of the attributes of the men, where each woman can have different weights for each attribute. Some women may care more about, say, height whereas others care more about sense of humor. Men’s preferences are defined analogously.

Related Problems

Generalizations: Stable Marriage Problem

Related: Almost Stable Marriage Problem, Stable Roommates Problem, Stable Matching Verification, Stable Pair Checking


$n$: number of men and number of women

$d$: number of attributes

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem Implication Year Citation Reduction
Maximum Inner Product Search assume: OVH
then: for an $\epsilon > {0}$ there is a $c$ such that finding a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$.
2016 link