소비집합에 따른 시장균형의 계산복잡도 연구

Abstract

본 논문에서는 미시경제학에서 근본적인 시장균형 모형 중 하나인 Fisher 모형의 계산복잡도를 다룬다. 몇 가지 결과들은 더욱 일반적인 모형인 Arrow-Debreu 모형에 적용될 수 있음을 보인다. Fisher 시장은 상품들과 소비자들로 이루어져 있으며, 소비자들은 자신의 소비집합에서 자신의 예산 이내로 효용을 최대화하는 선택을 한다. 각 상품의 가격은 모든 소비자들이 최적선택을 했을 때 총수요의 가치와 총공급의 가치가 같아지도록 결정되며, 이를 균형가격이라고 한다. 최근 이론컴퓨터 과학자들은 시장균형의 계산에 관심을 기울이고 있다. 계산론 관점에서 일반적으로 시장균형 모형은 풀기 어렵다는 것이 밝혀졌기 때문이다. 컴퓨터 과학자들은 어떤 시장이 주어졌을 때 그 시장이 실제로 균형을 계산할 수 있는지 의문을 품기 시작했다. 논의를 Fisher 시장으로 좁히면, 모든 소비자들의 효용함수가 선형인 시장은 다항시간에 계산 가능하지만, 일반적인 오목 효용함수는 계산하기 어렵다는 사실이 증명됐다. 이 논문에서는 먼저 소비집합이 볼록뿔인 Fisher 시장이 다항시간 내에 계산 가능함을 보인다. 그에 반해 소비집합이 다면체인 Fisher 시장은, 효용함수가 모두 선형으로 주어지는 경우에도 계산이 어렵다는 사실을 증명한다. 이러한 결과는 소비집합에 따른 Fisher 시장의 계산이 쉬운 경우와 어려운 경우의 경계를 보여준다.