메커니즘 디자인

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

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

  • 게임 "디자이너"가 하나를 계승하기보다는 게임 구조를 선택한다는 것
  • 디자이너가 게임의 결과에 관심이 있다는 것

2007 년 노벨 경제학상은 Leonid Hurwicz, Eric Maskin, Roger Myerson에게 수여되었습니다.

직관편집

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

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

기초편집

메커니즘편집

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

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

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

 여기서 x는 유형의 함수로 렌더링되거나 수신 된 상품의 할당을 나타내며, t는 유형의 함수로서 금전적이 용을 나타냅니다.

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

 

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

계시의 원리편집

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

 

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

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

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,  . By definition agent i's equilibrium strategy   is Nash in expected utility:

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

 

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   such that

 

Implementability편집

The designer of a mechanism generally hopes either

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

To implement a social choice function   is to find some   transfer function that motivates agents to pick outcome  . Formally, if the equilibrium strategy profile under the mechanism maps to the same goods allocation as a social choice function,

 

we say the mechanism implements the social choice function.

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

 

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

 

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

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

필요성편집

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

The function   is implementable only if

 

whenever   and   and x is continuous at  . 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,

 

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,

 

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  , 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:

 

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.

 

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

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

Highlighted results편집

Revenue equivalence theorem편집

Vickrey (1961) gives a celebrated result that any member of a large class of auctions assures the seller of the same expected revenue and that the expected revenue is the best the seller can do. This is the case if

  1. The buyers have identical valuation functions (which may be a function of type)
  2. The buyers' types are independently distributed
  3. The buyers types are drawn from a continuous distribution
  4. The type distribution bears the monotone hazard rate property
  5. The mechanism sells the good to the buyer with the highest valuation

The last condition is crucial to the theorem. An implication is that for the seller to achieve higher revenue he must take a chance on giving the item to an agent with a lower valuation. Usually this means he must risk not selling the item at all.

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   number of agents have quasilinear utility with private valuations   where the currency   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

 

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

 

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.  

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  

 
 
 

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.

 

교장의 잉여의 평균 왜곡은 0이어야합니다. 일정을 평평하게하려면 역상이 위의 조건을 충족하는   간격에 매핑되도록 x를 찾으십시오.


내용주편집

각주편집

추가 읽기편집

외부 링크편집