인센티브 호환성

Incentive compatibility

모든 참가자가 자신의 진정한 선호에 따라 행동하는 것만으로 자신에게 최상의 결과를 얻을 수 있다면, 메커니즘은 인센티브 호환(IC)이라고 불린다.[1]: 225 [2]

인센티브 호환성의 몇 가지 다른 정도가 있다.[3]

  • 더 강한 정도는 지배적인 전략 인센티브-호환성(DSIC)이다.[1]: 415 그것은 진리를 말하는 것이 약하게 지배하는 전략이라는 것을 의미한다. 즉, 다른 사람들이 무엇을 하든 상관없이, 여러분은 진리를 지킴으로써 최선을 다하거나 최소한 더 나빠지지 않게 된다. DSIC 메커니즘에서 전략적 고려는 어떤 에이전트도 진실보다 나은 결과를 달성하도록 도울 수 없다. 따라서 그러한 메커니즘을 전략적으로[1]: 244, 752 입증하거나 진실하다고 부르기도 한다.[1]: 415 (전략적 검증 참고)
  • BNIC(Bayesian-Nash 인센티브 호환성)가 약하다.[1]: 416 참가자 모두가 진정한 선호를 드러내는 베이시안 나시 평형이 있다는 뜻이다. 즉, 다른 모든 사람들이 진실하게 행동한다면, 그것은 또한 당신이 진실하게 행동하는 것이 최선이거나 적어도 더 나쁘지는 않다.[1]: 234

모든 DSIC 메커니즘도 BNIC이지만 DSIC 메커니즘이 존재하지 않더라도 BNIC 메커니즘이 존재할 수 있다.

DSIC 메커니즘의 대표적인 예로는 두 가지 대안 중 다수결과 2차 가격 경매가 있다.

DSIC가 아닌 메커니즘의 대표적인 예는 3개 이상의 대안들과 1차 가격 경매 사이의 복수 투표다.

무작위화된 메커니즘으로

무작위화된 메커니즘은 결정론적 메커니즘에 대한 확률분포다. 무작위화된 메커니즘의 인센티브 호환성을 정의하는 두 가지 방법이 있다.[1]: 231–232

  • 더 강력한 정의는: 양의 확률을 가지고 선택된 모든 메커니즘이 인센티브 호환성이 있는 경우(예: 진실 확인이 메커니즘의 동전과 무관하게 에이전트에게 최적의 값을 제공하는 경우) 무작위화된 메커니즘은 보편적으로 인센트럴 호환성이 있다.
  • 더 약한 정의는: 무작위화된 메커니즘은 기대치에 의해 유도된 게임이 인센티브와 호환될 경우(예: 진실 확인이 에이전트에 최적의 기대 가치를 제공하는 경우) 인센티브와 호환성이 있다는 것이다.

계시의 원칙

주요 기사: 계시의 원리

계시의 원칙은 인센티브 호환성의 두 가지 맛에 해당하는 두 가지 변형으로 나타난다.

  • 지배 전략 계시 원칙은 지배 전략에서 구현될 수 있는 모든 사회 선택 기능은 DSIC 메커니즘에 의해 구현될 수 있다고 말한다.
  • 베이시안-나시 폭로 원칙은 베이시안-나시 평형(베이시안 게임, 즉 불완전한 정보의 게임)에서 구현될 수 있는 모든 사회 선택 기능은 BNIC 메커니즘에 의해 구현될 수 있다고 말한다.

참고 항목

참조

  1. ^ Jump up to: a b c d e f g Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
  2. ^ "Incentive compatibility game theory". Encyclopedia Britannica. Retrieved 2020-05-25.
  3. ^ Jackson, Matthew (December 8, 2003). "Mechanism Theory" (PDF). Optimization and Operations Research.