애로-드브뢰 교환 시장

경제학에서 애로-드브뢰 교환 시장(영어: Arrow–Debreu exchange market)은 생산이 없고 이미 존재하는 상품의 교환만 있는 애로-드브뢰 모형의 특별한 경우이다. 애로-드브뢰 교환 시장은 다음 구성 요소를 포함한다:

• $m$개의 가분 상품 집합.
• $n$개의 에이전트 집합.
• 각 에이전트 $i=1,\dots ,n$는 상품 집합인 할당 $e_{i}$를 가진다.

각 상품 $j$는 가격 $p_{j}$를 가지며, 가격은 아래에 설명된 방법에 의해 결정된다. 상품 묶음의 가격은 묶음 내 상품 가격의 합이다. 묶음은 벡터 $x=x_{1},\dots ,x_{m}$으로 표현되며, 여기서 $x_{j}$는 상품 $j$의 수량이다. 따라서 묶음 $x$의 가격은 $p\cdot x=\sum _{j=1}^{m}p_{j}\cdot x_{j}$이다.

주어진 가격 벡터에서 에이전트의 예산은 그들의 할당의 총 가격인 $p\cdot e_{i}$이다.

구매자에게 묶음이 감당 가능하다는 것은 해당 묶음의 가격이 구매자 예산 이하임을 의미한다. 즉, 묶음 $x$가 구매자 $i$에게 감당 가능하다는 것은 $p\cdot x\leq p\cdot e_{i}$를 의미한다.

각 구매자는 묶음에 대한 선호 관계를 가지며, 이는 효용 함수로 표현될 수 있다. 구매자 $i$의 효용 함수는 $u_{i}$로 표기된다. 구매자의 수요 집합은 모든 감당 가능한 묶음 중에서 구매자의 효용을 최대화하는 감당 가능한 묶음의 집합이다. 즉:

${\text{Demand}}_{i}(p):=\arg \max _{p\cdot x\leq p\cdot e_{i}}u_{i}(x)$.

경쟁 균형(CE)은 각 에이전트에게 수요 집합에서 묶음을 할당하여 총 할당이 상품 공급과 정확히 일치하도록 하는 가격 벡터 $p_{1},\dots ,p_{m}$이다. 해당하는 가격을 시장 청산 가격이라고 한다. CE는 더 일반적인 애로-드브뢰 모형에서도 항상 존재한다. 주요 과제는 CE를 찾는 것이다.

균형 계산

근사 CE

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

정확한 CE

자인은 모든 에이전트가 선형 효용을 가질 때 정확한 CE를 계산하는 최초의 다항 시간 알고리즘을 제시했다. 그의 알고리즘은 타원체 방법과 동시 디오판토스 근사를 사용하여 볼록 계획법을 푸는 것에 기반한다. 그는 또한 균형에서의 할당 집합이 볼록하며, 균형 가격 자체가 로그 볼록함을 증명했다.

자인의 알고리즘을 기반으로 예는 CE를 찾기 위한 더 실용적인 내부점법을 개발했다.

데바누르와 칸난은 모든 자원이 상품(효용이 양수)인 오목 효용 함수를 가진 교환 시장에 대한 알고리즘을 제시했다:

• 효용이 SPLC(분리 가능한 조각별 선형 오목 함수)이고 n 또는 m이 상수일 때, 그들의 알고리즘은 다른 변수에 대해 다항식이다. 이 기술은 가격 공간을 일정한 수의 초평면을 사용하여 셀로 분해하여 각 셀에서 각 구매자의 임계 한계효용이 알려지도록 한다. n과 m이 모두 변수인 경우, 다항 시간 알고리즘이 존재하는지는 미해결 문제로 남아 있었다. 나중에 첸, 다이, 두, 텅은 SPLC 효용을 가질 때 CE를 계산하는 것이 PPAD-난해하다는 것을 증명했다. 그들의 증명은 또한 이 시장 균형 문제가 PPAD가 P에 포함되지 않는 한 FPTAS를 가지지 않는다는 것을 보여준다.
• 효용이 PLC(조각별 선형 오목 함수이지만 반드시 분리 가능하지는 않음)이고 m이 상수일 때, 그들의 알고리즘은 n에 대해 다항식이다. 그러나 m과 n이 모두 변수일 때, CE를 찾는 것은 레온티예프 효용의 특수한 경우인 PLC 효용(n은 상수이지만 m은 변수인 경우, 다항 시간 알고리즘이 존재하는지는 미해결 문제로 남아 있었다)에 대해서도 PPAD-난해하다.

코데노티, 맥쿤, 페누마차, 바라다라잔은 대체 탄력성이 1/2 이상인 CES 효용을 가진 애로-드브뢰 시장에 대한 알고리즘을 제시했다.

초드리, 가르그, 맥로플린, 메타는 상품이 흉악품인 경우 효용이 선형일 때도, CE 존재를 보장하는 특정 조건에서도 균형을 계산하는 것이 PPAD-난해하다는 것을 증명한다.

생산 시장의 CE

뉴먼과 프리막은 모든 에이전트가 선형 효용을 가질 때 생산이 있는 애로-드브뢰 시장에서 근사 CE를 찾기 위한 두 가지 타원체 방법 변형을 연구했다. 그들은 내접 타원체 방법이 외접 타원체 방법보다 계산 효율적임을 증명했다.

관련 모형

피셔 시장은 에이전트가 구매자이지 판매자가 아닌 더 간단한 시장이다. 각 에이전트는 미리 지정된 예산을 가지고 있으며, 주어진 가격으로 상품을 구매하는 데 사용할 수 있다.

피셔 시장에서는 가격이 오르면 고정된 예산으로 더 적게 구매할 수 있으므로 에이전트의 수요가 항상 감소한다. 그러나 애로-드브뢰 교환 시장에서는 가격이 오르면 에이전트의 예산도 증가하므로 수요가 가격의 단조 함수가 아니다. 이로 인해 애로-드브뢰 교환 시장에서 CE를 계산하는 것이 훨씬 더 어렵다.