Boolean d-Attribute Stable Matching (Stable Matching Problem)
Description
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
Parameters
$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 | https://arxiv.org/pdf/1510.06452.pdf | link |