경제학으로 해석한 헝가리안 알고리즘

Photo by Angele Kamp on Unsplash

할당 문제(assignment problem)는 $n$ 명의 노동자와 $n$ 개의 작업 그리고 각 노동자를 각 작업에 할당했을 때 발생하는 비용이 모두 주어졌을 때, 각 노동자를 하나의 작업에 중복 없이 모두 최소의 비용으로 할당하는 방법을 찾는 문제이며, 헝가리안 알고리즘(Hungairan algorithm)은 이 문제를 해결하는 가장 유명한 방법입니다. 할당 문제와 헝가리안 알고리즘은 조합론적 최적화(combinatorial optimization) 분야의 근간을 이루는 개념 중 하나일 뿐 아니라 산업 공학(industrial engineering), 운용 과학(operations research) 등 여러 실용적인 분야에서도 널리 활용됩니다.

 

이렇게 다양한 분야에서 활약하는 할당 문제와 헝가리안 알고리즘이 경제학과도 큰 관련이 있다는 사실을 최근 알게 되었습니다. 이번 포스트에서는 경제학적 관점에서 헝가리안 알고리즘이 어떻게 해석될 수 있는지 한번 알아 보도록 하겠습니다. 할당 문제와 헝가리안 알고리즘의 개괄적인 내용은 다른 글에서도 다루었으니, 함께 보시는 것도 추천 드립니다.

할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm)

 

저는 컴퓨터과학을 전공하는 학생입니다. 경제학은 교양 수업으로 경제학 입문을 들은 것이 전부입니다. 그마저도 다 까먹었고요. 수요 곡선과 공급 곡선이 만나는 점이 가격이 된다는 정도의 상식만 머릿속에 남아 있습니다. 따라서 아래에서 사용되는 용어들은 실제 경제학 분야에서 사용되는 것들이 아닐 수 있습니다. 그냥 제가 공부하면서 제 방식대로 이해한 내용을 기술한 것이니 읽으실 때 참고 바랍니다. 혹여 치명적인 오류가 있는 경우에는 댓글로 알려 주시면 감사하겠습니다.

문제 모델

다음과 같은 모델을 생각해 봅시다. $n$ 개의 물건이 시장에 나왔고 꼭 $n$ 명의 매수자가 있다고 합시다. 매수자 집합은 $I$, 물건 집합은 $J$라고 하겠습니다. 각 매수자 $i\in I$는 각 물건 $j\in J$를 $v_{i,j}\in {\mathbb{R}}_{+}$의 가치로 생각하고 있습니다. 논의를 간단히 하기 위해 모든 가치는 0 이상이라고 하겠습니다.

 

우리는 각 물건을 모든 매수자에게 하나씩 할당해 주고자 합니다. 어떻게 할당해 주는 것이 가장 좋을까요? 이를 평가할 척도는 다양하겠지만, 이번 글에서는 공리주의적인 시각에서 접근해 보고자 합니다. 바로 각 매수자가 얻은 가치의 합이 최대가 되도록 만드는 것입니다. 다시 말해, 각 매수자 $i$가 할당 받은 물건을 $\sigma (i)$라고 했을 때, $$\sum _{i\in I}{v}_{i,\sigma (i)}$$를 최대로 만드는 일대일 대응(bijection) $\sigma :I\to J$를 찾는 것입니다.^[ㄱ]

 

문제는 매수자들이 우리가 할당하는 대로 고분고분 인정하고 받아들일 사람들이 아니라는 것입니다. 이들은 매우 '이기적'이어서 만약 자신이 할당 받은 물건보다 다른 매수자에게 할당된 물건이 자신에게 더 좋다면 길길이 날뛸 요량입니다. 이를 해결하는 방법은 무엇일까요? 많은 사람이 희소한 물건을 원하는 상황을 경제학적인 관점에서 우리는 경쟁이 발생하였다고 말합니다. 그리고 경쟁을 해소하는 경제학적인 방법은 희소한 물건에 가격을 붙이는 것이죠. 가격이 생기면 그만큼의 가치는 없다고 생각하는 사람들은 더이상 경쟁에 참가하지 않을 것이고, 해당 가격을 지불할 용의가 있는 사람들만 남을 것입니다. 이러한 방법으로 경쟁을 해소할 수 있습니다.

 

우리 모델에서도 똑같이 경쟁이 발생한 물건들에 적절한 가격을 붙여 모든 매수자들이 자신이 할당 받은 물건에 만족하도록 만들어 보겠습니다. 좀더 자세히 설명해 보죠. 각 물건 $j$에 $p_j$의 가격이 붙었다고 합시다. 그러면 매수자 $i$는 해당 물건을 할당 받았을 때 $$v_{i,j}-p_j$$의 이득을 보았다고 생각할 것입니다. 이를 현재 가격 $p$에서 물건 $j$에 대한 매수자 $i$의 효용(utility)이라고 부르겠습니다. 만일 자신이 할당 받은 물건 $\sigma (i)$가 자신에게 있어 최대의 효용을 달성한다면, 다시 말해 임의의 물건 $j$에 대해 $$v_{i,\sigma (i)}-p_{\sigma (i)}\ge v_{i,j}-p_j$$를 만족한다면, 이 매수자는 만족합니다. 모든 매수자가 만족한 상태를 우리는 평형(equilibrium)이라고 부릅니다. 과연 가격을 어떻게 정해야 평형을 이루면서 매수자들이 얻은 가치의 합이 최대가 되도록 만들 수 있을까요?

 

참고로, 우리의 목표는 각 매수자가 얻은 가치의 합 $\sum _{i\in I}{v}_{i,\sigma (i)}$를 최대화 하는 것이지, 가격이 결정된 후 각 매수자가 생각하는 효용의 합 $\sum _{i\in I}(v_{i,\sigma (i)}-p_{\sigma (i)})$를 최대화 하는 것이 아님을 알려 드립니다. 하지만 나중에 이 둘이 아주 큰 연관성이 있음이 밝혀집니다.

알고리즘 개요

우리의 목표는 가격을 통해 모든 매수자가 자신이 할당받은 물건에 만족하는 평형 상태에서 매수자가 얻는 가치의 총합이 최대가 되는 할당을 찾는 것입니다. 하지만 처음부터 해당 가격을 찾는 것은 쉽지 않아 보입니다. 따라서 처음부터 좋은 가격을 딱 제시하는 대신, 아래 방법과 같이 시행착오를 거치면서 가격을 형성해 보겠습니다.

모든 매수자들이 각자의 최대 효용을 얻기 위해 이기적으로 행동하는 시장에서 매수자들끼리 경쟁이 붙은 물건들을 찾는다. 이는 물건의 수보다 해당 물건만 원하는 매수자의 수가 더 많을 때 발생한다. 해당 매수자들이 다른 물건에도 눈독들이도록 경쟁이 붙은 물건의 가격을 적당히 올린다. 이를 경쟁이 없을 때까지 반복한다.

일견 합리적으로 보이는 위 방법에는 '컴퓨터과학'적이지 못한 부분이 두 가지 있습니다.

• 어떻게 하면 현재 가격에서 경쟁이 붙은 물건들을 찾을 수 있는가?
• 경쟁이 붙은 물건들의 가격을 얼마큼 올려야하는가?

또한 아래의 항목들도 엄밀히 증명해야 위 방법이 올바른 방법이라고 결론을 지을 수 있습니다.

• 언젠가는 평형 상태를 주는 가격에 도달하는가? 즉, 위 방법이 언젠가는 끝나는가?
• 평형 상태에 도달했을 때 매수자가 얻은 가치의 합이 최대가 되는가?

위 질문에 대한 답변을 아래에서 차근히 드리도록 하겠습니다.

경쟁이 붙은 물건 찾기

앞에서 제시한 방법에서 첫 번째로 컴퓨터과학적이지 못한 부분은 경쟁이 붙은 물건들을 어떻게 하면 찾을 수 있는지 입니다. 간단한 예시와 함께 이를 찾는 방법을 알아 보겠습니다. 아래 표는 각 매수자가 각 물건을 얼마큼의 가치로 생각하는지를 나타낸 것입니다. 물건은 제가 요새 즐겨하는 게임인 쿠키런 킹덤에서 따왔습니다. 독버섯은 귀엽습니다. 핡.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	12	12	12	8	-
영희	5	6	10	9	-
민수	8	5	11	11	-
지혜	2	3	3	7	-
가격	-	-	-	-

표에서 가장 아래쪽 행은 물건(열)의 가격을, 가장 오른쪽 열은 각 매수자(행)가 얻을 수 있는 최대 효용을 나타냅니다. 먼저 모든 물건의 가격이 0이라고 해보죠. 그러면 각 매수자의 최대 효용은 다음과 같습니다.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	12	12	12	8	12
영희	5	6	10	9	10
민수	8	5	11	11	11
지혜	2	3	3	7	7
가격	0	0	0	0

위에서 빨간색 배경에 밑줄이 쳐진 칸은 해당 행의 매수자가 최대의 효용을 얻기 위해서 바라는 물건입니다. 예를 들어, 철수는 마늘빵, 독버섯, 바다 요정 중 아무거나 하나를 받으면 본인의 최대 효용을 얻을 수 있습니다. 반면, 영희에게는 바다 요정만이 최대 효용을 얻을 수 있는 물건입니다.

 

각 물건이 매수자에게 미치는 영향을 좀더 잘 보기 위해 각 칸의 값을 해당 행의 매수자가 얻을 수 있는 최대 효용으로 빼 보겠습니다. 그러면 아래와 같은 표가 나옵니다. 각 칸은 해당 행의 매수자가 해당 열의 물건을 얻었을 때 이 매수자가 얻을 수 있는 최대 효용으로부터 얼마큼 적은 효용을 얻을지 나타냅니다. 이때 각 행마다 적어도 하나의 물건은 최대 효용을 줄 것이므로 분명 해당 행에는 0이 적힌 칸이 적어도 하나는 있을 것입니다. 또한 각 매수자는 자신의 행에서 0이 적힌 칸의 물건을 받아야 만족할 것입니다.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	0	0	0	-4	12
영희	-5	-4	0	-1	10
민수	-3	-6	0	0	11
지혜	-5	-4	-4	0	7
가격	0	0	0	0

이제 이 상황에서 매수자(행)와 물건(열)을 뽑아서 표의 모든 0을 '덮어' 보려고 합니다. 이때 뽑은 행과 열의 개수가 물건의 개수 (혹은 매수자의 수) $n$보다 작다면 놀랍게도 우리는 현재 경쟁 중인 물건이 무엇인지 알 수 있습니다.

 

위 예시를 다시 한번 살펴 봅시다. 만약 매수자에서는 철수를 선택하고 물건에서는 바다 요정과 목화솜을 선택하면 아래 초록색으로 표시한 것과 같이 표의 모든 0을 덮을 수 있습니다. 이때 뽑은 행과 열의 총 개수는 세 개로 물건의 개수인 네 개보다 적습니다.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	0	0	0	-4	12
영희	-5	-4	0	-1	10
민수	-3	-6	0	0	11
지혜	-5	-4	-4	0	7
가격	0	0	0	0

뽑은 행과 열의 개수가 $n$보다 작은 것이 어쨌길래 현재 경쟁이 붙은 물건을 찾을 수 있다는 것일까요? 흥미롭게도, 뽑힌 열의 물건들이 곧 경쟁에 참여하는 물건이 되기 때문입니다. 좀더 자세히 설명을 드리죠. 뽑힌 매수자의 집합을 $I^{\prime }$, 뽑힌 물건의 집합을 $J^{\prime }$이라고 하겠습니다. 이제 매수자 중에서 뽑히지 않은 사람들만 고려해 보겠습니다. 그러면 그 매수자에 해당하는 행의 0은 뽑힌 물건들로만 덮혔을 것입니다. 다시 말해, $n-|I^{\prime }|$ 명의 매수자들이 $J^{\prime }$의 물건들만 원하는 상황이라는 뜻입니다. 이때, 전체 뽑은 개수 $|I^{\prime }|+|J^{\prime }|$이 $n$보다 작다는 가정에서 우리는 쉽게 $n-|I^{\prime }|>|J^{\prime }|$을 이끌어 낼 수 있습니다. 따라서 뽑힌 물건들이 곧 뽑히지 않은 매수자들이 경쟁하는 물건들이 됩니다. 위 예시에서도 똑같이 뽑히지 않은 매수자들인 영희, 민수, 지혜가 뽑힌 물건인 바다 요정과 목화솜을 두고 경쟁하는 것을 확인할 수 있습니다.

 

그렇다면 경쟁이 존재하지 않는 상태는 어떻게 파악할 수 있을까요? 자연스럽게 생각할 수 있는 조건은 표의 모든 0을 $n$ 개보다 적은 수의 행과 열을 뽑아서는 덮을 수 없을 때입니다. 그리고 흥미롭게도 그 예상이 정확합니다. 경쟁이 존재하지 않는다면 아무래도 각 매수자에게 최대 효용을 주는 물건(즉, 표에서 0의 값을 갖는 칸의 물건)을 하나씩 할당하는 방법이 있을 것으로 기대할 수 있으며, 실제로도 그러합니다. 이에 대해서는 다음 절에서 좀더 자세히 알아 보겠습니다.

 

이번 절을 마치기 전에 마지막으로 한 가지 짚고 넘어 가겠습니다. 위에서 알 수 있는 사실은 $n$개 보다 적은 수의 행과 열을 뽑아서 표의 모든 0을 덮을 수 있는 방법이 존재하면 경쟁이 발생했다는 것입니다. 그렇다면 그러한 방법은 어떻게 구할 수 있을까요? 이번 글에서는 자세히 다루지는 않겠지만, 표의 모든 0을 덮는 방법은 표의 행과 열을 정점으로 생각하고 0의 값을 갖는 칸에 해당하는 쌍이 간선으로 연결된 이분 그래프(bipartite graph)의 정점 덮개(vertex cover)와 동일합니다. 이분 그래프에서는 다음과 같은 사실이 잘 알려져 있으며, 이번 글에서는 아래의 내용을 받아 들이고 넘어가면 되겠습니다.

• 이분 그래프에서 최소 정점 덮개의 크기는 최대 이분 매칭(bipartite matching)의 크기와 동일하다. 즉, 표에서 $n$ 개보다 적은 수의 행과 열을 뽑아서는 모든 0을 덮을 수 없다면 반드시 각 매수자에게 최대 효용을 제공하는 물건을 하나씩 분배할 수 있다.
• 이분 그래프에서 최소 정점 덮개는 다항 시간(polynomial time)에 구할 수 있다.

보다 자세한 사항이 궁금하시면 아래 포스트를 참고하시기 바랍니다.

2019.01.28 - [조합론적 최적화/Matching] - 쾨니그의 정리 (Kőnig's Theorem)

쾨니그의 정리 (Kőnig's Theorem)

적정 가격 형성하기

이전 절에서는 현재 가격에서 경쟁이 존재한다면, 경쟁이 붙은 물건이 무엇이고 어느 매수자가 경쟁에 참여하였는지를 확인하는 방법을 알아 보았습니다. 우리는 모든 매수자가 자신의 물건에 만족하는 평형 상태를 원하며, 경쟁이 붙은 물건의 가격을 조정함으로써 이를 이룰 수 있다고 하였습니다. 이번 절에서는 가격을 얼마큼 조정하면 좋은지에 대해서 논의해 보겠습니다.

 

이전 절에서 사용한 표를 다시 가지고 오겠습니다. 표의 각 칸에는 해당 행의 매수자가 해당 열의 물건을 얻었을 때 그 매수자가 원래 얻을 수 있는 최대 효용으로부터 얼마큼 적은 효용을 얻는지를 나타냅니다.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	0	0	0	-4	12
영희	-5	-4	0	-1	10
민수	-3	-6	0	0	11
지혜	-5	-4	-4	0	7
가격	0	0	0	0

앞에서 우리는 $n$보다 작은 수의 행과 열을 뽑아서 표의 모든 0을 덮을 수 있으면 뽑힌 열의 물건이 경쟁이 붙은 물건이며, 뽑히지 않은 행의 매수자가 그 경쟁에 참여하고 있다는 사실을 확인하였습니다. 위 예시에서는 영희, 민수, 지혜가 바다 요정과 목화솜을 두고 경쟁을 하고 있습니다.

 

경쟁을 해소하기 위해 마늘빵과 독버섯의 가격은 그대로 둔 채로 현재 경쟁의 대상인 바다 요정과 목화솜의 가격을 올려 보도록 합시다. 과연 얼마큼 올리면 될까요? 우리의 목표는 영희, 민수, 지혜 중 누군가가 바다 요정이나 목화솜 말고 마늘빵이나 독버섯도 원하게 만드는 것입니다. 그렇다고 가격을 너무 높게 올리는 것은 또 좋은 선택이 아닙니다. 바다 요정과 목화솜의 가격이 너무 높아져 버리면, 이번에는 모든 매수자들이 마늘빵과 독버섯을 원하게 될 것이기 때문이지요.

 

따라서 우리의 목표는 경쟁에 참여하는 매수자가 경쟁 중이지 않은 물건을 원하게 될 정도로 경쟁 중인 물건의 가격을 올리되, 너무 높이 올려서 아무도 현재 경쟁 중인 물건을 더이상 원하지 않게 되는 상황이 오지는 않게 하는 것입니다. 위 예시에서는 민수가 마늘빵을 원하게 하는 것이 가장 가망이 있어 보입니다. 왜냐하면 영희, 민수, 지혜 중 한 명이 마늘빵이나 독버섯을 받았을 때 최대 효용에서 감소하는 폭이 가장 작은 경우가 그 경우이기 때문이죠. 그 폭은 -3입니다.

 

바다 요정과 목화솜의 가격을 3으로 조정해 봅시다. 그러면 영희, 민수, 지혜가 바다 요정이나 목화솜을 얻을 때의 효용이 감소하게 되며, 덩달아 이들이 얻는 최대 효용도 같이 감소하게 됩니다. 이를 모두 계산하여 보면 아래 표와 같습니다. 각 칸에는 가격이 증가한 이후의 최대 효용에 대해 얼마큼 감소된 효용을 얻는지가 적혀 있습니다.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	0	0	-3	-7	12
영희	-2	-1	0	-1	7
민수	0	-3	0	0	8
지혜	-2	-1	-4	0	4
가격	0	0	3	3

위 표에서 우리는 몇 가지 흥미로운 점을 발견할 수 있습니다. 첫 번째는 철수가 더이상 바다 요정을 원하지 않는다는 것입니다. 철수가 생각하는 가치는 12인데, 이제 3의 가격이 붙었으므로 철수의 바다 요정에 대한 효용은 9가 됩니다. 하지만 마늘빵과 독버섯은 여전히 12의 효용을 가지므로, 위 표에서 확인할 수 있듯이 -3의 격차가 발생합니다.

 

두 번째 그리고 더 중요한 점은 민수가 이제부터는 우리의 의도대로 마늘빵도 원한다는 것입니다. 이는 마늘빵의 효용은 그대로인데 반해, 바다 요정과 목화솜의 가격이 나란히 3으로 결정되면서 그것으로부터 얻는 효용이 8이 되었기 때문입니다. 

 

과연 가격이 위와 같이 형성된 이번에는 모든 행의 매수자가 위 표에서 0의 값을 갖는 열의 물건을 받을 수 있을까요? 네, 존재합니다. 이전 절에서 설명한 대로, 위 표에서는 네 개보다 적은 개수의 행과 열을 뽑아서는 표의 모든 0을 덮을 수가 없기 때문이죠. 실지로 철수에게는 독버섯, 영희에게는 바다 요정, 민수에게는 마늘빵, 지혜에게는 목화솜을 할당하면 됩니다. 이때 철수와 민수에게는 공짜로 물건을 줘야 하고, 반대로 영희와 지혜에게는 각각 3의 가격을 받아야 합니다. 이를 정리하면 아래 표와 같습니다.

매수자 ＼ 물건	마늘빵	독버섯	바다 요정	목화솜	최대 효용
철수	12	12	12	8	12
영희	5	6	10	9	7
민수	8	5	11	11	8
지혜	2	3	3	7	4
가격	0	0	3	3

경제학으로 해석한 헝가리안 알고리즘

이것으로 앞에서 제시한 방법의 컴퓨터과학적이지 못한 부분을 모두 해소하였습니다. 이것이 바로 헝가리안 알고리즘이며, 아래는 위 방법에서 부족한 부분을 자세히 밝혀 적은 것입니다. 아래에서 좀더 간결하게 표현하기 위해, 물건에 대해 어떤 가격 $p\in {\mathbb{R}}^J$이 정해졌을 때, 각 매수자 $i$가 얻는 최대 효용을 $u_i^p$, 즉 $$u_i^p:=\underset{j\in J}{max}(v_{i,j}-p_j)$$라고 하겠습니다.

알고리즘 1. 헝가리안 알고리즘 (경제학적 관점)

---

입력: 매수자 $I$, 물건 $J$, 각 매수자 $i$가 생각하는 각 물건 $j$의 가치 $v_{i,j}\in {\mathbb{R}}_{+}$ (단, $n=|I|=|J|$.)

출력: 할당 $\sigma :I\to J$, 가격 $p\in {\mathbb{R}}^J$

 

1. 모든 물건 $j$에 대해, $p_j\leftarrow 0$
2. 다음을 만족하는 $n\times n$ 크기의 표 $T$을 만든다: 각 $i$ 번째 행, $j$ 번째 열의 칸의 값을 현재 가격을 기준으로 매수자 $i$가 물건 $j$를 얻을 때의 효용에서 최대 효용을 뺀 값, 즉 $(v_{i,j}-p_j)-u_i^p$로 정의한다.
3. 표 $T$에서 행과 열을 최소의 개수로 뽑아 표의 모든 0을 덮는 방법을 찾는다. 그렇게 찾은 행(매수자)의 집합을 $I^{\prime }$, 열(물건)의 집합을 $J^{\prime }$이라고 하자.
4. 만약 $|I^{\prime }|+|J^{\prime }|<n$이라면, 아래를 수행하고 단계 2로 돌아간다.
   1. $\epsilon \leftarrow \underset{i\notin I^{\prime },j\notin J^{\prime }}{min}\{u_i^p-(v_{i,j}-p_j)\}$
   2. 각 $j\in J^{\prime }$, $p_j\leftarrow p_j+\epsilon$
5. 만약 $|I^{\prime }|+|J^{\prime }|=n$이라면, 표 $T$에서 각 매수자에게 0의 값을 갖는 칸의 물건을 할당하는 방법 $\sigma$를 찾고 $\sigma$와 $p$를 반환한다.

앞서 제기하였듯이, 우리에게는 여전히 아래의 두 가지 의문점이 남아 있습니다.

• 알고리즘이 언젠가는 끝나는가?
• 알고리즘이 각 매수자가 얻는 가치의 총합을 최대로 하는 할당을 출력하는가?

이를 하나씩 해결해 봅시다.

알고리즘의 종료(termination)

만약 알고리즘이 끝나지 않는다면, 사실 이는 알고리즘이라고 부를 수 없습니다. 따라서 알고리즘이 언젠간 끝이 나는지를 논의하는 것은 일반적으로 알고리즘의 정당성(correctness)을 분석하는데 지대한 부분을 차지합니다.

 

첫 번째 질문에 대해 답변하려면 아래의 정리들이 필요합니다. 첫 번째 정리는 사실 증명이 필요하지 않을 정도로 간단한 정리입니다.

정리 1. 표 $T$의 양이 아닌 수만 갖는 성질

---

알고리즘 1이 동작하는 내내, 표 $T$의 모든 칸은 0보다 작거나 같다.

[증명] 임의의 $i$ 번째 행 $j$ 번째 열의 칸에는 현재 가격 $p$에서 물건 $j$에 대한 매수자 $i$의 효용에서 매수자 $i$가 얻는 최대 효용을 뺀 값이 들어갑니다. 따라서 반드시 0보다 작거나 같습니다. ■

 

앞에서 경쟁이 발생했을 때, 경쟁에 참여하는 매수자 중 일부가 더이상 관심이 없도록은 만들되, 너무 많은 매수자가 경쟁에서 이탈하는 것은 방지하는 수준으로 경쟁이 붙은 물건의 가격을 올려야 한다고 했습니다. 위 알고리즘에서는 단계 4에서 경쟁이 붙은 물건의 가격을 $\epsilon$만큼 증가시킵니다. 이때 $\epsilon$은 경쟁에 참여하는 (즉, $I^{\prime }$에 속하지 않는) 매수자가 경쟁이 붙지 않은(즉, $J^{\prime }$에 속하지 않는) 물건을 원하게 만드는 가격의 증가량 중의 최솟값으로 정해집니다. 이 값은 반드시 0보다 큽니다. 그렇지 않으면 $I^{\prime }$이나 $J^{\prime }$으로 덮이지 않은 0의 값을 갖는 칸이 있다는 뜻이기 때문입니다. 두 번째 정리는 이렇게 정한 $\epsilon$이 우리가 딱 원하는 수준의 가격의 증가량이라는 것을 알려 줍니다.

정리 2. 가격의 증가량의 적절성

---

알고리즘 1이 동작하는 내내, 표 $T$의 모든 칸의 총합은 항상 증가하기만 한다.

[증명] 단계 4를 거쳤을 때 표 $T$의 모든 칸의 총합이 항상 증가하기만 함을 보이면 증명이 완성됩니다. 단계 4를 거치기 전의 가격을 $p$, 거친 후의 가격을 $p^{\prime }$이라고 하겠습니다. 즉, 임의의 물건 $j\in J$에 대해 $$p_j^{\prime }=\{\begin{array}{ll}{p}_j+\epsilon & \text{if }j\in J^{\prime }\\ p_j& \text{otherwise}\end{array}$$를 만족합니다. 이제 경우를 매수자 $i$가 $I^{\prime }$에 속하는지 속하지 않는지, 물건 $j$가 $J^{\prime }$에 속하는지 속하지 않는지로 나누어 해당 칸의 $T$가 얼마큼 변화하는지를 따져 보겠습니다.

 

경우 1. $i\in I^{\prime }$. 먼저 경쟁에 참여하지 않는 (즉, $I^{\prime }$에 속하는) 매수자 $i$에 대해서 고려하겠습니다. 이 경우에는 일반성을 잃지 않고 단계 4를 거치기 전에 $J^{\prime }$에 덮이지 않으면서 0의 값을 갖는 칸이 존재한다고 가정해도 됩니다. 그렇지 않다면 해당 $i$를 $I^{\prime }$에서 뺐을 때도 $T$의 모든 0을 (더 적은 수로) 덮을 수 있기 때문입니다. 그러한 칸의 물건을 $j^{\ast }\in J\setminus J^{\prime }$이라고 하겠습니다. 이때 $j^{\ast }$는 최대 효용을 주는 물건입니다. 즉, $u_i^p=v_{i,j^{\ast }}-p_{j^{\ast }}$를 만족한다는 뜻입니다. $j^{\ast }$는 $J^{\prime }$에 속하지 않으므로 가격의 변동이 없습니다. 따라서 단계 4를 거친 후에도 여전히 $j^{\ast }$는 최대 효용을 주는 물건이 됩니다. 다시 말해, $u_i^{p^{\prime }}=u_i^p$입니다.

 

이제 해당 매수자의 각 칸의 값이 어떻게 변화하는지 살펴 봅시다. 경쟁이 붙지 않은 임의의 물건 $j\in J\setminus J^{\prime }$에 대해서는, 가격의 변동이 없으므로 $p_j^{\prime }=p_j$가 성립하고, 따라서 $$(v_{i,j}-p_j^{\prime })-u_i^{p^{\prime }}=(v_{i,j}-p_j)-u_i^p$$가 되어 $T$에서 해당 칸의 변동이 없다는 것을 이끌어 낼 수 있습니다. 반대로 경쟁이 붙은 물건 $j\in J^{\prime }$에 대해서는, $p_j^{\prime }=p_j+\epsilon$이므로, $$(v_{i,j}-p_j^{\prime })-u_i^{p^{\prime }}=(v_{i,j}-p_j)-u_i^p-\epsilon$$이 되어 정확히 $\epsilon$만큼 감소함을 알 수 있습니다.

 

경우 2. $i\in I\setminus I^{\prime }$. 이제 경쟁에 참여하는 매수자 $i$에 대해서 고려해 봅시다. 가격을 올리기 전에 매수자 $i$에게 최대 효용을 주는 물건을 $j^{\ast }$라고 하겠습니다. $j^{\ast }$는 분명히 $J^{\prime }$에 포함되어 있어야 합니다. 그렇지 않다면 $T$의 $i$ 번째 행 $j^{\ast }$ 번째 열의 칸은 0이지만 $I^{\prime }$이나 $J^{\prime }$에 덮이지 않기 때문입니다. 따라서 $j^{\ast }$의 가격은 $\epsilon$만큼 올라갑니다.

 

그럼에도 $j^{\ast }$는 가격이 올라간 후에도 여전히 최대 효용을 제공합니다. 직관적으로 설명하자면 $\epsilon$을 가능한 값들 중에서 가장 작은 값으로 골랐기 때문입니다. 엄밀히 보이자면 다음과 같습니다. 똑같이 $J^{\prime }$에 속한 물건들은 가격이 오를 것이므로 똑같이 효용이 감소합니다. 따라서 $J^{\prime }$에 속하지 않는, 즉 효용이 감소하지 않는 임의의 물건 $j$와 비교해서 $j^{\ast }$의 효용이 감소함에도 여전히 최대 효용을 주는지 판단하면 됩니다. 실지로 $p^{\prime }$에서 $j^{\ast }$에 대한 효용에 $j$에 대한 효용을 빼 보면, $$\begin{array}{ll}(v_{i,j^{\ast }}-p_{j^{\ast }}^{\prime })-(v_{i,j}-p_j^{\prime })& =(v_{i,j^{\ast }}-(p_{j^{\ast }}+\epsilon ))-(v_{i,j}-p_j)\\ & =u_i^p-(v_{i,j}-p_j)-\underset{i^{\prime }\notin I^{\prime },j^{\prime }\notin J^{\prime }}{min}(u_{i^{\prime }}^p-(v_{i^{\prime },j^{\prime }}-p_{j^{\prime }}))\\ & \ge 0\end{array}$$을 만족합니다. 여기서 두 번째 등식은 $j^{\ast }$가 기존 가격 $p$에서 최대의 효용을 주는 물건이기 때문에, 부등식은 $i\notin I^{\prime }$, $j\notin J^{\prime }$이기 때문에 성립합니다. 이를 통해 알 수 있는 사실은 바뀐 가격 $p^{\prime }$에서 매수자 $i$의 최대 효용은 정확히 $\epsilon$ 만큼 감소한다는 것입니다. 즉, $u_i^{p^{\prime }}=u_i^p-\epsilon$을 만족합니다.

 

이제 $T$의 $i$ 번째 행의 칸들이 어떻게 변화하는지 살펴 봅시다. 먼저 경쟁이 붙은 물건 $j\in J^{\prime }$를 고려해 봅시다. 이 물건의 가격은 정확히 $\epsilon$만큼 상승하므로 $$(v_{i,j}-p_j^{\prime })-u_i^{p^{\prime }}=(v_{i,j}-(p_j+\epsilon ))-(u_i^p-\epsilon )=(v_{i,j}-p_j)-u_i^p$$가 되어 값의 변화가 없습니다. 반대로 경쟁의 대상이 아닌 물건 $j\in J\setminus J^{\prime }$에 대해서는 가격의 변동이 없으므로, $$(v_{i,j}-p_j^{\prime })-u_i^{p^{\prime }}=(v_{i,j}-p_j)-(u_i^p-\epsilon )=(v_{i,j}-p_j)-u_i^p+\epsilon$$을 만족하여 정확히 $\epsilon$만큼 증가하게 됩니다.

 

이것으로 모든 경우에 대한 분석을 마칩니다. 위에서 얻은 정보를 정리해 보겠습니다. 단계 4를 거친 후의 $T$의 $i$ 번째 행 $j$ 번째 열의 칸은 다음과 같이 변하게 됩니다.

• $i\in I^{\prime },j\in J^{\prime }$이면, 정확히 $\epsilon$만큼 감소
• $i\in I^{\prime },j\notin J^{\prime }$이면, 변화 없음
• $i\notin I^{\prime },j\in J^{\prime }$이면, 변화 없음
• $i\notin I^{\prime },j\notin J^{\prime }$이면, 정확히 $\epsilon$만큼 증가

따라서 $T$의 모든 칸의 합은 정확히 $\epsilon (n-|I^{\prime }|)(n-|J^{\prime }|)-\epsilon |I^{\prime }||J^{\prime }|$만큼 증가하게 됩니다. 이를 정리하면, $$\epsilon (n-|I^{\prime }|)(n-|J^{\prime }|)-\epsilon |I^{\prime }||J^{\prime }|=\epsilon n(n-|I^{\prime }|-|J^{\prime }|)>0$$을 얻게 됩니다. 이때 부등식은 $\epsilon >0$이라는 사실과 단계 4에 들어가기 위해서는 $|I^{\prime }|+|J^{\prime }|<n$이어야 한다는 사실에서 유도할 수 있습니다. ■

 

정리 1을 통해서 $T$의 값은 항상 양이 아닌 수로만 이루어져 있지만, 정리 2를 통해 $T$의 총합은 계속 증가하기만 합니다. 따라서 아무리 못해도 $T$의 모든 칸이 0이 되는 순간이 언젠가는 도달할 것이며, 이때는 자명하게 $T$의 모든 0을 덮기 위해서 $n$ 개의 행과 열을 선택해야 합니다. 그러므로 이 알고리즘은 분명 언젠가 끝납니다.

알고리즘의 최적성(optimality)

첫 번째 질문이 알고리즘의 종결성에 대한 질문이었다면, 두 번째 질문은 알고리즘이 정말로 최적해를 반환하는지에 대한 것입니다. 구체적으로는 각 매수자가 얻는 가치의 합 $\sum _{i\in I}{v}_{i,\sigma (i)}$를 최대화하는 할당을 얻을 수 있는지 묻고 있습니다. 여기서 문제는 위 알고리즘은 어떤 가격 $p$에 따른 각 매수자가 얻는 최대 효용의 합 $\sum _{i\in I}\underset{j\in J}{max}(v_{i,j}-p_j)$을 주는 할당을 반환한다는 것입니다. 그럼에도 여전히 최적의 답을 제공할까요?

 

놀랍게도 그렇습니다. 아래의 정리는 그 관계를 규명하는데 큰 역할을 담당합니다.

정리 3. 최대 효용과 가격의 역할

---

임의의 가격 $p\in {\mathbb{R}}^J$에 대해서, 임의의 할당 $\sigma :I\to J$을 가져왔을 때, 할당 $\sigma$가 이룩하는 가치는 모든 물건의 가격의 합에 현재 가격에서의 모든 매수자의 최대 효용의 합을 더한 것을 넘지 못한다. 다시 말해, $$\sum _{i\in I}{v}_{i,\sigma (i)}\le \sum _{j\in J}{p}_j+\sum _{i\in I}{u}_i^p$$가 항성 성립한다.

[증명] 다음 식을 통해 간단히 증명할 수 있습니다.

$$\begin{array}{ll}\sum _{i\in I}{u}_i^p+\sum _{j\in J}{p}_j& =\sum _{i\in I}\underset{j^{\prime }\in J}{max}(v_{i,j^{\prime }}-p_{j^{\prime }})+\sum _{j\in J}{p}_j\\ & \ge \sum _{i\in I}(v_{i,\sigma (i)}-p_{\sigma (i)})+\sum _{j\in J}{p}_j\\ & =\sum _{i\in I}{v}_{i,\sigma (i)}\end{array}$$

여기서 마지막 등식은 할당 $\sigma$가 $I$와 $J$ 사이의 일대일 대응이므로 성립합니다. ■

 

알고리즘 1은 적절히 형성된 가격 $p$에 대해 모든 매수자가 자신에게 최대의 효용을 주는 물건을 하나씩 받는 할당을 반환합니다. 정리 3을 활용하여 이 할당이 최적해라는 것을 증명할 수 있습니다.

정리 4. 알고리즘 1의 최적성

---

알고리즘 1은 각 매수자가 얻는 가치의 합이 최대가 되는 할당을 반환한다.

[증명] 알고리즘이 반환하는 할당을 ${\sigma }^{\ast }$, 그때의 가격을 $p^{\ast }$라고 하겠습니다. 이 할당이 이루는 가치는 $$\sum _{i\in I}{v}_{i,{\sigma }^{\ast }(i)}=\sum _{i\in I}((v_{i,{\sigma }^{\ast }(i)}-p_{{\sigma }^{\ast }(i)}^{\ast })+p_{{\sigma }^{\ast }(i)}^{\ast })=\sum _{i\in I}{u}_i^{p^{\ast }}+\sum _{j\in J}{p}_j^{\ast }$$가 성립합니다. 이때 마지막 등식은 알고리즘이 가격 $p^{\ast }$에 대해 각 매수자에게 최대의 효용을 주는 물건을 할당한다는 사실과 ${\sigma }^{\ast }$가 일대일 대응이라는 사실에서 이끌어 낼 수 있습니다. 정리 3을 통해 가격 $p$가 어떻게 주어지든지 간에 우리는 어떤 할당도 $\sum _{i\in I}{u}_i^p+\sum _{j\in J}{p}_j$ 보다 큰 가치를 이룰 수 없다는 것을 압니다. 따라서 ${\sigma }^{\ast }$가 이루는 가치가 최대가 될 수 밖에 없습니다. ■

마치며

이것으로 경제학으로 해석한 헝가리안 알고리즘에 대한 설명을 모두 마칩니다. 요새 경제학, 특히 후생 경제학(welfare economics)에서 활용되는 알고리즘에 대해 공부를 하고 있습니다. 그와중에 제가 애정하는 헝가리안 알고리즘이 경제학적으로 해석될 수 있다는 사실을 알게 되어 이 글을 적었습니다. 동일한 알고리즘에 대해 새로운 시각을 제공하는 것은 아주 멋진 일입니다. 아무래도 이 글이 헝가리안 알고리즘의 해석 중 개인적으로 가장 좋아하는 해석이 되지 싶습니다.

 

선형 계획법(linear programming)에 익숙하신 분들은 쉽게 보셨을 수 있지만, 정리 3은 곧 선형 계획법의 쌍대성(duality)에 해당합니다. 언젠가 헝가리안 알고리즘을 쌍대성으로 해석하는 글을 적어 보려고 했는데, 이 글로 갈음하고자 합니다. 쌍대성에 관해 더 알아 보고 싶으신 분들은 아래를 참고하시기 바랍니다.

2019.07.15 - [수학적 도구/Linear programming] - [선형 계획법] 쌍대성(Duality)

[선형 계획법] 쌍대성(Duality)

 

현재 개인적으로 갖는 의문은 과연 위와 같이 동작하는 헝가리안 알고리즘이 유인 부합적(incentive compatible)이기도 한지입니다. 유인 부합적이라는 말의 뜻은 각 매수자들이 자신이 생각하는 실제 가치 $v_{i,j}$를 우리에게 알려줄 때 사기를 칠 유인이 없다는 뜻입니다. 사실 헝가리안 알고리즘을 $O(n)$ 번 수행하면 유인 부합적인 메커니즘을 만들 수 있습니다만, 한 번의 수행으로도 동일한 효과를 낼 수 있는지 궁금합니다. 간단히 인터넷을 뒤져 봤는데 이에 대한 답을 쉽게 찾지는 못했습니다. 혹여 관련하여 아시는 분이 있으시면 댓글로 알려 주시기 바랍니다.

 

글을 마무리 짓는 지금은 성탄절입니다. 2020년과 2021년 모두 코로나 때문에 힘든 나날을 보냈는데 다가오는 해에는 개인적으로도, 모두에게도 좋은 날이 되기를 바라 봅니다. 읽어 주셔서 고맙습니다.

참조

[1] Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education, 2013.

각주

[ㄱ] 제 경험에 비추어 본 바, 할당 문제는 대개 비용을 최소화 하는 문제로 정의되는 경우가 많습니다. 다만 본문에서는 가치를 최대화 하는 문제로 정의하였습니다. 이것이 후생 경제학의 관점에 더 부합하기 때문입니다. 게다가 할당 문제는 최소화 문제나 최대화 문제나 본질적으로 동등(equivalent)하기도 합니다.