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