The Stable Triamorous Arrangement Problem

In class we saw the stable marriage algorithm $($this algorithm and its analysis can be found in an accom$-$

panying handout$),$ where the elements of two sets are paired together based on their preferences. In this

exercise, you will adapt this algorithm so that it can be applied to find an alternative relationship structure

which is popular at Burning Man. Here the input will be three sets $A=\{A_1,$dots,$A_n\},B=\{B_1,$dots,$B_n\}$

and $C=\{C_1,$dots,$C_n\},$ all of the same size, and for each element of each set we have a preference list. So$,$

for example, for each AinA, there is a set $P^A$ which lists $A\text{'}$s preference on the set $BC.$ So$,$ for example,

we might have

$P^A=\{(B_1,C_1)>(B_3,C_5)>(B_4,C_1)>$cdots$\}$

if $A\text{'}$s favorite pair is $(B_1,C_1),$ second favorite pair is $(B_3,C_5),$ and so on$.$ Likewise, for BinB or CinC there

are preference lists $P^B$ and $P^C$ which list, respectively, B$\text{'}$s and $C\text{'}$s preferences on the elements of $AC$ and

$AB.$ Design an algorithm which, given such sets and preferences, finds a stable triamorous arrangement,

$M,$ which is a set of triples $(A,B,C)$ such that every AinA,BinB and CinC appear in exactly one triple, and

moreover so that the arrangement has no unstable throuple. An unstable throuple is a triple $(A,B,C)!$inM

such that each item of the triple prefers the other two to their specified pair in M$.$ So$,$ for example, A prefers

$(B,C)$ to the $(B^{\text{'}},C^{\text{'}})$ that $A$ is paired with in $M($and similarly for $B$ and $C).$ Analyze your algorithm $($i$.$e$.,$

compute runtime and additionally prove that your algorithm outputs a stable triamorous arrangement$).$