시장 균형 계산

**시장 균형 계산**(, 또는 **경쟁 균형 계산**(competitive equilibrium computation) 또는 **청산 가격 계산**(clearing-prices computation))은 경제학과 컴퓨터 과학의 교차점에 있는 계산 문제이다. 이 문제의 입력은 자원 집합과 에이전트 집합으로 구성된 시장이다. 피셔 시장과 애로-드브뢰 시장과 같이 다양한 종류의 시장이 있으며, 자원은 가분적이거나 비가분적일 수 있다. 필요한 출력은 경쟁 균형이며, 이는 가격 벡터(각 자원에 대한 가격)와 할당(각 에이전트에 대한 자원 묶음)으로 구성되어 각 에이전트가 예산에 따라 가능한 최상의 묶음을 얻고 시장이 청산되는(모든 자원이 할당되는) 상태를 의미한다.

경쟁 균형이 항상 파레토 효율적이라는 사실 때문에 시장 균형 계산은 흥미롭다. 모든 구매자가 동일한 소득을 가지는 피셔 시장의 특수한 경우는 특히 흥미로운데, 이 설정에서는 경쟁 균형이 무질투적이기도 하기 때문이다. 따라서 시장 균형 계산은 공정하고 효율적인 할당을 찾는 방법이다.

## 정의
시장 균형 계산의 **입력**은 다음 요소로 구성된다.

# 사전 지정된 공급량을 가진 m개의 자원 집합. 자원은 가분적일 수 있고(이 경우 공급량은 일반성을 잃지 않고 1로 정규화됨), 비가분적일 수 있다.
#* 묶음은 벡터 \mathbf{x} = x_1,\dots,x_m으로 표현되며, 여기서 x_j는 자원 j의 수량이다. 자원이 비가분적인 경우 모든 xj는 정수이며; 자원이 가분적인 경우 xj는 임의의 실수(보통 [0,1]로 정규화됨)일 수 있다.
# n명의 에이전트 집합. 각 에이전트에 대해 묶음에 대한 선호 관계가 있으며, 이는 효용 함수로 표현될 수 있다. 에이전트 i의 효용 함수는 u_i로 표시된다.
# 각 에이전트에 대한 초기 보유량.
#* 피셔 시장에서는 보유량이 "법정 화폐"의 예산 B_i이다. 이 화폐는 시장 밖에서는 가치가 없으므로 효용 함수에 포함되지 않는다. 에이전트는 돈만 가지고 오므로 종종 구매자라고 불린다.
#* 애로-드브뢰 시장에서는 보유량이 임의의 묶음  \mathbf{e}^i이다. 이 모형에서는 에이전트가 구매자와 판매자 모두가 될 수 있다.

필요한 **출력**은 다음 요소들을 포함해야 한다:

# 가격 벡터 \mathbf{p} = p_1,\dots,p_m; 각 자원에 대한 가격. 묶음의 가격은 묶음 내 자원들의 가격 합계이므로, 묶음 \mathbf{x}의 가격은 \mathbf{p} \cdot \mathbf{x}=\sum_{j=1}^m p_j\cdot x_j이다.
# 할당 - 각 에이전트 i에 대한 묶음 \mathbf{x}^i.

출력은 다음 요구사항을 충족해야 한다:

# 묶음 \mathbf{x}^i는 i가 감당할 수 있어야 한다. 즉, 그 가격이 에이전트 i의 보유량 가격을 초과해서는 안 된다.
#* 피셔 시장에서는 이는 \mathbf{p} \cdot \mathbf{x}^i \leq B_i를 의미한다.
#* 애로-드브뢰 시장에서는 이는 \mathbf{p} \cdot \mathbf{x}^i \leq \mathbf{p} \cdot \mathbf{e}^i를 의미한다.
# 묶음 \mathbf{x}^i는 i의 수요 집합에 속해야 한다: \mathbf{x}^i \in \text{Demand}_i(\mathbf{p})이며, 이는 (공급량에 관계없이) 모든 감당할 수 있는 묶음 중에서 에이전트의 효용을 최대화하는 묶음 집합으로 정의된다. 예를 들어, 피셔 시장에서는 다음과 같다:  \text{Demand}_i(\mathbf{p}) := \arg\max_{\mathbf{p} \mathbf{x}\leq B_i} u_i(\mathbf{x})
# 시장이 청산된다. 즉, 모든 자원이 할당된다. 해당 가격을 시장 청산 가격이라고 한다.

이러한 요구사항을 충족하는 가격과 할당을 경쟁 균형(CE) 또는 시장 균형이라고 한다. 가격은 또한 균형 가격 또는 청산 가격이라고도 한다.

## 효용 함수의 종류
시장 균형 계산은 에이전트의 효용 함수에 대한 다양한 가정 하에 연구되어 왔다.

* **오목성**: 가장 일반적인 가정(피셔와 애로-드브뢰가 제시)은 에이전트의 효용이 오목 함수라는 것이다. 즉, 수확 체감을 나타낸다.
* **동차성**: 어떤 경우에는 효용이 동차 함수라고 가정된다. 이는 특히 대체 탄력성이 일정한 효용을 포함한다.
* **분리성**: 효용 함수는 묶음의 효용이 묶음 내 개별 자원의 효용의 합인 경우 분리 가능이라고 불린다. 즉,  u_i(\mathbf{x}) = \sum_{j=1}^m u_{i,j}(x_j).
* **부분 선형성**은 분리성의 특수한 경우로, 각 개별 자원에 대한 효용 함수  u_{i,j}(x_j)가 xj의 구간별 선형 함수인 경우이다.
* **선형성**은 각 개별 자원에 대한 효용 함수가 선형 함수인 더욱 특수한 경우이다. 즉, u_i(\mathbf{x}) = \sum_{j=1}^m u_{i,j}\cdot x_j이며, 여기서 u_{i,j}는 상수이다.
부분 선형 및 오목한 효용은 종종 PLC라고 불리며; 분리 가능하기도 한 경우 SPLC라고 불린다.

## 주요 결과
### 근사 알고리즘
스카프는 스페르너 보조정리를 사용하여 CE의 존재를 처음으로 보였다( 피셔 시장 참조). 그는 또한 근사 CE를 계산하는 알고리즘을 제시했다.

메릴은 근사 CE를 위한 확장된 알고리즘을 제시했다.

카카데, 컨스, 오르티즈는 에이전트가 그래프에 위치하고 인접한 에이전트 간에만 거래가 발생할 수 있는 일반화된 애로-드브뢰 시장에서 근사 CE를 위한 알고리즘을 제시했다. 그들은 비선형 효용을 고려했다.

뉴먼과 프리막은 선형 효용을 가진 애로-드브뢰 시장에서 CE를 찾는 타원체 방법의 두 가지 변형을 연구했다. 그들은 내접 타원체 방법이 외접 타원체 방법보다 계산 효율적임을 증명했다.

### 난이도 결과
어떤 경우에는 근사 CE를 계산하는 것이 PPAD-hard이다.

* 데바누르와 칸난은 PLC 효용의 특수한 경우인 레온티에프 효용을 가진 애로-드브뢰 시장에서 PPAD-난이도를 증명했다.
* 첸, 다이, 두, 텅은 SPLC 효용을 가진 애로-드브뢰 시장에서 PPAD-난이도를 증명했다. 그들의 증명은 PPAD가 P에 속하지 않는 한 이 시장 균형 문제가 FPTAS를 갖지 않음을 보여준다.
* 첸과 텅은 SPLC 효용을 가진 피셔 시장에서 PPAD-난이도를 증명했다.
* 초두리, 가르그, 맥글로클린, 메타는 나쁜 재화와 선형 효용을 가진 교환(애로-드브뢰) 시장에서 CE 존재를 보장하는 특정 조건 하에서도 PPAD-난이도를 증명했다.

### 정확한 알고리즘
데바누르, 파파디미트리우, 사베리, 바지라니는 선형 효용 함수를 가진 피셔 시장에서 균형을 정확하게 계산하는 다항 시간 알고리즘을 제시했다. 그들의 알고리즘은 KKT 조건과 볼록 프로그램의 강화된 설정에서 원시-쌍대 패러다임을 사용한다. 그들의 알고리즘은 약 다항식적이다: O((n+m)^5\log(u_{\max}) + (n+m)^4\log{B_{\max}})개의 최대 흐름 문제를 해결하며, 따라서 O((n+m)^8\log(u_{\max}) + (n+m)^7\log{B_{\max}}) 시간에 실행된다. 여기서 umax와 Bmax는 각각 최대 효용과 예산이다.

올린은 선형 효용을 가진 피셔 시장 모델에 대해 개선된 알고리즘을 제시했으며, O((n+m)^4\log(u_{\max}) + (n+m)^3 B_{\max}) 시간에 실행된다. 그는 이후 자신의 알고리즘을 개선하여 강다항 시간에 실행되도록 했다: O((m+n)^4\log(m+n)).

데바누르와 칸난은 모든 자원이 재화(효용이 양수)인 오목 효용 함수를 가진 애로-드브뢰 시장에 대한 알고리즘을 제시했다:

* 효용이 SPLC이고 n 또는 m이 상수인 경우, 그들의 알고리즘은 다른 매개변수에 대해 다항식적이다. 이 기술은 가능한 가격 공간을 일정한 수의 초평면을 사용하여 셀로 분해하는 것으로, 각 셀에서 각 구매자의 임계 한계효용이 알려진다 (n과 m이 모두 변수인 경우, 다항 시간 알고리즘의 존재 여부는 미해결로 남았다).
* 효용이 PLC(반드시 분리 가능하지는 않음)이고 m이 상수인 경우, 그들의 알고리즘은 n에 대해 다항식적이다. m과 n이 모두 변수인 경우, CE를 찾는 것은 PPAD-hard이며, 이는 레온티에프 효용의 특수한 경우인 PLC 효용의 경우에도 마찬가지이다 (n이 상수이고 m이 변수인 경우, 다항 시간 알고리즘의 존재 여부는 미해결로 남았다).
코데노티, 맥쿤, 페누마차, 바라다라잔은 대체 탄력성이 1/2 이상인 대체 탄력성 효용을 가진 애로-드브뢰 시장에 대한 알고리즘을 제시했다.

### 나쁜 재화와 혼합 마나
보고몰나이아, 물랭, 산도미르스키, 야노브스카이아는 나쁜 재화(음의 효용을 가진 품목)를 가진 피셔 시장과 재화와 나쁜 재화의 혼합을 가진 피셔 시장에서 CE의 존재와 특성을 연구했다. 재화 설정과 달리, 자원이 나쁜 재화인 경우 CE는 선형 효용을 가진 경우에도 어떤 볼록 최적화 문제도 해결하지 못한다. CE 할당은 실현 가능한 효용 집합의 파레토 프론티어에서 효용의 곱의 지역 최소값, 지역 최대값, 안장점에 해당한다. CE 규칙은 다중값이 된다. 이 연구는 이러한 시장에서 CE를 찾는 알고리즘에 대한 여러 연구로 이어졌다:

* 브란제이와 산도미르스키는 나쁜 재화와 선형 효용을 가진 피셔 시장에서 모든 CE를 찾는 알고리즘을 제시했다. 그들의 알고리즘은 n 또는 m이 고정된 경우 강 다항 시간에 실행된다. 그들의 접근 방식은 세 가지 아이디어를 결합한다: PO 할당의 모든 소비 그래프는 다항 시간에 나열될 수 있고; 주어진 소비 그래프에 대해 CE 후보는 명시적 공식을 통해 구성될 수 있으며; 주어진 할당이 최대 흐름 계산을 사용하여 CE인지 확인할 수 있다.
* 가르그와 맥글로클린은 혼합 마나와 선형 효용을 가진 피셔 시장에서 모든 CE를 계산하는 알고리즘을 제시했다. 그들의 알고리즘은 n 또는 m이 고정된 경우 다항 시간에 실행된다.
*초두리, 가르그, 맥글로클린, 메타는 혼합 마나와 SPLC 효용을 가진 피셔 시장에서 단일 CE를 계산하는 알고리즘을 제시했다. 그들의 알고리즘은 심플렉스와 유사하며 렘케의 방식에 기반한다. 최악의 경우 실행 시간은 다항식적이지 않지만(재화가 있는 경우에도 문제는 PPAD-hard이다), 무작위 인스턴스에서는 빠르게 실행된다. 또한 이 문제는 PPAD에 속하며, 해는 유리수 값이며, 해의 개수는 홀수임을 증명한다. 그들의 알고리즘은 모든 효용이 음수인 특수한 경우에 다항 시간에 실행된다.

n과 m이 모두 변수인 경우, 문제는 계산적으로 어려워진다:

* 초두리, 가르그, 맥글로클린, 메타는 나쁜 재화와 선형 효용을 가진 피셔 시장에서 CE의 존재 여부를 결정하는 것이 NP-hard임을 보여준다. 이 난이도는 모든 δ>0에 대해 (11/12+δ)-CE를 찾는 경우에도, 심지어 동일한 소득에서도 적용된다. 또한 그래프 연결성을 기반으로 CE의 존재에 대한 충분 조건을 증명한다. 이 조건 하에서는 CE가 항상 존재하지만, 이를 찾는 것은 PPAD-hard이다.

## 주요 기법
### 가성비 (Bang-for-buck)
효용이 선형일 때, 에이전트 i의 가성비(BPB 또는 효용-대-화폐)는 지불한 가격으로 나눈 i의 효용으로 정의된다. 단일 자원의 BPB는 bpb_{i,j} :=  \frac{u_{i,j}}{p_j}이며; 총 BPB는 bpb_{i,total} := \frac{\sum_{j=1}^m u_{i,j}\cdot x_{i,j}}{B_i}이다.

선형 효용을 가진 피셔 시장에서 CE를 찾는 데 있어 핵심적인 관찰은, 어떤 CE에서든 그리고 어떤 에이전트 i에 대해서든:

* 총 BPB는 어떤 개별 자원의 BPB보다 약하게 크다, \forall j: bpb_{i,j}\leq bpb_{i,total}  .
* 에이전트 i는 가능한 최대 BPB를 가진 자원만 소비한다. 즉, \forall j: x_{i,j}>0 \implies bpb_{i,j} = bpb_{i,total}.

모든 제품 j에 잠재적 구매자, 즉 u_{i,j}>0인 구매자 i가 있다고 가정하자. 그러면 위 부등식은 p_j>0, 즉 모든 가격이 양수임을 의미한다.

### 셀 분해
셀 분해는 가능한 가격 공간 \mathbb{R}^m_+을 초평면 또는 더 일반적으로 다항 곡면을 사용하여 작은 "셀"로 분할하는 과정이다. 셀은 각 곡면의 어느 쪽에 놓이는지를 지정함으로써 정의된다(다항 곡면의 경우, 셀은 준대수 집합이라고도 알려져 있다). 각 셀에 대해 시장 청산 가격 벡터(즉, 시장 청산 할당이 존재하는 해당 셀 내의 가격)를 찾거나, 해당 셀에 시장 청산 가격 벡터가 포함되어 있지 않음을 확인한다. 문제는 다음 속성을 가진 분해를 찾는 것이다:

* 셀의 총 수는 입력 크기에 대해 다항식적이다. 이는 \mathbb{R}^m_+에서 k개의 초평면의 모든 집합이 공간을 O(k^m)개의 셀로 분할한다는 사실을 사용한다. 이는 m이 고정된 경우 다항식적이다. 또한, 차수가 최대 d인 k개의 다항 곡면의 모든 집합은 공간을 O(k^{m+1}\cdot d^{O(m)})개의 비어 있지 않은 셀로 분할하며, 이들은 출력 크기에 비례하는 시간에 열거될 수 있다.
* 각 셀에서 시장 청산 가격 벡터를 찾는 것은 선형 계획법을 사용하여 다항 시간에 수행될 수 있다.

### 볼록 최적화: 동차 효용
모든 에이전트의 효용이 동차 함수인 경우, 피셔 모델의 균형 조건은 **아이젠버그-게일 볼록 프로그램**이라는 볼록 최적화 프로그램의 해로 작성될 수 있다. 이 프로그램은 예산에 따라 결정되는 가중치로 구매자 효용의 가중 기하 평균을 최대화하는 할당을 찾는다. 동등하게, 이는 효용 로그의 가중 산술 평균을 최대화한다:

:: 최대화 \sum_{i=1}^n \left( B_i\cdot \log{(u_i)} \right)
:: 제약 조건:
:::: 비음 수량: 모든 구매자 i 및 제품 j에 대해: x_{i,j}\geq 0
:::: 충분한 공급: 모든 제품 j에 대해: \sum_{i=1}^n x_{i,j} \leq 1

(공급량은 1로 정규화되므로).

이 최적화 문제는 카루시-쿤-터커 조건(KKT)을 사용하여 해결할 수 있다. 이 조건은 가격 p_1,\dots,p_m으로 해석될 수 있는 라그랑주 승수를 도입한다. 아이젠버그-게일 프로그램을 최대화하는 모든 할당에서 모든 구매자는 요구되는 묶음을 받는다. 즉, 아이젠버그-게일 프로그램의 해는 시장 균형을 나타낸다.

### 바지라니의 알고리즘: 선형 효용, 약다항 시간
동차 효용의 특별한 경우는 모든 구매자가 선형 효용 함수를 가질 때이다. 각 자원이 잠재적 구매자, 즉 해당 자원에서 양의 효용을 얻는 구매자를 가진다고 가정한다. 이 가정 하에 시장 청산 가격은 존재하며 유일하다. 증명은 아이젠버그-게일 프로그램에 기반한다. KKT 조건은 최적 해(할당 x_{i,j} 및 가격 p_j)가 다음 부등식을 만족함을 의미한다:

# 모든 가격은 음수가 아니다: p_j\geq 0.
# 제품이 양의 가격을 가진다면, 모든 공급이 소진된다: p_j>0 \implies \sum_{i=1}^n x_{i,j} = 1.
# 총 BPB는 어떤 개별 자원의 BPB보다 약하게 크다, \forall j: bpb_{i,j}\leq bpb_{i,total}  .
# 에이전트 i는 가능한 최대 BPB를 가진 자원만 소비한다. 즉, \forall j: x_{i,j}>0 \implies bpb_{i,j} = bpb_{i,total}.

모든 제품 j에 잠재적 구매자, 즉 u_{i,j}>0인 구매자 i가 있다고 가정하자. 그러면 부등식 3은 p_j>0, 즉 모든 가격이 양수임을 의미한다. 그러면 부등식 2는 모든 공급이 소진됨을 의미한다. 부등식 4는 모든 구매자의 예산이 소진됨을 의미한다. 즉, 시장이 청산된다. 로그 함수는 엄밀히 오목 함수이므로, 두 개 이상의 균형 할당이 있다면 두 할당에서 각 구매자가 얻는 효용은 동일해야 한다(한 구매자의 효용 감소가 다른 구매자의 효용 증가로 상쇄될 수 없다). 이는 부등식 4와 함께 가격이 유일함을 의미한다.

바지라니는 선형 피셔 시장에서 균형 가격과 할당을 찾는 알고리즘을 제시했다. 이 알고리즘은 위 조건 4에 기반한다. 이 조건은 균형 상태에서 모든 구매자가 현재 가격에서 최대 BPB를 제공하는 제품만 구매한다는 것을 의미한다. 구매자가 현재 가격에서 제품이 최대 BPB를 제공하는 경우 "좋아한다"고 하자. 가격 벡터가 주어지면, 각 간선의 용량이 해당 간선을 통해 "흐르는" 총액을 나타내는 흐름 네트워크를 구성한다. 네트워크는 다음과 같다:

* 소스 노드 s가 있다.
* 각 제품에 대한 노드가 있다. s에서 각 제품 j로의 간선이 있으며, 용량은 p_j이다 (이는 제품 j에 소비될 수 있는 최대 금액으로, 공급량이 1로 정규화되었기 때문이다).
* 각 구매자에 대한 노드가 있다. 제품에서 구매자로의 간선은 구매자가 해당 제품을 (현재 가격에서) 좋아하는 경우 무한 용량을 갖는다.
* 목표 노드 t가 있다. 각 구매자 i에서 t로의 간선이 있으며, 용량은 B_i이다 (i의 최대 지출).

가격 벡터 p는 ({s},V\{s})와 (V\{t},{t}) 두 절단이 최소 컷일 때만 균형 가격 벡터이다. 따라서 균형 가격 벡터는 다음 방식으로 찾을 수 있다:

* 균형 가격보다 낮게 보장되는 매우 낮은 가격으로 시작한다. 이 가격에서 구매자는 예산이 남아 있다(즉, 최대 흐름이 t로 들어가는 노드의 용량에 도달하지 않는다).
* 모든 예산이 소진될 때까지 가격을 지속적으로 인상하고 이에 따라 흐름 네트워크를 업데이트한다.

이 문제를 약다항 시간에 해결하는 알고리즘이 있다.

## 온라인 계산
최근 가오, 페이사코비치, 크로어는 시장 균형의 온라인 계산을 위한 알고리즘을 제시했다.

## 같이 보기
* 효율적인 무질투 분할
* 효율적인 대략 공정한 품목 할당
* 내쉬 균형 계산 - 밀접하게 관련된 계산 문제.
* 비례 반응 역학 - (특정 조건 하에서) 시장 균형으로 수렴하는 분산 프로세스.

## 더 읽어보기
*는 2004년까지의 시장 균형 계산 역사를 조사한다.
*는 레온티에프 및 PLC 효용을 가진 교환 시장에서 정확하고 근사적인 균형을 계산하는 복잡성을 연구한다.
*는 내쉬 후생을 극대화하여 시장 균형을 근사화하는 방법을 논의한다.
*는 비례 반응 역학을 제시하고 그것이 시장 균형으로 수렴함을 증명한다.
*는 비례 반응 역학의 일반화를 제시하며, 에이전트가 총 대체재 가치 평가를 가질 때 시장 균형으로 수렴함을 보인다.

## 각주

분류:시장 (경제학)