알고리즘 게임 이론

Algorithmic game theory

알고리즘 게임 이론(AGT)은 게임 이론과 컴퓨터 과학이 교차하는 영역으로, 전략적 환경에서 알고리즘을 이해하고 설계하는 것을 목적으로 한다.

일반적으로 알고리즘 게임 이론 문제에서 주어진 알고리즘에 대한 입력은 출력에 개인적인 관심이 있는 많은 플레이어들에게 분배된다. 그러한 상황에서 대리인은 자신의 개인적인 관심 때문에 그 의견을 진실로 보고하지 않을 수 있다. 우리는 알고리즘 게임 이론을 두 가지 관점에서 볼 수 있다.

  • 분석: 현재 구현된 알고리즘을 고려하여 게임 이론 도구를 사용하여 분석하십시오(예: Nash 평형 평형, 무정부 상태 가격 및 최상의 대응 역학)
  • 디자인: 좋은 게임 이론적 특성과 알고리즘적 특성을 모두 갖춘 디자인 게임. 이 영역을 알고리즘 메커니즘 설계라고 한다.

설계자는 고전 알고리즘 설계의 일반적인 요건(예: 다항 시간 실행 시간, 좋은 근사 비율)에 더하여 인센티브 제약에 대해서도 주의해야 한다.

역사

Nisan-Ronen: 알고리즘을 연구하는 새로운 틀

1999년 니산과 로넨의 세미날짜 논문이 이기적(전략적) 사용자를 위한 알고리즘 설계에 이론 컴퓨터 과학계의 관심을 끌었다. 그들은 추상적으로 다음과 같이 주장한다.

참가자가 알고리즘을 따르는 것으로 가정할 수 없고 오히려 그들 자신의 이익을 따르는 것으로 가정할 수 없는 분산된 환경에서 알고리즘 문제를 고려한다. 에이전트라고 불리는 그러한 참여자들이 알고리즘을 조작할 수 있기 때문에, 알고리즘 설계자는 에이전트의 이익이 올바르게 행동함으로써 가장 잘 수행되도록 사전에 보장해야 한다. 메커니즘 설계 분야의 개념에 따라, 우리는 그러한 알고리즘을 연구하기 위한 프레임워크를 제안한다. 이 모델에서 알고리즘 솔루션은 참가자에 대한 지급으로 장식되며 메커니즘이라고 불린다. 모든 참가자가 알고리즘 설계자가 원하는 대로 행동하도록 동기를 부여하기 위해 지급액을 신중하게 선택해야 한다. 우리는 메커니즘 설계의 표준 도구를 알고리즘 문제, 특히 최단 경로 문제에 적용한다.

본 논문은 알고리즘 메커니즘 디자인이라는 용어를 만들어 냈으며, 2012년 괴델상 위원회로부터 "알고리즘 게임 이론의 성장 기반을 마련하는 3개 논문" 중 하나로 인정받았다.[2]

무정부상태의 가격

주요기사 : 무정부상태의 가격

다른 두 논문은 알고리즘 게임 이론에 대한 근본적인 공헌을 위해 2012 괴델 상에서 인용한 것으로 '무정부 상태의 가격'이라는 개념을 도입, 개발했다. 쿠투피아스와 파파디미트리오우는 1999년 논문 'Worst-case Equilibria'[3]에서 대리인의 이기적인 행동에 의한 시스템 효율 저하, 즉 최적의 구성에서의 시스템 효율 간 비율과 최악의 내시 평형에서의 효율성에 대한 새로운 대책을 제안했다. (무정부상태의 가격이라는 용어는 불과 몇 년 후에야 나타났다.)[4]

촉매로서의 인터넷

인터넷은 교류와 상업의 기반으로서 그리고 그 자체로 새로운 경제를 창조했다. 인터넷의 계산적 특성은 이 새로운 신흥 경제에서 컴퓨터 도구를 사용할 수 있게 했다. 반면에 인터넷 그 자체는 많은 사람들의 행동의 결과물이다. 이것은 그때까지 유지되었던 계산에 대한 고전적인 '하향식' 접근법에 새로운 것이었다. 그러므로, 게임 이론은 인터넷과 그 안의 상호작용을 인간과 기계적으로 보는 자연스러운 방법이다.

게임 이론은 평형(Nash 평형 등)을 연구한다. 평형상태는 일반적으로 어떤 선수도 전략을 바꿀 동기가 없는 상태로 정의된다. 평형주의는 예를 들어 금융 상호작용과 통신 부하[citation needed] 균형과 같은 인터넷과 관련된 여러 분야에서 발견된다. 게임 이론은 평형을 분석하기 위한 도구를 제공하며, 공통적인 접근법은 '게임 찾기' 즉, 특정 인터넷 상호작용을 게임으로 공식화하고 관련 평형을 도출하는 것이다.

게임 측면에서 문제를 재인용하는 것은 인터넷 기반 상호작용의 분석과 특정 수요를 충족시키기 위한 메커니즘의 구축을 가능하게 한다. 만약 평형증이 존재한다고 증명될 수 있다면, 추가적인 질문에 답해야 한다: 균형은 적당한 시간에 찾을 수 있는가? 이것은 평형성을 찾기 위한 알고리즘의 분석으로 이어진다. 특히 중요한 것은 알고리즘 게임 이론의 많은 문제를 포함하고 있는 PPAD라는 복잡성 등급이다.

연구 분야

알고리즘 메커니즘 설계

주요 기사: 알고리즘 메커니즘 설계

메커니즘 설계는 인센티브 제약 하에서 최적화를 다루는 경제학의 하위 영역이다. 알고리즘 메커니즘 설계는 계산 효율 요건에 따른 경제 시스템의 최적화를 고려한다. 대표적인 연구목표로는 수익 극대화와 사회복지 극대화를 들 수 있다.

평형주의 비효율성

무정부 상태의 가격 개념과 안정성의 가격 개념은 참여자들의 이기적인 행동으로 인한 시스템 성능의 손실을 포착하기 위해 도입되었다. 무정부상태의 가격은 가능한 최적 성능에 비례하여 평형상태에서 시스템의 최악의 경우 성능을 포착한다.[5] 반면에 안정의 가격은 시스템의 최상의 평형상태의 상대적 성능을 포착한다.[6] 이러한 개념은 알고리즘 설계에서 근사비 개념의 반대 개념이다.

평형추구의 복잡성

게임에서 평형의 존재는 전형적으로 비건설적인 고정점 정리를 사용하여 확립된다. 내시 평형을 계산하는 것으로 알려진 효율적인 알고리즘은 없다. 문제는 2인용 게임에서도 PPAD의 복잡성에 대해서는 완전하다.[7] 이와는 대조적으로 상관관계가 있는 평형도는 후회 없는 전략을 통해 학습될 뿐만 아니라 선형 프로그래밍을 사용하여 효율적으로 계산할 수 있다.[8][9]

계산적 사회적 선택

주요 기사: 계산적 사회적 선택

계산적 사회적 선택은 사회적 선택의 계산적 측면, 즉 개별적 대리인의 선호의 집계를 연구한다. 그 예로는 투표 규칙과 연정 구성의 알고리즘과 계산상의 복잡성이 있다.[10]

기타 주제는 다음과 같다.

그리고 그 영역은 다양한 실용적인 용도에 반영된다.[11][12]

저널 및 뉴스레터

  • 경제 및 계산에 관한 ACM 거래
  • SIGEcom Exchange

알고리즘 게임 이론 논문은 GEB와 같은 게임 이론 저널,[15] Economometrica와 같은 이코노믹스 저널, SICOMP와 같은 컴퓨터 사이언스 저널에도 종종 게재된다.[16]

참고 항목

참조

  1. ^ Nisan, Noam; Ronen, Amir (1999), "Algorithmic mechanism design", Proceedings of the 31st ACM Symposium on Theory of Computing (STOC '99), pp. 129–140, doi:10.1145/301250.301287, ISBN 978-1581130676, S2CID 8316937
  2. ^ "ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use" (Press release). New York. Association for Computing Machinery. 2012-05-16. Archived from the original on 2013-07-18. Retrieved 2018-01-08.
  3. ^ Koutsoupias, Elias; Papadimitriou, Christos (May 2009). "Worst-case Equilibria". Computer Science Review. 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003. Archived from the original on 2016-03-13. Retrieved 2018-01-08.
  4. ^ Papadimitriou, Christos (2001), "Algorithms, games, and the Internet", Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC '01), pp. 749–753, CiteSeerX 10.1.1.70.8836, doi:10.1145/380752.380883, ISBN 978-1581133493, S2CID 207594967
  5. ^ Tim Roughgarden (2005). Selfish routing and the price of anarchy. MIT Press. ISBN 0-262-18243-2.
  6. ^ *Anshelevich, Elliot; Dasgupta, Anirban; Kleinberg, Jon; Tardos, Éva; Wexler, Tom; Roughgarden, Tim (2008). "The Price of Stability for Network Design with Fair Cost Allocation". SIAM J. Comput. 38 (4): 1602–1623. doi:10.1137/070680096. S2CID 2839399.
  7. ^ *Chen, Xi; Deng, Xiaotie (2006). Settling the complexity of two-player Nash equilibrium. Proc. 47th Symp. Foundations of Computer Science. pp. 261–271. doi:10.1109/FOCS.2006.69. ECCC TR05-140..
  8. ^ Papadimitriou, Christos H.; Roughgarden, Tim (2008). "Computing correlated equilibria in multi-player games". J. ACM. 55 (3): 14:1–14:29. CiteSeerX 10.1.1.335.2634. doi:10.1145/1379759.1379762. S2CID 53224027.
  9. ^ Foster, Dean P.; Vohra, Rakesh V. (1996). "Calibrated Learning and Correlated Equilibrium". Games and Economic Behavior.
  10. ^ Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia, eds. (2016), Handbook of Computational Social Choice (PDF)
  11. ^ Tim Roughgarden (2016). Twenty lectures on algorithmic game theory. Cambridge University Press. ISBN 9781316624791.
  12. ^ "EC'19 20th ACM Conference on Economics and Computation".
  13. ^ 찻잔
  14. ^ SIGEcom Exchange
  15. ^ Chawla, Shuchi; Fleischer, Lisa; Hartline, Jason; Tim Roughgarden (2015), "Introduction to the Special Issue – Algorithmic Game Theory – STOC/FOCS/SODA 2011", Games and Economic Behavior, 92: 228–231, doi:10.1016/j.geb.2015.02.011
  16. ^ SICOMP

외부 링크

  • gambit.sourceforge.net - 유한한 광범위하고 전략적인 게임의 구축 및 분석을 위한 게임 이론 소프트웨어 및 도구 라이브러리.
  • gamut.stanford.edu - 게임용 알고리즘 테스트용으로 지정된 게임 생성기 제품군.