제로섬 게임으로 랜덤화된 알고리즘

이 글에는 출처가 없다 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "제로섬 게임으로서의 임의 알고리즘" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

무작위화된 알고리즘은 어느 정도의 무작위성을 그들의 논리의 일부로 채택하는 알고리즘이다.이러한 알고리즘은 결정적으로 해결하기 어려운 문제에 대해 좋은 평균 사례 결과(복잡성)를 제공하거나 최악의 경우 복잡성을 보이는 데 사용될 수 있다.알고리즘 게임 이론적 접근법은 평균 사례에서 무작위화된 알고리즘이 결정론적 알고리즘보다 더 잘 작동하는 이유를 설명하는데 도움이 될 수 있다.

게임 공식화

전략이 결정론적인 알고리즘인 A 플레이어와 A 알고리즘의 입력인 B 플레이어 사이의 제로섬 게임을 생각해 보자.전략 프로파일의 비용은 B가 선택한 입력에서 A가 선택한 알고리즘의 실행 시간이다.따라서 A선수는 비용을 최소화하려고 하고, B선수는 비용을 최대화하려고 한다.순수 전략의 세계에서, A가 선택하는 모든 알고리즘에 대해, B는 가장 비용이 많이 드는 입력을 선택할 수 있다 – 이는 최악의 시나리오로, 표준 복잡도 분석을 사용하여 찾을 수 있다.

그러나 현실 세계에서 입력은 일반적으로 '악의 상대'에 의해 선택되지 않고 입력에 대한 어떤 분포로부터 온다.이런 경우가 있기 때문에 알고리즘도 어느 정도 배포에서 끌어낼 수 있도록 허용한다면, 우리는 게임을 혼합된 전략을 허용하는 것으로 볼 수도 있다.즉, 각 플레이어가 전략보다 분배를 선택한다.

분석

게임에 혼합된 전략을 통합하면 폰 노이만의 미니맥스 정리를 사용할 수 있다.

${\displaystyle \min _{R}\max _{D}T(A,D)=\max _{D}\min _{A}T(A,D)\,}$

여기서 R은 알고리즘에 대한 분포, D는 입력에 대한 분포, A는 단일 결정론적 알고리즘, T(A, D)는 입력 D에 대한 알고리즘의 평균 실행 시간이다.좀 더 구체적으로:

${\displaystyle T(A,D)=\,{\underset {x\sim D}{\operatorname {E}}}}}}}}[T(A,X)]].\,}$

알고리즘 집합을 특정 패밀리로 제한할 경우(예: 빠른 정렬 알고리즘의 피벗에 대한 모든 결정론적 선택) R에서 알고리즘 A를 선택하는 것은 무작위화된 알고리즘을 실행하는 것과 같다(예를 들어, 빠른 정렬을 실행하고 각 단계에서 피벗을 랜덤하게 선택하는 것).

이는 주어진 문제를 해결하기 위한 임의화된 알고리즘의 예상 비용이 해당 알고리즘에 대한 최악의 경우 입력에 대한 최악의 무작위 확률 분포에 대한 예상 비용보다 나을 수 없다는 야오 원리에 대한 통찰력을 제공한다.분배