피셔 시장

**피셔 시장**(Fisher market)은 어빙 피셔에게 귀속되는 경제 모형이다. 이 모형은 다음 구성 요소를 포함한다:author=Yishay Mansour * 미리 지정된 공급량을 가진 m개의 가분 상품 집합(일반적으로 각 상품의 공급량이 1이 되도록 정규화됨). * n명의 구매자 집합. * 각 구매자 i=1,\dots,n에 대해 미리 지정된 화폐 예산 B_i가 있다. 각 상품 j는 가격 p_j를 가지며, 가격은 아래에 설명된 방법에 따라 결정된다. 상품 묶음의 가격은 묶음 내 상품 가격의 합이다. 묶음은 벡터 x = x_1,\dots,x_m으로 표현되며, 여기서 x_j는 상품 j의 수량이다. 따라서 묶음 x의 가격은 p(x)=\sum_{j=1}^m p_j\cdot x_j이다. 묶음이 구매자의 예산 내에 있으면 그 묶음은 구매자에게 구매 가능하다. 즉, 묶음 x는 구매자 i에게 p(x)\leq B_i이면 구매 가능하다. 각 구매자는 묶음에 대한 선호 관계를 가지며, 이는 효용 함수로 표현될 수 있다. 구매자 i의 효용 함수는 u_i로 표시된다. 구매자의 수요 집합은 구매 가능한 모든 묶음 중에서 구매자의 효용을 극대화하는 구매 가능한 묶음들의 집합이다. 즉: :\text{Demand}_i(p) := \arg\max_{p(x)\leq B_i} u_i(x). **경쟁 균형**(CE)은 각 에이전트에게 자신의 수요 집합에서 묶음을 할당할 수 있고, 총 할당량이 상품 공급량과 정확히 일치하는 가격 벡터 p_1,\dots,p_m이다. 해당 가격은 시장 청산 가격이라고 불린다. 피셔 시장 분석의 주요 과제는 CE를 찾는 것이다.chapter=Chapter 5: Combinatorial Algorithms for Market Equilibria / Vijay V. Vazirani103–105
# 관련 모형
* 피셔 시장 모형에서 예산은 본질적인 가치를 가지지 않으며, 상품을 구매하는 데만 유용하다. 이는 돈 자체가 상품이며 자체 가치를 가지는 준선형 효용을 가진 에이전트가 있는 **왈라스 시장**과는 대조적이다. * **애로-드브뢰 모형**은 피셔 모형의 일반화로, 각 에이전트가 구매자와 판매자 모두가 될 수 있다. 즉, 각 에이전트는 돈만 가진 것이 아니라 상품 묶음을 가지고 온다. * **아이스엔버그-게일 시장**은 선형 피셔 시장의 또 다른 일반화이다.doi=10.1016/j.geb.2008.11.011
# indivisible가분 상품이 있는 피셔 시장

## 균형의 존재
시장의 모든 상품이 가분일 때, CE는 항상 존재한다. 이는 유명한 스퍼너 보조정리를 사용하여 증명할 수 있다.doi=10.2307/190938367 수량은 상품당 1단위로 정규화되고, 예산은 합계가 1이 되도록 정규화되었다고 가정한다. 또한 모든 상품이 좋다고 가정한다. 즉, 에이전트는 자신이 감당할 수 있다면 항상 각 상품을 더 많이 가지는 것을 엄격하게 선호한다. m개의 정점을 가진 표준 단체를 고려한다. 이 단체의 각 점은 모든 가격의 합이 1인 가격 벡터에 해당한다. 따라서 모든 상품의 총 가격은 1이다. 각 가격 벡터 p에서 각 에이전트의 수요 집합을 찾고, 그 다음 모든 수요 집합의 합계를 계산하고, 그 다음 이 집계된 수요의 총 가격을 찾을 수 있다. 각 수요 집합의 가격이 에이전트의 예산 이하이고, 예산의 합계가 1 이하이므로, 집계된 수요의 가격은 1 이하이다. 따라서 각 p에 대해 총 수요가 1 이하인 상품이 적어도 하나 존재한다. 이러한 상품을 p에서 "고가 상품"이라고 부르자. m-정점 단체를 삼각분할하고, 각 삼각분할-정점 p에 p에서 임의의 고가 상품의 인덱스를 붙인다. 단체의 각 면에서는 일부 상품의 가격이 0이다. 모든 상품이 좋으므로, 가격이 0인 상품에 대한 각 에이전트의 수요는 항상 1이다. 따라서 가격이 0인 상품은 결코 고가로 간주될 수 없다. 따라서 위 라벨링은 스퍼너 경계 조건을 만족한다. 스퍼너 보조정리에 의해, m개의 다른 라벨이 붙은 정점을 가진 작은 단체가 존재한다. 수요 함수는 연속적이므로, 점점 더 미세한 삼각분할을 취함으로써 모든 상품이 고가인 단일 가격 벡터 p∗를 찾을 수 있다. 즉, 모든 상품에 대한 집계 수요가 1 이하이다. 그러나 모든 예산의 합이 1이므로, p∗의 각 상품에 대한 집계 수요는 정확히 1이어야 한다. 따라서 p∗는 시장 청산 가격의 벡터이다.
## 균형 계산
스퍼너 보조정리를 사용하여 CE를 찾을 수 있지만, 계산적으로 매우 비효율적이다. 더 효율적인 방법이 있다(시장 균형 계산 참조). 데바누어, 파파디미트리우, 사베리, 바지라니url-access=subscription는 선형 효용 함수를 가진 피셔 시장의 균형을 정확하게 계산하는 다항 시간 알고리즘을 제시했다. 그들의 알고리즘은 KKT 조건 및 볼록 프로그램의 확장된 설정에서 원시-이중 패러다임을 사용한다. 그들의 알고리즘은 약-다항식이다. O((n+m)^5\log(u_{\max}) + (n+m)^4\log{B_{\max)개의 최대 유량 문제를 해결하므로, 최대 효용과 예산을 각각 umax와 Bmax라고 할 때, O((n+m)^8\log(u_{\max}) + (n+m)^7\log{B_{\max) 시간에 실행된다. 올린s2cid=8235905은 선형 효용을 가진 피셔 시장 모형에 대해 개선된 알고리즘을 제시했으며, O((n+m)^4\log(u_{\max}) + (n+m)^3 B_{\max}) 시간에 실행된다. 그는 이후 자신의 알고리즘을 강한-다항 시간: O((m+n)^4\log(m+n))에 실행되도록 개선했다. 첸과 텅s2cid=7817966은 에이전트의 효용이 임의의 SPLC(분리 가능한 선형-구간별 오목) 함수일 때, CE를 찾는 것이 PPAD-hard임을 증명했다.
## 악재와 혼합된 만노
보고몰나이아, 물랭, 산도미르스키, 야노브스카이아는 악재(음의 효용을 가진 항목)가 있는 피셔 시장에서 CE의 존재와 특성을 연구했다doi-access=free 그리고 재화와 악재의 혼합이 있는 시장에서도 연구했다.s2cid=17081755 재화가 있는 설정과 대조적으로, 자원이 악재일 때는 선형 효용이라도 CE는 어떤 볼록 최적화 문제도 해결하지 못한다. CE 할당은 실현 가능한 효용 집합의 파레토 프런티어에서 효용 곱의 국소 최소값, 국소 최대값, 안장점에 해당한다. CE 규칙은 다중값이 된다. 이 연구는 그러한 시장에서 CE를 찾는 알고리즘에 대한 여러 연구로 이어졌다: * 브란제이와 산도미르스키date=2019-07-03는 악재와 선형 효용을 가진 피셔 시장에서 모든 CE를 찾는 알고리즘을 제시했다. 그들의 알고리즘은 n 또는 m이 고정될 경우 강한 다항 시간에 실행된다. 그들의 접근 방식은 세 가지 아이디어를 결합한다: PO 할당의 모든 소비 그래프는 다항 시간에 나열될 수 있고, 주어진 소비 그래프에 대해 CE 후보는 명시적 공식을 통해 구성될 수 있으며, 주어진 할당은 최대 유량 계산을 사용하여 CE인지 확인할 수 있다. * 가르그와 맥글로플린isbn=978-1-4503-7518-4은 혼합된 만노와 선형 효용을 가진 피셔 시장에서 모든 CE를 계산하는 알고리즘을 제시했다. 그들의 알고리즘은 n 또는 m이 고정될 경우 다항 시간에 실행된다. * 초두리, 가르그, 맥글로플린, 메타는 혼합된 만노와 SPLC 효용을 가진 피셔 시장에서 단일 CE를 계산하는 알고리즘을 제시했다. 그들의 알고리즘은 심플렉스(simplex)와 유사하며 렘케의 방식을 기반으로 한다. 최악의 경우 실행 시간은 다항식이 아니지만(재화가 있는 경우에도 문제는 PPAD-hard이다s2cid=7817966), 무작위 인스턴스에서는 빠르게 실행된다. 또한 문제는 PPAD에 속하며, 해는 유리수 값이고, 해의 개수는 홀수임을 증명한다. 그들의 알고리즘은 모든 효용이 음수일 때 특수한 경우에 다항 시간에 실행된다. n과 m이 모두 가변일 경우, 문제는 계산적으로 어려워진다: * 초두리, 가르그, 맥글로플린, 메타first4=RutaThm.3는 악재와 선형 효용을 가진 피셔 시장에서 CE가 존재하는지 여부를 결정하는 것이 NP-난해임을 보여준다. 동일한 난이도는 모든 δ>0에 대해 (11/12+δ)-CE를 찾는 경우에도, 심지어 소득이 동일한 경우에도 유지된다. 그들은 또한 그래프 연결성을 기반으로 CE의 존재에 대한 충분 조건을 증명한다. 이 조건이 충족되면 CE는 항상 존재하지만, 이를 찾는 것은 PPAD-난해이다.Thm.5
# indivisible분할 불가능한 상품이 있는 피셔 시장
시장의 상품이 분할 불가능할 때는 CE의 존재가 보장되지 않는다. CE가 존재하는지 여부를 결정하는 것은 계산적으로 어려운 문제이다. 덩 외doi-access=free는 각 에이전트가 초기 소득(초기 소득이 아닌)을 가지고 시장에 오고 모든 가치가 가산적이라고 가정하는 시장을 연구했다. 그들은 CE가 존재하는지 여부를 결정하는 것이 3명의 에이전트라도 NP-난해임을 증명했다. 그들은 CE 조건을 두 가지 방식으로 완화하는 근사 알고리즘을 제시했다: (1) 각 에이전트에게 할당된 묶음은 주어진 가격에서 최적의 1-엡실론 값 이상이고, (2) 수요는 공급의 1-엡실론배 이상이다. 부베레와 르메트르issn=1573-7454는 동등 소득 경쟁 균형(CEEI)을 항목의 공정한 할당 규칙으로 연구했다. 그들은 모든 에이전트가 가산적 가치 함수를 가진다고 가정할 때 이를 네 가지 다른 공정성 기준과 관련시켰다. 그들은 CEEI가 존재하는지 여부를 결정하는 계산 복잡성을 물었다. 이 질문은 얼마 지나지 않아 아지즈에 의해 답변되었다.s2cid=11495811 그는 두 명의 에이전트와 m개의 항목이 있을 때 이 문제가 약한 NP-난해이며, n명의 에이전트와 3n개의 항목이 있을 때 강한 NP-난해임을 증명했다. 그는 또한 CEEI-FRAC라는 더 강력한 조건을 제시했는데, 흥미롭게도 이는 확인하기 더 쉽다 — 다항 시간 내에 확인할 수 있다. 밀터센, 호세이니, 브란제이s2cid=656603는 주어진 할당이 CEEI인지 확인하는 것조차 co-NP-난해임을 증명했다. 그들은 또한 단일 지향 에이전트에 대한 CEEI도 연구했다. 이 경우, 주어진 할당이 CEEI인지 확인하는 것은 다항 시간이지만, CEEI가 존재하는지 확인하는 것은 co-NP-완전이다. 하이넨 외isbn=9783319231136는 부베레와 르메트르의 작업을 가산적 효용 함수에서 k-가산적 효용 함수로 확장했는데, 여기서 각 에이전트는 최대 k개의 항목을 포함하는 묶음에 대한 값을 보고하고, 더 큰 묶음의 값은 기본 묶음의 값을 더하고 빼는 방식으로 결정된다. 부디쉬s2cid = 154703357는 에이전트가 묶음에 대해 임의의 선호 관계를 가질 수 있는 가장 일반적인 설정을 연구했다. 그는 동등 소득 근사 경쟁 균형 메커니즘을 발명했는데, 이는 CEEI 조건을 두 가지 방식으로 완화한다: (1) 에이전트의 소득이 정확히 같지 않고, (2) 소수의 항목이 할당되지 않은 상태로 남을 수 있다. 그는 근사-CEEI가 항상 존재함을 증명했다(비록 오스만 외s2cid=2780775가 최근 근사-CEEI의 계산이 PPAD 완전임을 증명했지만). 바르만과 크리슈나무르티class=cs.GT는 모든 에이전트가 가산적 효용을 가지는 피셔 시장을 연구한다. 그들은 부분 CE(일부 상품이 분할됨)가 항상 에이전트의 예산을 변경함으로써 정수 CE(상품이 분할 불가능하게 유지됨)로 반올림될 수 있음을 보여준다. 각 예산의 변경은 부분 CE에서 상품의 가장 큰 가격만큼 높을 수 있다. 바바이오프, 니산, 탈감-코헨class=cs.GT은 소득이 일반적일 때, 즉 유한한 등식 집합을 만족하지 않을 때 CE가 존재하는지 연구했다. 다른 말로 하면: 거의 모든 소득 벡터에 대해 CE가 존재하는지 여부이다. 그들은 세 가지 상품에 대해, 그리고 네 가지 상품과 두 명의 에이전트에 대해 존재를 증명했다. 그들은 다섯 가지 상품과 두 명의 에이전트에 대해 비존재를 증명했다. 이후, 네 가지 상품과 세 명의 에이전트가 있을 때 가치가 비가산적이면 CE가 존재하지 않을 수 있지만, 가치가 가산적이면 항상 존재한다는 것이 증명되었다.s2cid=210911501