Popularity on the 3D-Euclidean Stable Roommates

Steven Ge, Toshiya Itoh

Institute of Science Tokyo
Department of Mathematical and Computing Science

Content

  • Preliminaries

    • 3D-Euclidean Stable Roommates (3D-EuclidSR)
      • Anecdote
      • Problem Statement
    • Strict Popularity

  • Results

    • Planar and Cubic Exact Cover by 3-Sets Problem (PC-X3C)
    • Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
    • Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$

  • Future Work

Preliminaries

3D-Euclidean Stable Roommates

Andecdote
  • Drones
    • Coordinates in 3D Space
  • Groups of constant size $s$
    • $s=3$
    • Consider drone h
  • Preference only depends on:
    Sum of distances to group members
    • The smaller the sum, the better
Problem Statement
  • Agents $N$
    • Embedding $E: N \rightarrow \mathbb{R}^3$
  • Room size $s \in \mathbb{N}$
    • $s=3$
  • Preference of $a \in N$ only depends on:
    • Sum of distances to room members in $S$
    • $S \succsim_{a} S' \iff \delta(a, S) \leq \delta(a, S')$
  • Game $G = (N, s, E)$

Preliminaries

Popularity$^{\text{[1]}}$

  • Outcomes (Partitioning of Agents)
    • $\pi$
    • $\pi'$
  • $\pi$ is more popular than $\pi'$
    • (Strictly) More $\vee$ than $\wedge$



  • $\pi$ is popular
    • No other outcome $\pi'$ is more popular than $\pi$

  • $\pi$ is strictly popular
    • $\pi$ is more popular than any other outcome $\pi'$

Results

Theorem: strict popularity with room size 3 is co-NP-hard

Results

Theorem: strict popularity with room size 3 is co-NP-hard
Exact Cover by 3-Sets Problem$^{\text{[1]}}$
  • Exact 3-set Cover (X3C)
    • Universe $X = \{1, \dots, m\}$
    • 3-sets $\mathcal{C} = \{C_1, \dots, C_q\}$
      • $C_i \subseteq X$
      • $|C_i| = 3$
    • Does there exist a set $S \subseteq \mathcal{C}$ of 3-sets that partitions $X$?
      • E.g. {$C_1$, $C_2$, $C_4$} is NOT a solution.
      • E.g. {$C_1$, $C_6$} IS a solution.
    • X3C instance $I = (X,\mathcal{C})$.
    • Exact 3-set Cover problem is NP-complete

$X = \{1,2,3,4,5,6\}$

$\mathcal{C} = \left\{\begin{array}{l} ~ \\ ~ \\ ~ \\ ~ \\ ~ \\ \end{array} \right.$
  • $C_1 = \{1,2,3\}$
  • $C_2 = \{1,2,4\}$
  • $C_3 = \{1,3,5\}$
  • $C_4 = \{2,4,6\}$
  • $C_5 = \{3,5,6\}$
  • $C_6 = \{4,5,6\}$
$\left.\begin{array}{l} ~ \\ ~ \\ ~ \\ ~ \\ ~ \\ \end{array} \right\}$

Results

Theorem: strict popularity with room size 3 is co-NP-hard
Planar and Cubic Exact Cover by 3-Sets Problem$^{\text{[1]}}$
  • Exact 3-set Cover (PC-X3C)
    • Universe $X = \{1, \dots, m\}$
    • 3-sets $\mathcal{C} = \{C_1, \dots, C_q\}$
      • $C_i \subseteq X$
      • $|C_i| = 3$
    • Does there exist a set $S \subseteq \mathcal{C}$ of 3-sets that partitions $X$?
      • E.g. {$C_1$, $C_2$, $C_4$} is NOT a solution.
      • E.g. {$C_1$, $C_6$} IS a solution.
    • Planar and Cubic
      • Cubic
        • Each element in $X$ is contained in exactly three 3-sets of $\mathcal{C}$.
      • Planar
        • Corresponding graph is planar.
    • PC-X3C instance $I = (X,\mathcal{C})$.
    • Planar and Cubic Exact 3-set Cover problem is NP-complete

$X = \{1,2,3,4,5,6\}$

$\mathcal{C} = \left\{\begin{array}{l} ~ \\ ~ \\ ~ \\ ~ \\ ~ \\ \end{array} \right.$
  • $C_1 = \{1,2,3\}$
  • $C_2 = \{1,2,4\}$
  • $C_3 = \{1,3,5\}$
  • $C_4 = \{2,4,6\}$
  • $C_5 = \{3,5,6\}$
  • $C_6 = \{4,5,6\}$
$\left.\begin{array}{l} ~ \\ ~ \\ ~ \\ ~ \\ ~ \\ \end{array} \right\}$

Results

Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
  • There exists exactly 1 Permanent popular outcome $\pi_{pp}$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
  • There exists exactly 1 Permanent popular outcome $\pi_{pp}$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
  • There exists 1 reduced outcome $\pi_{S}$ per solution $S$ of $I$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
  • There exists 1 reduced outcome $\pi_{S}$ per solution $S$ of $I$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
  • $I$ has a solution $\Rightarrow$ No strictly popular outcome
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Strategy: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
  • Let $\Pi$ be the set of all outcomes of $G$
  • $I$ has NO a solution $\Rightarrow$ $\pi_{pp}$ is strictly popular

Results

Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
3 Layers
  • Bottom Layer
  • Top Layer
  • Ascending Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Bottom Layer

PC-X3C Instance $I = (X, \mathcal{C})$
  • $\small X = \{1,2,3,4,5,6\}$
  • $\small \mathcal{C} = \{\{1,2,3\}, \{1,2,4\}, \{1,3,5\}, \{2,4,6\}, \{3,5,6\}, \{4,5,6\}\}$$\small ~~~= \{C_1,C_2,C_3,C_4,C_5,C_6\}$
  • (Example from Slide 8)

  • A planar graph with a maximum vertex degree of three can be embedded, in polynomial time, in the grid $\mathbb{Z}^2$ such that:
    • its vertices lie on the integer grid points
    • its edges are drawn using at most one horizontal and one vertical segment in the grid$^{[4]}$
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Top Layer
  • Place 3 vertices in a center that form an equilateral triangle
    •
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Ascending Layer
  • Purpose: The ascending layer connects the bottom layer with the top layer

    •
  • Replace every edge with a chain of vertex triples that form a isosceles triangle with two edges of length 1 and one of $\epsilon$
  • Example from Slide 8, $I = (X,\mathcal{C})$
    • $\small X = \{1,2,3,4,5,6\}$
    • $\small \mathcal{C} = \{\{1,2,3\}, \{1,2,4\}, \{1,3,5\}, \{2,4,6\}, \{3,5,6\}, \{4,5,6\}\}$$\small ~~~= \{C_1,C_2,C_3,C_4,C_5,C_6\}$
Bottom Layer
Ascending Layer
Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
  • For permanent popular outcome $\pi_{pp}$ we have
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Ascending Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Ascending Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Permanent popular outcome $\pi_{pp}$
Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$

Solution $S = \{C_1, C_6\}$

Bottom Layer
Ascending Layer
Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{S}$
  • For reduced outcome $\pi_{S}$ we have
    • For each vertex $v$, $\delta(v, \pi(v))$ is minimized
    • Exactly one per solution $S$ of PC-X3C instance $I$ exists.

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Ascending Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Ascending Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Reduced outcome $\pi_{reduced}$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$

Solution $S = \{C_1, C_6\} = \{\{1,2,3\}, \{4,5,6\}\}$

Bottom Layer
Ascending Layer
Top Layer
Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$

PC-X3C instance $I$ has no solution$\iff$$G$ has a strictly popular outcome $\Box$

Future Work

Equilibrium Concept Room size 3D-Euclidean Stable Roommates (3D-EuclidSR)
Popularity $2$ ?
Strict Popularity $3$ co-NP-hard
Strict Popularity $> 3$ ?
Mixed Popularity $\geq 3$ ?
Popularity $\geq 3$ ?

Bibliography

[1] Gärdenfors, P.: Match making: Assignments based on bilateral preferences. Systems Research and Behavioral Science 20, 166–173 (1975). https://doi.org/10.1002/bs.3830200304, https://onlinelibrary.wiley.com/doi/10.1002/bs.3830200304
[2] Deineko, V. G., & Woeginger, G. J. (2013). Two hardness results for core stability in hedonic coalition formation games. Discrete Applied Mathematics, 161(13-14), 1837-1842.
[3] Chen, J., & Roy, S. (2021). Multi-dimensional stable roommates in 2-dimensional Euclidean space. arXiv preprint arXiv:2108.03868.
[4] Di Battista, G., Liotta, G., & Vargiu, F. (1998). Spirality and optimal orthogonal drawings. SIAM Journal on Computing, 27(6), 1764-1811.

The end

Thank you for your attention!

Appendix

Related Work

Multidimensional Stable Roommates Problem with metric preferences$^{[2]}$

Metric Space (Room size > 2)
Core Stability NP-Complete


2D-Euclidean Stable Roommates Problem$^{[3]}$

2D-Euclidean Space (Room size > 2)
Core Stability NP-Complete

Appendix

Results

Theorem: strict popularity with room size 3 is co-NP-hard
Reduction Sketch: PC-X3C $I$ $\rightarrow$ 3D-EuclidSR $G$
Top Layer
  • Place 3 vertices in a center that form an equilateral triangle
    •