메커니즘 디자인

메커니즘 디자인은 경제적 메커니즘과 인센티브를 설계 전략에 적용하여 전략적 환경에서 원하는 목표를 향해 설계자가 합리적으로 행동하는 엔지니어링 접근법을 사용한다. 게임이 끝날 때부터 시작하여 뒤로 이동하기 때문에 역게임 이론이라고도 한다. 경제 및 정치(시장, 경매, 투표 절차)에서 네트워크 시스템(인터넷 도매인 간 라우팅, 스폰서 검색 경매)에 이르기까지 광범위한 응용 프로그램을 보유하고 있다.

메커니즘 설계는 개인 정보 게임의 클래스에 대한 솔루션 개념을 연구한다. 레오니드 후르비츠는 "디자인 문제에서는 목표 기능이 주된 '주어진' 반면 메커니즘은 알려지지 않았다" 고 설명한다. 따라서 디자인 문제는 전통적 경제 이론의 '역 (inverse)'이며, 이는 일반적으로 주어진 메커니즘의 수행 분석에 사용된다.

직관

재미있는 베이지안 게임 클래스에서는 "교장"이라고 불리는 한 플레이어가 다른 플레이어에게 개인적으로 알려진 정보에 자신의 행동을 적용하고 싶어한다. 예를 들어, 교장은 판매원이 피칭하는 중고차의 실제 품질을 알고 싶어한다. 그는 진실을 왜곡하는 것이 그의 관심사이기 때문에 단순히 판매원에게 물어 봄으로써는 아무것도 배울 수 없다. 그러나 메커니즘 설계에서 주자에게는 장점이 하나 있다. 규칙이 다른 사람이 자신이 원하는 방식으로 행동하도록 영향을 줄수 있는 게임을 디자인할 수 있다.

메커니즘 설계 이론이 없다면 교장의 문제는 해결하기 어려울 것이다. 가능한 모든 게임을 고려하고 다른 플레이어의 전술에 가장 영향을 미치는 게임을 선택해야 산다. 또한 교장은 거짓말쟁이 요원으로부터 결론을 이끌어내야 한다. 메커니즘 설계, 특히 계시 원칙 덕분에 교장은 에이전트가 진실하게 개인정보를 보고하는 게임만 고려하면 된다.

기초

메커니즘

메커니즘 설계 게임은 주체라고 불리는 에이전트 중 하나가 보수 구조를 선택하는 개인 정보 게임이다. Harsanyi (1967)에 이어, 대리인은 보상과 관련된 정보를 포함하고있는 비밀 메시지 "를 받는다. 예를 들어 메시지에는 판매 환경 설정이나 판매 품질에 대한 정보가 포함될 수 있다. 우리는 이 정보를 상담원의 "유형"(대개 \ theta 및 그에 따른 유형 \ Theta의 공간)이라고 부른다. 그런 다음 요원은 전략적 거짓말 일 수있는 교장 (일반적으로 모자 {\ hat {\ theta}}으로 표시)에 유형을 보고한다. 보고서 다음에, 교장 및 대리인은 교장이 선택한 보수 구조에 따라 지급된다.

게임의 타이밍은 다음과 같다.

1. The principal commits to a mechanism $y()$ that grants an outcome $y$ as a function of reported type
2. The agents report, possibly dishonestly, a type profile ${\hat {\theta }}$
3. The mechanism is executed (agents receive outcome $y({\hat {\theta }})$)

$y(\theta )=\{x(\theta ),t(\theta )\},\ x\in X,t\in T$여기서 x는 유형의 함수로 렌더링되거나 수신 된 상품의 할당을 나타내며, t는 유형의 함수로서 금전적이 용을 나타낸다.

벤치마킹으로 설계자는 종종 완전한 정보 하에서 일어날 일을 정의한다. 사회적 선택함수$f(\theta )$ (true) 유형프로파일을 수신 또는 확정된 상품의 할당에 직접 매핑하고,

$f(\theta ):\Theta \rightarrow X$

In contrast a mechanism maps the reported type profile to an outcome (again, both a goods allocation $x$ and a money transfer $t$)

계시의 원리

제안 된 메커니즘은 베이지안 게임 (개인 정보 게임)을 구성하며, 잘 작동하면 베이지안 내쉬 균형이 있다. 평형 에이전트에서 유형에 따라 전략적으로 보고서를 선택한다.

${\hat {\theta }}(\theta )$

그러한 상황에서 베이즈 균형을 풀기란 어렵다. 왜냐하면 에이전트의 최상의 응답 전략을 해결하고 가능한 전략적 거짓으로부터 최상의 추론을 하기 때문이다. 계시 원리와 같은 결과로 인해 디자이너는 메커니즘에 관계없이 에이전트가 유형을 진실하게 보고하는 평형에 주의를 기울일 수 있다. 계시 원리는 다음과 같이 말한다. "모든 베이지안 내쉬 균형은 동일한 평형 결과를 가진 베이지안 게임과 일치하지만 플레이어가 진실로 유형을 보고한다."

이것은 매우 유용하다. 이 원리는 모든 플레이어가 진실로 유형을 보고한다고 가정함으로써 베이지안 평형을 풀 수 있도록 해준다 (인센티브 호환성 제약이 있음). 한 번의 타격으로 전략적 행동이나 거짓말을 고려할 필요가 없다.

Its proof is quite direct. Assume a Bayesian game in which the agent's strategy and payoff are functions of its type and what others do, $u_{i}\left(s_{i}(\theta _{i}),s_{-i}(\theta _{-i}),\theta _{i}\right)$. By definition agent i's equilibrium strategy $s(\theta _{i})$ is Nash in expected utility:

 195/5000 에이전트가 동일한 평형을 선택하게하는 메커니즘을 정의하기만 하면 된다. 가장 쉽게 정의할 수 있는 메커니즘은 상담원이 에이전트의 평형 전략을 수행하는 데 필요한 메커니즘이다.

$y({\hat {\theta }}):\Theta \rightarrow S(\Theta )\rightarrow Y$

Under such a mechanism the agents of course find it optimal to reveal type since the mechanism plays the strategies they found optimal anyway. Formally, choose $y(\theta )$ such that

${\begin{aligned}\theta _{i}\in {}&\arg \max _{\theta '_{i}\in \Theta }\sum _{\theta _{-i}}\ p(\theta _{-i}\mid \theta _{i})\ u_{i}\left(y(\theta '_{i},\theta _{-i}),\theta _{i}\right)\\[5pt]&=\sum _{\theta _{-i}}\ p(\theta _{-i}\mid \theta _{i})\ u_{i}\left(s_{i}(\theta ),s_{-i}(\theta _{-i}),\theta _{i}\right)\end{aligned}}$

Implementability

The designer of a mechanism generally hopes either

• to design a mechanism $y()$ that "implements" a social choice function
• to find the mechanism $y()$ that maximizes some value criterion (e.g. profit)

To implement a social choice function $f(\theta )$ is to find some $t(\theta )$ transfer function that motivates agents to pick outcome $x(\theta )$. Formally, if the equilibrium strategy profile under the mechanism maps to the same goods allocation as a social choice function,

$f(\theta )=x\left({\hat {\theta }}(\theta )\right)$

we say the mechanism implements the social choice function.

계시 원리 덕분에 설계자는 일반적으로 연관된 진리 탐구 게임을 해결함으로써 사회적 선택을 구현하는 전달 함수 $t(\theta )$

${\hat {\theta }}(\theta )=\theta$

we say such a mechanism is truthfully implementable (or just "implementable"). The task is then to solve for a truthfully implementable $t(\theta )$ and impute this transfer function to the original game. An allocation $x(\theta )$ is truthfully implementable if there exists a transfer function $t(\theta )$ such that

$u(x(\theta ),t(\theta ),\theta )\geq u(x({\hat {\theta }}),t({\hat {\theta }}),\theta )\ \forall \theta ,{\hat {\theta }}\in \Theta$

인센티브 호환성 (IC) 제약이라고도 한다.

응용 프로그램에서 IC 조건은 $t(\theta )$의 모양을 유용한 방법으로 설명하는 핵심 요소이다. 특정 조건 하에서는 전달 함수를 분석적으로 분리 할 수도 있다. 또한 에이전트가 게임을하지 않을 수있는 경우 참가 (개별 합리성) 제약 조건이 추가되는 경우가 있다.

필요성

Consider a setting in which all agents have a type-contingent utility function $u(x,t,\theta )$. Consider also a goods allocation $x(\theta )$ that is vector-valued and size $k$ (which permits $k$ number of goods) and assume it is piecewise continuous with respect to its arguments.

The function $x(\theta )$ is implementable only if

$\sum _{k=1}^{n}{\frac {\partial }{\partial \theta }}\left({\frac {\partial u/\partial x_{k}}{\left|\partial u/\partial t\right|}}\right){\frac {\partial x}{\partial \theta }}\geq 0$

whenever $x=x(\theta )$ and $t=t(\theta )$ and x is continuous at $\theta$. This is a necessary condition and is derived from the first- and second-order conditions of the agent's optimization problem assuming truth-telling.

Its meaning can be understood in two pieces. The first piece says the agent's marginal rate of substitution (MRS) increases as a function of the type,

${\frac {\partial }{\partial \theta }}\left({\frac {\partial u/\partial x_{k}}{\left|\partial u/\partial t\right|}}\right)={\frac {\partial }{\partial \theta }}\mathrm {MRS} _{x,t}$

In short, agents will not tell the truth if the mechanism does not offer higher agent types a better deal. Otherwise, higher types facing any mechanism that punishes high types for reporting will lie and declare they are lower types, violating the truthtelling IC constraint. The second piece is a monotonicity condition waiting to happen,

${\frac {\partial x}{\partial \theta }}$

which, to be positive, means higher types must be given more of the good.

There is potential for the two pieces to interact. If for some type range the contract offered less quantity to higher types $\partial x/\partial \theta <0$, it is possible the mechanism could compensate by giving higher types a discount. But such a contract already exists for low-type agents, so this solution is pathological. Such a solution sometimes occurs in the process of solving for a mechanism. In these cases it must be "ironed." In a multiple-good environment it is also possible for the designer to reward the agent with more of one good to substitute for less of another (e.g. butter for margarine). Multiple-good mechanisms are an ongoing problem in mechanism design theory.

Sufficiency

Mechanism design papers usually make two assumptions to ensure implementability:

$1.\ {\frac {\partial }{\partial \theta }}{\frac {\partial u/\partial x_{k}}{\left|\partial u/\partial t\right|}}>0\ \forall k$

This is known by several names: the single-crossing condition, the sorting condition and the Spence–Mirrlees condition. It means the utility function is of such a shape that the agent's MRS is increasing in type.

$2.\ \exists K_{0},K_{1}{\text{ such that }}\left|{\frac {\partial u/\partial x_{k}}{\partial u/\partial t}}\right|\leq K_{0}+K_{1}|t|$

This is a technical condition bounding the rate of growth of the MRS.

These assumptions are sufficient to provide that any monotonic $x(\theta )$ is implementable (a $t(\theta )$ exists that can implement it). In addition, in the single-good setting the single-crossing condition is sufficient to provide that only a monotonic $x(\theta )$ is implementable, so the designer can confine his search to a monotonic $x(\theta )$.

강조 표시된 결과

수익 등가정리

Vickrey (1961)는 대규모 경매의 모든 구성원이 판매자에게 동일한 예상 수익을 보장하고 예상 수익이 판매자가 할 수 있는 최선이라는 유명한 결과를 제공한다. 다음과 같은 경우

1. 구매자는 동일한 평가 기능을 가진다(유형의 기능일 수 있음)
2. 구매자의 유형은 독립적으로 분배된다.
3. 구매자 유형은 확률 분포에서 가져온다.
4. 유형 분포는 단조로운 위험률 특성을 나타낸다.
5. 매커니즘은 가치가 가장 높은 구매자에게 상품을 판매한다.

마지막 조건은 정리에 중요하다. 이는 판매자가 더 높은 수익을 달성하려면 더 낮은 가치를 가진 에이전트에게 항목을 제공할 기회를 가져야 한다는 것을 의미한다. 일반적으로 이것은 그가 항목을 전혀 판매하지 않는 위험을 감수해야 함을 의미한다.

Vickrey–Clarke–Groves mechanisms

The Vickrey (1961) auction model was later expanded by ClarkeClarke (1971) and Groves to treat a public choice problem in which a public project's cost is borne by all agents, e.g. whether to build a municipal bridge. The resulting "Vickrey–Clarke–Groves" mechanism can motivate agents to choose the socially efficient allocation of the public good even if agents have privately known valuations. In other words, it can solve the "tragedy of the commons"—under certain conditions, in particular quasilinear utility or if budget balance is not required.

Consider a setting in which $I$ number of agents have quasilinear utility with private valuations $v(x,t,\theta )$ where the currency $t$ is valued linearly. The VCG designer designs an incentive compatible (hence truthfully implementable) mechanism to obtain the true type profile, from which the designer implements the socially optimal allocation

$x_{I}^{*}(\theta )\in {\underset {x\in X}{\operatorname {argmax} }}\sum _{i\in I}v(x,\theta _{i})$

The cleverness of the VCG mechanism is the way it motivates truthful revelation. It eliminates incentives to misreport by penalizing any agent by the cost of the distortion he causes. Among the reports the agent may make, the VCG mechanism permits a "null" report saying he is indifferent to the public good and cares only about the money transfer. This effectively removes the agent from the game. If an agent does choose to report a type, the VCG mechanism charges the agent a fee if his report is pivotal, that is if his report changes the optimal allocation x so as to harm other agents. The payment is calculated

$t_{i}({\hat {\theta }})=\sum _{j\in I-i}v_{j}(x_{I-i}^{*}(\theta _{I-i}),\theta _{j})-\sum _{j\in I-i}v_{j}(x_{I}^{*}({\hat {\theta }}_{i},\theta _{I}),\theta _{j})$

which sums the distortion in the utilities of the other agents (and not his own) caused by one agent reporting.

Gibbard–Satterthwaite theorem

GibbardGibbard (1973) and SatterthwaiteSatterthwaite (1975) give an impossibility result similar in spirit to Arrow's impossibility theorem. For a very general class of games, only "dictatorial" social choice functions can be implemented.

한 사회자가 항상 자신이 가장 좋아하는 물품 분배를받는다면 사회적 선택 함수f() 는 독재 적이지만,

이 정리는 일반적 조건 하에서 진실하게 구현 가능한 사회 선택 기능은 독재 적이어야하며,

1.  X는 유한이며 세 개 이상의 요소를 포함한다. 
   
2. 선호도는 이성적이다.
3. $f(\Theta )=X$

Myerson–Satterthwaite 정리

Myerson and Satterthwaite (1983)는 한 당사자가 손실로 거래를 할 수 있는 위험없이 각 당사자가 비밀스럽고 확률 론적으로 다양한 가치 평가를 할 때 두 당사자가 재화를 거래하는 효율적인 방법이 없음을 보여준다. 그것은 복지 경제의 근본 정리에 부정적 거울의 일종 인 경제학에서 가장 현저한 부정적 결과 중 하나이다.

예시

가격 차별

MirrleesMirrlees (1971) introduces a setting in which the transfer function t() is easy to solve for. Due to its relevance and tractability it is a common setting in the literature. Consider a single-good, single-agent setting in which the agent has quasilinear utility with an unknown type parameter $\theta$

$u(x,t,\theta )=V(x,\theta )-t$

$u(x(\theta ),t(\theta ),\theta )\geq u(x(\theta '),t(\theta '),\theta )\ \forall \theta ,\theta '$

$u(x(\theta ),t(\theta ),\theta )\geq {\underline {u}}(\theta )\ \forall \theta$

The principal here is a monopolist trying to set a profit-maximizing price scheme in which it cannot identify the type of the customer. A common example is an airline setting fares for business, leisure and student travelers. Due to the IR condition it has to give every type a good enough deal to induce participation. Due to the IC condition it has to give every type a good enough deal that the type prefers its deal to that of any other.

$\int _{\underline {\theta }}^{\overline {\theta }}\left({\frac {\partial V}{\partial x}}(x,\theta )-{\frac {1-P(\theta )}{p(\theta )}}{\frac {\partial ^{2}V}{\partial \theta \,\partial x}}(x,\theta )-{\frac {\partial c}{\partial x}}(x)\right)p(\theta )\,d\theta =0$

교장의 잉여의 평균 왜곡은 0이어야 한다. 일정을 평평하게 하려면 역상이 위의 조건을 충족하는 $\theta$ 간격에 매핑되도록 x를 찾아야 한다.

각주

• Clarke, Edward H. (1971). “Multipart Pricing of Public Goods” (PDF). 《Public Choice》 11 (1): 17–33. doi:10.1007/BF01726210. JSTOR 30022651. 2017년 5월 10일에 원본 문서 (PDF)에서 보존된 문서. 2018년 11월 5일에 확인함. 
• Gibbard, Allan (1973). “Manipulation of voting schemes: A general result” (PDF). 《Econometrica》 41 (4): 587–601. doi:10.2307/1914083. JSTOR 1914083. 
• Groves, Theodore (1973). “Incentives in Teams” (PDF). 《Econometrica》 41 (4): 617–631. doi:10.2307/1914085. JSTOR 1914085. 
• Harsanyi, John C. (1967). “Games with incomplete information played by "Bayesian" players, I-III. part I. The Basic Model”. 《Management Science, special issue: Theory Series》 (INFORMS) 14 (3): 159–182. doi:10.1287/mnsc.14.3.159. JSTOR 2628393. 
• Mirrlees, J. A. (1971). “An Exploration in the Theory of Optimum Income Taxation” (PDF). 《Review of Economic Studies》 38 (2): 175–208. doi:10.2307/2296779. JSTOR 2296779. 2017년 5월 10일에 원본 문서 (PDF)에서 보존된 문서. 2018년 11월 5일에 확인함. 
• Myerson, Roger B.; Satterthwaite, Mark A. (1983). “Efficient Mechanisms for Bilateral Trading” (PDF). 《Journal of Economic Theory》 29 (2): 265–281. doi:10.1016/0022-0531(83)90048-0. 2017년 5월 10일에 원본 문서 (PDF)에서 보존된 문서. 2018년 11월 5일에 확인함. 
• Satterthwaite, Mark Allen (1975). “Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions”. 《Journal of Economic Theory》 10 (2): 187–217. doi:10.1016/0022-0531(75)90050-2. 
• Vickrey, William (1961). “Counterspeculation, Auctions, and Competitive Sealed Tenders” (PDF). 《The Journal of Finance》 16 (1): 8–37. doi:10.1111/j.1540-6261.1961.tb02789.x. 

추가 자료

• Chapter 7 of Fudenberg, Drew; Tirole, Jean (1991), 《Game Theory》, Boston: MIT Press, ISBN 978-0-262-06141-4 . A standard text for graduate game theory.
• Chapter 23 of Mas-Colell; Whinston; Green (1995), 《Microeconomic Theory》, Oxford: Oxford University Press, ISBN 978-0-19-507340-9 . A standard text for graduate microeconomics.
• Milgrom, Paul (2004), 《Putting Auction Theory to Work》, New York: Cambridge University Press, ISBN 978-0-521-55184-7 . Applications of mechanism design principles in the context of auctions.
• Noam Nisan. A Google tech talk on mechanism design.
• Legros, Patrick; Cantillon, Estelle (2007). “What is mechanism design and why does it matter for policy-making?”. Centre for Economic Policy Research. 
• Roger B. Myerson (2008). "Mechanism Design," The New Palgrave Dictionary of Economics Online, Abstract.

외부 링크

• Eric Maskin "Nobel Prize Lecture" delivered on 8 December 2007 at Aula Magna, Stockholm University.