Stable Marriage in Euclidean Space

We study stable marriage problems in the 𝑑-Euclidean space. Under this setting, each agent is represented as a point in the 𝑑dimensional space, and for each agent 𝑎, the preference of 𝑎 is based on the sorting according to the Euclidean distances between 𝑎 and agents from the opposite gender. Let 𝛿 (𝑎, 𝑏) being the Euclidean distance between two points 𝑎 and 𝑏. A man 𝑢 prefers a woman 𝑤 1 to another woman 𝑤 2 if and only if 𝛿 (𝑢, 𝑤 1) < 𝛿 (𝑢, 𝑤 2). If 𝛿 (𝑢, 𝑤 1) = 𝛿 (𝑢, 𝑤 2), then 𝑢 ranks 𝑤 1 and 𝑤 2 indifferently, and we say there is a tie between 𝑤 1 and 𝑤 2 in 𝑢's preference list. A lot of variants of Stable Marriage with Ties (SMT) have been shown to be NP-complete when ties occur in preference lists. In this paper, we study the most famous hard variants of SMT in 𝑑-Euclidean space, namely, Regret-SMT, Forced-SMT, and Egalitarian-SMT. We prove that with 𝑑 = 1, Forced-SMT and Regert-SMT can be solved in polynomial-time, while with 𝑑 = 2, all of the three problems are NP-hard. Then we show that if the preference list can be incomplete (agents are allowed to not give a full rank of the opposite gender), the three problems and another variant Max-SMTI are NP-hard even with 𝑑 = 1. Finally, we provide an algorithm to recognize whether a given preference profile can be embedded into 1-Euclidean space.