자연계열 3번

이동통신 사업자 3개사와 휴대폰 제조사 3개사가 서로 전략적인 제휴관계를 맺으려고 한다. 각 이동통신 사업자는 3개의 휴대폰 제조사를 선호도에 따라서 순위를 매기고 각 휴대폰 제조사도 선호도에 따라 이동통신 사업자들에 대한 순위를 매긴다고 하자. 그 결과 아래 표와 같이 [가] 이동통신 사업자가 제일 선호하는 휴대폰 제조사는 [B]이고, 두 번째로 선호하는 휴대폰 제조사는 [A]였다. 또한 [A] 휴대폰 제조사의 첫 번째 선호도는 [가] 이동통신 사업자이고, 두 번째 선호도는 [나] 이동통신 사업자였다.

모든 이동통신 사업자와 휴대폰 제조사는 빠짐없이 제휴를 맺어야만 하고, 불안정한 제휴가 없는 <안정된 상황>을 이루어야 한다. 이 때 <불안정한 제휴>란 한 이동통신 사업자와 한 휴대폰 제조사가 서로를 현재 자신들과 맺어진 제휴사보다 더 선호하는 제휴관계를 말한다. 예를 들어 {(가, C), (나, B), (다, A)}와 같은 상황에서 (나, B)는 불안정한 제휴가 된다. 왜냐하면 [나] 사업자는 맺어진 제휴사인 [B] 제조사보다 [A] 제조사를 더 선호하고, 또한 [A] 제조사도 맺어진 제휴사인 [다] 사업자보다 [나] 사업자를 더 선호하기 때문이다.Correction. 불안정한 제휴의 예시로 든 ‘(나, B)’는 ‘(나, A)’의 오기이다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.

(1) 위의 표를 바탕으로 이동통신 사업자 3개사와 휴대폰 제조사 3개사이에서 안정된 상황을 이루는 제휴가 존재하는지 판정하시오.

(2) 다음과 같은 순환적인 방법을 적용하면 안정된 상황을 항상 이룰 수 있다고 한다.① 이동통신 사업자와 휴대폰 제조사는 각각 상대에 대한 선호도 리스트를 작성한다.② 각 이동통신 사업자는 자신의 선호도 리스트에 남아있는 휴대폰 제조사 중에서 선호하는 제조사 하나를 선택한다.③ 각 휴대폰 제조사는 ②에서 자신을 선택한 이동통신 사업자 중에서 자신이 가장 선호하는 사업자 하나를 선택한다.④ ③에서 선택되지 않은 이동통신 사업자들은 각자가 가진 선호도 리스트에서 자신을 선택하지 않은 휴대폰 제조사를 제거한다.⑤ 이동통신 사업자가 모두 선택될 때까지 ②~④의 과정을 되풀이한다.

일반적인 경우에 대하여, 위의 과정을 모두 완료하였을 때 불안정한 제휴가 존재하지 않는 이유를 설명하시오.