무정부의 대가

1. 개요

무정부의 대가 Price of Anarchy (PoA)
정의	최악 균형의 사회적 비용 ÷ 중앙집중 최적 비용
기원	쿠추피아스·파파디미트리우 (1999) — 명칭은 파파디미트리우 (2001)
대표 결과	아핀 지연 비원자적 라우팅 $4/3$ (러프가든·타르도스 2002)
원자적 아핀 혼잡	$5/2$ — 가중판은 $(3+\sqrt5)/2 \approx 2.618$
부하분산	동일 기계 순수 $2-\frac{2}{m+1}$ · 혼합 $\Theta(\log m/\log\log m)$
증명 도구	매끄러움 $(\lambda,\mu)$ → 상한 $\lambda/(1-\mu)$
사촌	안정성의 대가(PoS) — 최선 균형으로 잰다

무정부의 대가(Price of Anarchy, PoA)는 어떤 게임의 «가장 나쁜 균형»에서 발생하는 사회적 비용을, 중앙에서 전부 명령했을 때의 최적 비용으로 나눈 비율이다.

$$\mathrm{PoA} \;=\; \frac{\max_{s \in \mathrm{EQ}} \mathrm{cost}(s)}{\min_{s} \mathrm{cost}(s)}$$

쿠추피아스와 파파디미트리우가 1999년 논문 「Worst-case equilibria」에서 도입했고, “무정부의 대가”라는 이름은 파파디미트리우가 2001년에 붙였다.¹ 값이 1 에 가까우면 “각자 이기적으로 굴게 놔둬도 별로 손해 안 본다”는 뜻이고, 그건 분산 시스템을 설계할 때 조율 장치를 만들지 않아도 된다는 허가증이다. 그래서 이 지표는 경제학보다 전산학·네트워크 설계 쪽에서 훨씬 사랑받는다.

내시 균형 문서가 이 정의와 $4/3$ 이라는 숫자를 한 문단으로 소개하고 넘어가니, 여기서는 그 숫자가 어디서 나오고 어디까지 일반화되는지를 본다. 결론을 미리 말하면, 2009년 이후 이 분야의 상한 증명은 거의 전부 매끄러움이라는 세 줄짜리 논변 하나로 통일됐고, 그 부산물로 상한이 내시 균형을 넘어 학습 동역학 전체로 확장됐다.

2. 정의를 쓸 때 주의할 것

정의가 짧아서 오히려 함정이 많다.

• 분자가 최악이다. 균형이 여럿일 때 가장 나쁜 것을 고른다. “최선”을 고르면 그건 아래의 안정성의 대가다.
• 어떤 균형인가. 순수 내시, 혼합 내시, 상관 균형, 조대 상관 균형(CCE) 중 어느 집합을 쓰느냐에 따라 값이 달라진다. 집합이 커질수록 최악이 나빠지므로 $\mathrm{PoA}(\text{순수}) \le \mathrm{PoA}(\text{혼합}) \le \mathrm{PoA}(\text{CE}) \le \mathrm{PoA}(\text{CCE})$ 다. 놀랍게도 많은 경우 네 값이 전부 같다.
• 사회적 비용의 정의가 자유롭다. 총합($\sum_i C_i$)인지 최댓값($\max_i C_i$, 메이크스팬)인지에 따라 완전히 다른 이론이 나온다. 라우팅 문헌은 대개 총합, 부하분산 문헌은 대개 최댓값을 쓴다. 논문 두 편의 PoA 를 비교하기 전에 이 항목부터 맞춰야 한다.
• 인스턴스 하나가 아니라 부류에 대한 상한이다. “이 도로망의 PoA”보다 “아핀 지연 함수를 갖는 모든 도로망의 PoA 상한”이 훨씬 쓸모 있는 명제다.

3. 피구의 예 — 4/3 이 나오는 최소 사례

$s$ 에서 $t$ 로 유량 1 이 흐르고, 평행한 링크가 두 개다. 위쪽은 통행시간이 상수 $c_1(x)=1$(넓지만 느린 고속도로), 아래쪽은 $c_2(x)=x$(막히면 느려지는 지름길).

균형. 아래쪽은 유량이 1 이어도 통행시간이 1 이라 위쪽보다 결코 나쁘지 않다. 전원이 아래로 간다. 총비용 $1\times 1 = 1$.

최적. 절반씩 나누면 총비용은 $\tfrac12\cdot\tfrac12 + \tfrac12\cdot 1 = \tfrac34$.

$$\mathrm{PoA} = \frac{1}{3/4} = \frac{4}{3}$$

아서 피구가 1920년 The Economics of Welfare 에서 든 예이고², 놀랍게도 이 두 링크짜리 장난감이 아핀 지연 함수 부류 전체에서 최악이다. 러프가든(2003)이 보인 대로, 비원자적 이기적 라우팅의 PoA 는 네트워크 위상과 무관하고 오직 지연 함수의 부류만으로 결정되며, 그 값은 “그 부류에서 만들 수 있는 최악의 피구 예”로 계산된다. 도로망을 아무리 복잡하게 꼬아도 두 링크보다 나빠지지 않는다는 이 결과는, 처음 보면 믿기 어렵지만 매끄러움 논변으로 보면 거의 자명해진다.

4. 이기적 라우팅

러프가든과 타르도스(2002)의 결과가 이 분야의 대표작이다. 비원자적 혼잡 게임(=교통 배정)에서 각 링크의 지연이 아핀 함수 $c_e(x) = a_e x + b_e$($a_e, b_e \ge 0$)일 때

$$\mathrm{PoA} \;\le\; \frac{4}{3}, \qquad \text{그리고 이 상한은 타이트하다.}$$

즉 이기심의 대가가 33 % 를 넘지 않는다. 도로 확장이나 통행료 같은 개입을 고민하기 전에 “이론적으로 최대 33 % 절감”이라는 숫자를 먼저 알고 시작할 수 있다는 뜻이라, 정책 논의에서 대단히 쓸모 있다.

지연 함수를 일반화하면 값이 나빠진다.

지연 함수 부류	비원자적 PoA
상수	1
아핀 $ax+b$	$4/3$
2차 다항식	$\approx 1.626$
$d$ 차 다항식 (계수 비음수)	$\Theta(d/\log d)$
임의의 연속 비감소 함수	무한대

마지막 줄이 무섭지만, 그 자리에 러프가든·타르도스의 이중기준 결과가 들어온다.

유량 $r$ 에서의 균형 비용은, 유량 $2r$ 에서의 최적 비용보다 크지 않다.

지연 함수에 아무 가정도 없이 성립한다. 읽는 방법은 이렇다 — “이기적으로 굴게 놔두는 것”의 손해는 “용량을 두 배로 늘리는 것”의 이득보다 작다. 정교한 라우팅 제어를 설계하느니 회선을 두 배로 까는 게 확실하다는, 엔지니어의 직관을 정리로 만든 물건이다.

원자적(플레이어가 유한하고 각자 덩어리 유량을 가진) 판은 값이 더 나쁘다. 아핀 비용에서 순수·혼합·상관·CCE 모두 $5/2$ 이고, 플레이어마다 가중치가 다른 가중판에서는 $(3+\sqrt5)/2 \approx 2.618$ 이다. 비원자적 $4/3$ 과의 차이가 곧 “내가 혼잡에 실제로 기여하는 몫을 무시하는 대가”다.

5. 부하분산 — PoA 라는 개념이 태어난 곳

쿠추피아스·파파디미트리우의 원논문은 라우팅이 아니라 부하 분산 모형이었다. 기계 $m$ 대, 작업 $n$ 개, 각 작업이 자기 완료시간을 최소화하도록 기계를 고르고, 사회적 비용은 메이크스팬($\max_j$ 기계 $j$ 의 부하)이다.

• 동일 기계 · 순수 균형: $\mathrm{PoA} = 2 - \dfrac{2}{m+1}$. $m=2$ 면 $4/3$, $m\to\infty$ 면 2 로 간다. 상한 2 의 논증은 그리디 스케줄링 근사비의 고전 논증과 사실상 같다.
• 동일 기계 · 혼합 균형: $\Theta\!\left(\dfrac{\log m}{\log\log m}\right)$. $m=2$ 의 정확한 값 $3/2$ 가 원논문의 결과이고, 일반 $m$ 의 타이트한 차수는 추마이·푀킹(2002)이 확정했다.

순수에서 상수, 혼합에서 로그로 벌어진다는 이 격차가 시사하는 바가 크다. 무작위화가 균형의 집합을 넓히고, 넓어진 집합의 가장 나쁜 구석은 훨씬 나쁘다. 확률적으로 운 나쁘게 모두가 같은 기계를 고르는 사건이 최악을 만든다. 라우팅에서 순수/혼합/CCE 의 PoA 가 전부 같았던 것과 대조되는데, 차이는 목적함수가 최댓값이라는 데 있다. 합은 매끄러움 논변이 잘 통하고, 최댓값은 잘 안 통한다.

6. 안정성의 대가

균형이 여럿일 때 최선 균형으로 재는 것이 안정성의 대가(Price of Stability, PoS)다.

$$\mathrm{PoS} \;=\; \frac{\min_{s\in\mathrm{EQ}} \mathrm{cost}(s)}{\min_s \mathrm{cost}(s)} \;\le\; \mathrm{PoA}$$

둘을 갈라 쓰는 이유는 책임 소재가 다르기 때문이다. PoA 는 “최악의 경우에도 이만큼은 보장된다”는 보증서이고, PoS 는 “설계자가 좋은 균형을 제안하고 아무도 이탈하지 않게 만들 수 있는가”라는 목표치다. 시스템에 초기 설정이나 기본값을 심을 수 있다면 실제로 관측되는 것은 PoS 쪽에 가깝다.

간극이 극적인 대표 사례가 공정 비용분담 네트워크 설계다. 플레이어 $n$ 명이 각자 $s_i \to t_i$ 경로를 고르고, 간선 비용 $c_e$ 를 그 간선을 쓰는 사람 수로 똑같이 나눠 낸다. 이 게임은 혼잡 게임의 일종이라 순수 균형이 늘 존재하는데,

$$\mathrm{PoA} = n, \qquad \mathrm{PoS} = H_n = 1 + \tfrac12 + \cdots + \tfrac1n = \Theta(\log n)$$

이다(안셸레비치 등 2004). 최악 균형은 $n$ 배 나쁜데 최선 균형은 로그 배밖에 안 나쁘다. 증명은 로젠탈 퍼텐셜을 써서 ”$\Phi$ 의 최소점인 균형”의 비용을 재는, 이른바 퍼텐셜 논변의 교과서적 예다. 설계자가 개입할 수 있다면 $\log n$ 짜리 세상에 살 수 있다는 결론이라, “시스템 기본값을 잘 심는 것”의 가치를 정량화해 준다.

7. 매끄러움 논변

2009년 러프가든이 정리한 이 틀 하나가 이 분야의 증명 방식을 통일했다. 비용 최소화 게임이 $(\lambda,\mu)$-매끄럽다는 것은, 모든 전략 조합 $s$ 와 모든 $s^{*}$ 에 대해

$$\sum_{i} C_i\big(s_i^{*}, s_{-i}\big) \;\le\; \lambda\,\mathrm{cost}(s^{*}) \;+\; \mu\,\mathrm{cost}(s)$$

가 성립한다는 뜻이다. 이 부등식에는 균형이라는 단어가 안 나온다. 순전히 게임의 보수 구조에 대한 성질이다.

그런데 $s$ 가 순수 내시 균형이면 각 $i$ 가 $s_i^{*}$ 로 이탈해도 나빠지지 않으므로 $C_i(s) \le C_i(s_i^{*}, s_{-i})$ 이고, 세 줄이면 끝난다.

$$\mathrm{cost}(s) = \sum_i C_i(s) \;\le\; \sum_i C_i(s_i^{*}, s_{-i}) \;\le\; \lambda\,\mathrm{cost}(s^{*}) + \mu\,\mathrm{cost}(s)$$

$\mu < 1$ 이면 이항해서

$$\mathrm{cost}(s) \;\le\; \frac{\lambda}{1-\mu}\,\mathrm{cost}(s^{*}) \qquad\Longrightarrow\qquad \mathrm{PoA} \le \frac{\lambda}{1-\mu}$$

이 증명이 균형에 대해 쓴 성질은 «어떤 고정된 이탈 $s_i^{*}$ 보다 나쁘지 않다» 하나뿐이다. 그리고 그 조건은 혼합 내시 균형, 상관 균형, 조대 상관 균형, 심지어 무후회 학습의 시간평균 궤적에서도 (기댓값으로) 성립한다. 그래서 매끄러움으로 얻은 상한은 자동으로 그 계층 전체에 적용된다. 러프가든은 이를 강건 PoA(robust price of anarchy)라 불렀다.³

이 사실이 시뮬레이션 하는 사람에게 왜 결정적이냐면 — 균형을 계산할 필요가 없어진다. 에이전트마다 승수가중치/헤지 알고리즘 같은 무후회 학습기를 붙여 돌리고 시간평균 사회비용을 재면, 그 값이 이미 $\lambda/(1-\mu)$ 안에 들어 있음이 보장된다. PPAD-완전인 내시 계산을 우회하면서 성능 보증만 챙기는 셈이다. 자세한 계층 대응은 상관 균형 문서 참고.

숫자로 확인해 보면 아핀 원자적 혼잡 게임은 $(\lambda,\mu)=(5/3,\,1/3)$-매끄럽고, $\dfrac{5/3}{1-1/3} = \dfrac{5}{2}$ 로 앞의 값과 정확히 맞는다. 그리고 이 상한이 순수 내시 균형에서 이미 타이트하다는 것이 요점이다 — 계층이 통째로 무너져 네 값이 전부 $5/2$ 로 같아진다. 위 부하분산의 순수/혼합 격차가 나온 이유도 여기서 설명된다. 메이크스팬 목적함수는 $\sum_i C_i$ 형태로 안 쪼개져서 매끄러움 틀 자체가 안 맞는다.

8. 브라에스 역설이 왜 대표 사례인가

혼잡 게임 문서에서 본 브라에스 역설 — 지연 0 인 지름길을 추가했더니 균형 통행시간이 $3/2$ 에서 $2$ 로 늘어나는 예 — 의 비율이 정확히 $4/3$ 이다. 우연이 아니다. 지름길을 추가한 뒤의 네트워크에서 원래의 절반씩 갈라 쓰는 배분이 여전히 실행가능하고 그것이 최적이므로, 이 인스턴스는 아핀 부류의 PoA 상한을 정확히 치는 증인이다. 피구의 예와 같은 값을 다른 방식으로 실현한 셈이다.

브라에스가 교과서에서 피구보다 자주 인용되는 이유는 값 때문이 아니라 이야기 때문이다.

• 개입이 역효과를 낼 수 있음을 보여 준다. 피구의 예는 “이기심이 손해다”까지만 말하지만, 브라에스는 “선의의 개선이 손해다”까지 간다.
• PoA 가 «구조 대비 얼마나 나쁜가»를 재는 지표임을 드러낸다. 링크를 지우면 균형이 좋아진다는 것은 균형 개념 자체가 네트워크 구조에 비단조적으로 반응한다는 뜻이고, 위상 무관성 정리가 놀라운 이유도 이 배경 때문이다.
• 반대 방향의 설계 지침을 준다 — 지름길이 문제라면 지름길에 통행료를 매기면 된다. 링크마다 한계비용 통행료 $f_e\,c_e'(f_e)$ 를 부과하면 사용자 균형이 시스템 최적과 일치한다(피구식 조세). 이론적으로 PoA 를 1 로 만드는 방법이 있다는 것이며, 이 계보가 메커니즘 설계로 이어진다.

9. 설계·시뮬레이션에서 쓰는 법

• PoA 를 실제로 측정해 봐라. 이기적 에이전트 시뮬레이션의 사회비용을 분자로, 시스템 최적을 분모로 쓴다. 분모는 새 최적화기를 짤 필요 없이 지연 함수를 한계비용 $c_e(x)+x c_e'(x)$ 로 바꾼 뒤 같은 균형 계산기를 돌리면 나온다. 두 번 돌려서 나눈 값이 그 인스턴스의 PoA 다.
• 이론값은 상한이지 예측값이 아니다. 실제 인스턴스의 PoA 는 대개 상한보다 훨씬 작다. “우리 시스템 PoA 는 $5/2$ 다”가 아니라 ”$5/2$ 를 넘지 않는다”가 맞는 문장이다.
• 지표를 고르는 것이 절반이다. 합인가 최댓값인가, 최악 균형인가 최선 균형인가를 먼저 정해야 한다. 설계로 기본값을 심을 수 있으면 PoS, 못 하면 PoA.
• 상한이 나쁘면 세 가지 선택지가 있다. 자원을 늘린다(이중기준 결과), 가격을 매긴다(한계비용 통행료), 또는 일부만 중앙에서 통제한다(슈타켈베르크 라우팅 — 전체의 $\alpha$ 만 통제해도 PoA 가 크게 개선된다는 결과들이 있다).
• 밸런싱에도 그대로 온다. 게임 서버 큐, 파티 매칭, 자원 노드 경합처럼 플레이어가 스스로 고르는 시스템은 전부 혼잡 게임이고, “메타가 굳었을 때 전체 대기시간이 최적 대비 몇 배인가”가 그대로 PoA 다. 지표를 이렇게 정의해 두면 패치의 효과를 한 숫자로 보고할 수 있다.

10. 관련 문서

• 혼잡 게임 · 내시 균형 · 상관 균형 · 게임 이론
• 브라에스 역설 · 워드롭 균형 · 교통 배정 · 메커니즘 설계
• 무후회 학습 · 헤지 알고리즘 · 미러 하강
• 부하 분산 · 네트워크 흐름 · 최소 비용 흐름
• 근사 알고리즘 · NP-완전 · 볼록 최적화 · 최적설계
• 군중 시뮬레이션 · 경로 계획

11. Footnotes

1. Koutsoupias, E. & Papadimitriou, C. (1999). “Worst-case equilibria”. STACS. 명칭은 파파디미트리우의 2001년 STOC 초청논문 “Algorithms, games, and the Internet”에서 굳었다. 그리스어 이름이라 한국어 표기가 쿠추피아스·코우초우피아스 등으로 흔들린다. 어느 쪽이든 이름값의 절반은 “Price of Anarchy”라는 작명이 했다 — 예산 심의에서 한 줄로 설명이 끝나는 용어를 만드는 것도 실력이다. ↩

2. 피구는 좁고 빠른 길과 넓고 느린 길을 두고 “각자 알아서 고르게 두면 사회 전체로는 손해”라는 논지를 폈고, 처방으로 세금을 제안했다 — 그게 오늘날의 피구세다. 즉 경제학은 문제와 처방을 1920년에 이미 갖고 있었고, 80년 뒤 전산학이 한 일은 그 손해가 정확히 몇 배인지 재는 것이었다. 분야가 다르면 같은 그림에서 궁금해하는 것도 다르다. ↩

3. Roughgarden, T. (2015). “Intrinsic robustness of the price of anarchy”. JACM 62(5). 초기 버전은 2009년 STOC. 제목의 “intrinsic”이 정확한 단어다 — 상한이 균형 개념에 붙어 있는 게 아니라 게임의 보수 구조에 붙어 있다는 뜻이라, 어떤 균형 개념을 들고 오든 따라온다. 논문 하나가 기존 증명 수십 편을 사후적으로 “사실 다 같은 증명이었다”로 정리해 버린 드문 사례. ↩