분산 알고리즘 메커니즘 설계

Distributed algorithmic mechanism design

분산 알고리즘 메커니즘 설계(DAMD)는 알고리즘 메커니즘 설계의 확장이다.

DAMD는 알고리즘이 중앙 기관이 아닌 분산 방식으로 계산되기 때문에 알고리즘 메커니즘 설계와 다르다. 이것은 네트워크 내의 모든 에이전트들이 부담을 공유하기 때문에 계산 시간을 크게 향상시킨다.

DAMD의 한 가지 주요 장애물은 에이전트들이 주어진 시나리오와 관련된 실제 비용이나 선호도를 밝히도록 하는 것이다. 종종 이러한 요원들은 자신의 효용성을 향상시키기 위해 거짓말을 하곤 한다. DAMD는 합리적인 참여자들이 메시지 경로와 메커니즘 계산을 통제하는 순종적인 네트워킹과 메커니즘 인프라를 더 이상 가정할 수 없기 때문에 새로운 도전으로 가득 차 있다.

게임 이론 모형

게임 이론과 분산 컴퓨팅은 둘 다 많은 에이전트들이 서로 다른 목표를 추구할 수 있는 시스템을 다룬다. 하지만 그들은 서로 다른 초점을 가지고 있다. 예를 들어 분산 컴퓨팅의 관심사 중 하나는 결함이 있는 에이전트와 에이전트가 동시에 작업을 수행하는 것을 용인하는 알고리즘의 정확성을 증명하는 것이다. 반면에, 게임 이론에서는 우리를 시스템의 균형으로 이끄는 전략을 고안하는 것에 초점을 맞추고 있다. [1]

나시 평형

나시 평형은 게임 이론에서 가장 흔히 사용되는 평형 개념이다. 그러나 나시 평형은 잘못되거나 예상치 못한 행동을 다루지 않는다. 나시 평형에 도달하는 프로토콜은 이성적인 대리인의 면전에서 정확하게 실행이 보장되며, 어떤 대리인도 프로토콜에서 이탈하여 그 효용성을 향상시킬 수 없다.[2]

솔루션 선호도

AMD에 있는 것처럼 신뢰할 수 있는 센터가 없다. 따라서, 메커니즘은 에이전트 스스로 실행되어야 한다. 솔루션 선호도 가정은 각 대리점이 어떤 결과보다 결과를 전혀 선호하지 않는 것을 요구한다. 따라서 대리인은 결과에 대해 동의하지 않거나 알고리즘을 실패하게 할 동기가 없다. 즉, 아프크 외 연구원의 말처럼, "알고리즘이 실패하면 에이전트를 얻을 수 없다"[3]는 것이다. 결과적으로, 에이전트는 선호도가 있지만 알고리즘을 실패할 동기가 없다.

진실성

메커니즘은 에이전트가 자신의 또는 다른 에이전트의 가치에 대해 거짓말을 함으로써 얻는 것이 아무것도 없다면 진실된 것으로 간주된다. 좋은 예로는 네트워크 내의 계산 서버를 선택하는 리더 선거 알고리즘이 있다. 알고리즘은 에이전트들이 그들의 총 계산력을 서로 전송해야 한다고 명시하고, 그 후에 가장 강력한 에이전트를 작업을 완료하는 리더로 선택한다. 이 알고리즘에서 에이전트는 로컬 작업을 완료하는 데 필요한 전력을 줄일 수 있는 CPU 집약적인 작업을 처리할 수 있는 위험에 처할 수 있기 때문에 실제 계산 능력에 대해 거짓말을 할 수 있다. 이는 각 대리인의 기존 데이터와 입력에 대한 사전 지식 없이 각 대리인이 요청에 진실하게 응답하도록 하는 진실된 메커니즘의 도움으로 극복할 수 있다.[4]

게임 이론에서 잘 알려진 진실된 메커니즘은 비크리 경매다.

일반적인 분산 컴퓨팅 문제

리더 선출(완전히 연결된 네트워크, 동기식 사례)

리더 선거는 분산 컴퓨팅의 근본적인 문제로서 이 문제를 해결하기 위한 수많은 프로토콜이 있다. 시스템 에이전트는 합리적인 것으로 가정되며, 따라서 리더를 보유하지 않는 것보다 더 선호한다. 대리인은 누가 지도자가 되는가에 대해서도 다른 선호를 가질 수 있다(대리인은 자신이 지도자가 되는 것을 선호할 수 있다). 표준 프로토콜은 시스템 에이전트의 가장 낮거나 가장 높은 ID에 기초하여 리더를 선택할 수 있다. 그러나, 에이전트들은 그들의 효용성을 향상시키기 위해 그들의 ID에 대해 거짓말을 할 동기를 가지고 있기 때문에, 그러한 프로토콜들은 알고리즘 메커니즘 설계의 설정에서 쓸모 없게 된다.
이성적 대리인이 존재하는 지도자 선거를 위한 프로토콜이 Ittai 외 에 의해 도입되었다.

  • 1라운드에서 각 요원은 모두에게 신분증을 보낸다.
  • 2라운드에서 I 요원은 j 요원이 받은 ID 세트를 서로 보낸다(자신의 ID도 포함해서. 에이전트 i가 수신한 세트가 모두 동일하지 않거나 일부 에이전트로부터 ID를 수신하지 않으면 출력값을 Null로 설정하면 리더 선택이 실패한다. 그렇지 않으면 n을 ID 집합의 카디널리티로 한다.
  • 에이전트 i는 {0, ..., n-1}에서 임의의 번호 N을i 선택하여 다른 모든 에이전트로 전송한다.
  • 그런 다음 각 에이전트 i는 σn
    i=1     Ni(mod n)을 계산한 다음 집합에서 N번째 가장 높은 ID를 가진 에이전트를 리더로 삼는다. (일부 에이전트 j가 i를 임의의 번호로 보내지 않으면, 출력을 Null로 설정한다.)

이 프로토콜은 균형에 도달하는 동안 리더를 올바르게 선택하며, 어떤 에이전트도 그것의 입력에 대해 거짓말을 함으로써 이익을 얻을 수 없기 때문에 진실하다.[5]

참고 항목

참조

  1. ^ Halpern, Joseph Y. (2008). "Computer science and game theory: A brief survey". The New Palgrave Dictionary of Economics.
  2. ^ Martin, Osborne; Rubinstein, Ariel (1994). A course in game theory. MIT press.
  3. ^ Afek, Yehuda; Ginzberg, Yehonatan; Feibish, Shir Landau; Sulamy, Moshe (2014). "Distributed computing building blocks for rational agents". PODC '14 Proceedings of the 2014 ACM symposium on Principles of distributed computing.
  4. ^ Shneidman, Jeffrey; Parkes, David (2004). "Specification faithfulness in networks with rational nodes". twenty-third annual ACM symposium on principles of distributed computing: PODC.
  5. ^ Abraham, Ittai; Dolev, Danny (2013). "Distributed Protocols for Leader Election: a Game-Theoretic Perspective". DISC: 61–75.

외부 링크

  • [1] 분산 알고리즘 메커니즘 설계: 최근 결과 및 향후 방향
  • [2] 분산 알고리즘 메커니즘 설계 및 네트워크 보안
  • [3] Vickrey 옥션을 이용한 이기종 모바일 애드혹 네트워크의 서비스 할당