Popularity on the Roommate Diversity Problem

Steven Ge and Toshiya Itoh

Tokyo Institute of Technology
Department of Mathematical and Computing Science

Content

  • Preliminaries

    • Roommate Diversity Problem
      • Anecdote
      • Problem Statement
      • Dichotomous Preferences
    • Popularity

  • Results

    • Result Summary
    • Room Size 2
    • Hardness
      • Exact Cover by 3-Sets Problem
      • Strict Popularity

  • Future Work

Roommate Diversity Problem$^{\text{[1]}}$

Andecdote
  • International class
    • Japanese students
    • International students
  • Groups of constant size $s$
    • $s=3$
  • Preference only depends on $\frac{\#\text{Japanese students in group}}{s}$
    • $k$ does not speak nor wants to practice English
      • $1 \succ$$_k$ $\frac{2}{3}$ $\succ$$_k$ $\frac{1}{3}$
    • $a$ does not speak, but wants to practice Japanese
      • $\frac{1}{3}$ $\succ$$_a$ $\frac{2}{3}$ $\sim$$_a$ $0$
Problem Statement
  • Agents
    • Set of Red Agents $R$
    • Set of Blue Agents $B$
  • Room size $s$
    • $s=3$
  • Preference only depends on $\frac{\#\text{red agents in room}}{s}$
    • $a \in \color{red}{R} \color{black}\cup \color{blue}{B}$
    • $\succsim_{a}$ Complete transitive weak order over $D = \{\frac{j}{s}| j \in [0,s]\}$
  • Game $G = ($$R$$,$$B$$,s, (\succsim_a)_{a \in }$$_R$$_\cup$$_B$$)$
Dichotomous Preferences
  • Agents
    • Set of Red Agents $R$
    • Set of Blue Agents $B$
  • Room size $s$
    • $s=3$
  • Preference only depends on $\frac{\#\text{red agents in room}}{s}$
    • $a \in \color{red}{R} \color{black}\cup \color{blue}{B}$
    • $\succsim_{a}$ Complete transitive weak order over $D = \{\frac{j}{s}| j \in [0,s]\}$
  • Game $G = ($$R$$,$$B$$,s, (\succsim_a)_{a \in }$$_R$$_\cup$$_B$$)$
  • Preference of agent $a \in \color{red}{R} \color{black}\cup \color{blue}{B}$ is dichotomous
    • $D$ can be partitioned into $D_a^+$ and $D_a^-$
      • $a$ ''likes'' the fractions in $D_a^+$
      • $a$ ''hates'' the fractions in $D_a^-$
      • E.g. $\frac{1}{3}$ $\succ$$_a$ $\frac{2}{3}$ $\sim$$_a$ $0$

        • $D^+_{\color{blue}a}$$=\{\frac{1}{3}\}$
        • $D^-_{\color{blue}a}$$=\{\frac{2}{3}, 0\}$

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

  • Outcomes
    • $\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'$
    • $\pi$ is the only popular outcome

  • $p$ is mixed popular
    • $p$ is a probability distribution over all possible outcomes
    • $p$ is expected to be more popular than any other probability distribution

Results Summary

Setting Room size Preferences Results Proceedings Future Work
Popularity $2$ Unrestricted
  • P
  • Popular outcome is GUARANTEED to exist
  • Popular outcome computable in polynomial time
 Section 3
Strict Popularity $\geq 3$ Dichotomous preferences
  • co-NP-hard
 Section 4
  • Completeness
  • Strict Preferences
Mixed Popularity $\geq 3$ Dichotomous preferences
  • P
  • Mixed Popular outcome is GUARANTEED to exist
  • Mixed Popular outcome CANNOT be computed in polynomial time, unless P=NP
 Section 5
  • Strict Preferences
  • (Parameterized Complexity)
Popularity $\geq 3$ Trichotomous preferences
  • co-NP-hard
 Section 6
  • Completeness
  • Dichotomous Preferences
  • Strict Preferences
  • Parameterized Complexity

Room Size 2

  • Game $G = ($$R$$,$$B$$,2, (\succsim_a)_{a \in }$$_R$$_\cup$$_B$$)$
    • $s=2$
  • 3 possible preference types
    • Prefers to be paired with OWN color
    • Prefers to be paired with OTHER color
    • Indifferent
  • Weighted complete graph $G' = (\color{red}R\color{black}\cup\color{blue}B\color{black}, E, w)$
    • $w(x,y) = \begin{cases} ~\\ ~ \\ ~ \\ \end{cases}$
      • $\small 2~~~~ \{x,y\} \text{ liked by both } x \mathbf{\text{ AND }} y$
      $\small 1~~~~ \{x,y\} \text{ liked by both } x \mathbf{\text{ XOR }} y$
      $\small 0~~~~ \{x,y\} \text{ disliked by both } x \mathbf{\text{ AND }} y$

    • E.g. $\{\color{blue}a\color{black},\color{blue}b\color{black}\}$
      • $0 \succ_{\color{blue}a} \frac{1}{2}$
      • $0 \prec_{\color{blue}b} \frac{1}{2}$
      • $w(\color{blue}a\color{black},\color{blue}b\color{black}) = 1$

      • $0 \succ_{\color{blue}a} \frac{1}{2}$
      • $0 \sim_{\color{blue}b} \frac{1}{2}$
      • $w(\color{blue}a\color{black},\color{blue}b\color{black}) = 2$
  • Maximum weight perfect matching $M$ of $G'$ is popular!
    • $M$ can be found in polynomial time

  • Popularity on Stable Roommates Problem (room size 2)
    • More general problem (unrestricted preferences)
    • NP-hard

Hardness

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

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

$C = \left\{\begin{array}{l} ~ \\ ~ \\ ~ \\ ~ \\ ~ \\ \end{array} \right.$
  • $C_1 = \{1,2,3\}$
  • $C_2 = \{2,3,4\}$
  • $C_3 = \{1,2,5\}$
  • $C_4 = \{2,5,6\}$
  • $C_5 = \{1,5,6\}$
$\left.\begin{array}{l} ~ \\ ~ \\ ~ \\ ~ \\ ~ \\ \end{array} \right\}$
Strict Popularity
X3C Instance $I = (X, C)$
  • $\small X = \{1,2,3,4,5,6\}$
  • $\small C = \{\{1,2,3\}, \{2,3,4\}, \{4,5,6\}\}$
    $\small ~~~= \{C_1,C_2,C_3\}$

Roommate Diversity Game $G = ($$R$$,$$B$$,s, (\succsim_a)_{a \in }$$_R$$_\cup$$_B$$)$
  • Set $s = 5(q + 1) + 1 + m$
  • For each $i \in X$, create red set agent $\color{red}r_i$
  • For each $C_j \in C$, create the sets of agents:
    • Red Redundant Agents $R_j^{red} = \{r_j^1, \dots, r_j^{5j-2}\}$
    • Blue Filling Agents $B_j^{fill} = \{b_j^1, \dots, b_j^{s-(5j-2)-3}\}$
    • Blue Additional Agents $B_j^{add} = \{\tilde{b}_j^1, \tilde{b}_j^2, \tilde{b}_j^3\}$
  • Blue Evening Agents $B^{even}$
  • Red Monolithic Agents $R^{mon} = \{r_{mon}^1, \dots, r_{mon}^{5(q+1)+1}\}$
  • Blue Monolithic Agents $B^{mon}= \{b_{mon}^1, \dots, b_{mon}^{s-5(q+1)-1}\}$
  • An agent $a$ has dichotomous preferences

  • Monolithic Outcome $\pi_{mon}$
    • Unique
    • Exists regardless of $I$ having a solution
    • Each agent $a$ in a room with fraction in $D_a^+$
  • Reduced Outcome $\pi_{S}$
    • $S \subseteq C$ is a solution of $I$
    • Exists if and only if $I$ has a solution
    • Each agent $a$ in a room with fraction in $D_a^+$
  • $\pi_{mon}$ and $\pi_S$ are the ONLY popular outcomes of $G$

  • $I$ has no solution$\iff$$G$ has a strictly popular outcome
$\pi_S$, where $S = \{C_1,C_3\}$
$\pi_{mon}$

Future Work

Setting Room size Preferences Results Proceedings Future Work
Popularity $2$ Unrestricted
  • P
  • Popular outcome is GUARANTEED to exist
  • Popular outcome computable in polynomial time
 Section 3
Strict Popularity $\geq 3$ Dichotomous preferences
  • co-NP-hard
 Section 4
  • Completeness
  • Strict Preferences
Mixed Popularity $\geq 3$ Dichotomous preferences
  • P
  • Mixed Popular outcome is GUARANTEED to exist
  • Mixed Popular outcome CANNOT be computed in polynomial time, unless P=NP
 Section 5
  • Strict Preferences
  • (Parameterized Complexity)
Popularity $\geq 3$ Trichotomous preferences
  • co-NP-hard
 Section 6
  • Completeness
  • Dichotomous Preferences
  • Strict Preferences
  • Parameterized Complexity
Setting Room size Preferences Results Proceedings Future Work
Popularity $2$ Unrestricted
  • P
  • Popular outcome is GUARANTEED to exist
  • Popular outcome computable in polynomial time
 Section 3
Strict Popularity $\geq 3$ Dichotomous preferences
  • co-NP-hard
 Section 4
  • Completeness
  • Strict Preferences
Mixed Popularity $\geq 3$ Dichotomous preferences
  • P
  • Mixed Popular outcome is GUARANTEED to exist
  • Mixed Popular outcome CANNOT be computed in polynomial time, unless P=NP
 Section 5
  • Strict Preferences
  • Parameterized Complexity
Popularity $\geq 3$ Trichotomous preferences
  • co-NP-hard
 Section 6
  • Completeness
  • Dichotomous Preferences
  • Strict Preferences
  • Parameterized Complexity

Bibliography

[1] Boehmer, N., Elkind, E.: Stable Roommate Problem with Diversity Preferences. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI’20 (2021). https://doi.org/10.24963/ijcai.2020/14
[2] 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
[3] M.R. Garey; D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.

The end

Thank you for your attention!