Popularity Roommate Diversity Problem

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 #Japanese students in groups
- $k$ does not speak nor wants to practice English
  - $1 \succ$ $\frac{2}{3}$ $\succ$ $\frac{1}{3}$
- $a$ does not speak, but wants to practice Japanese
  - $\frac{1}{3}$ $\succ$ $\frac{2}{3}$ $\sim$ $0$

Problem Statement

Agents
- Set of Red Agents $R$
- Set of Blue Agents $B$
Room size s
- $s=3$
Preference only depends on #red agents in rooms
- $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 = ($ $,$ $,s, (\succsim_a)_{a \in }$ $_\cup$ $)$

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 = ($ $,$ $,s, (\succsim_a)_{a \in }$ $_\cup$ $)$
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. $\succ$ $_a$ $\frac{2}{3}$ $\sim$ $0$
    - $=\{\frac{1}{3}\}$
    - $=\{\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}$
- 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\}$
- Does there exist a set $S \subseteq C$ of 3-sets that partitions $X$ ?
- 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 = ($ $,$ $,s, (\succsim_a)_{a \in }$ $_\cup$ $)$

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:
- Redundant Agents $R_j^{red} = \{r_j^1, \dots, r_j^{5j-2}\}$
- Filling Agents $B_j^{fill} = \{b_j^1, \dots, b_j^{s-(5j-2)-3}\}$
- Additional Agents $B_j^{add} = \{\tilde{b}_j^1, \tilde{b}_j^2, \tilde{b}_j^3\}$
Evening Agents $B^{even}$
Monolithic Agents $R^{mon} = \{r_{mon}^1, \dots, r_{mon}^{5(q+1)+1}\}$
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