인공지능의 게임 이론 (game theory)

수강일시: 2021.01.21

출처: kmooc SNU048

 

www.kmooc.kr/courses/course-v1:SNUk+SNU048_011k+2020_T2

로그인 | K-MOOC

이번 강의 내용은 게임이론에 관한 것이다.

게임이론에서의 게임이란 2명 혹은 그 이상의 의사결정자가 어떠한 행동(action)을 통해 각자의 이익을 최대화(혹은 손실을 최소화)하는 과정을 말한다.

 

따라서 게임이론에서 가정은 다음 세가지 이다.

 

1.모든 player는 이익을 최대화하려고 한다.

2.모든 player는 이성적이다.

3.모든 player가 이성적이라는것을 서로가 알고 있다.

 

가장 유명한 게임이론중 하나인 죄수의 딜레마를 보면 다음과 같다.

그리고 이를 행렬 형태로 일반화시켜 보도록 하자.

N은 총 player의 숫자이고 A는 각 action들의 집합이다.

따라서 Ai는 i라는 사람이 가능한 action들이다. u는 정의역이 A이고 치역은 실수인 효용함수이다.

 

따라서 왼쪽의 죄수의 딜레마를 게임이론의 일반적인형태로 나타내면 다음과 같다.

다음으로는 게임이론의 부분집합인 zero sum game인데 그중에서도 가위바위보를 보도록 하겠다.

당연히 죄수의 딜레마는 제로썸 게임이 아니다.

 

 

 

support의 개념과 pure/mixed stage의 개념을 살펴보도록 하겠다.

support는 action의 확률이 0보다 큰 구간을 말한다.

전략이 pure하다는것은 모든 player가 동일한 전략을 사용한다는것이고

mixed 되어있다는 것은 모든 player가 전략을 선택함에 있어 항상 동일하지는 않다는(혹은 randomness 가 들어있다는) 뜻이다.

 

다음으로 내쉬균형은 이러한 게임이론에서 각자의 optimal한 선택에 있어 평형을 이룬 상태를 뜻한다.

 

 

2player (zero-sum혹은 sum-equal)  pure strategy game에서의 내쉬균형을 찾는 방법중 하나인 minmax(maxmin)방식에 대해 알아보고자 한다.

행렬이 player1의 효용에 관해 주어졌을때 player1의 선택은 최솟값들의 최대값이 된다. player2의 경우 반대로 최댓값들의 최소(행렬이 player1에 관해 주어졌으므로)가 된다.

예를들면 위와같은 상황에서 1행2열(player1의 action1 과 player2의 action2)가 내쉬균형이 된다.

 

2player인 상태에 대해서만 살펴봤는데 2인이상의 game의 경우 훨씬 복잡해지고 이러한 일반화된 방식이 아니라 개별 상황에 맞는 방식으로 접근해야 균형을 찾을 수 있다.

non-zero sum game에서도 general solution이 없으므로 상황에 맞는 판단을 진행해야 한다.

 

 

이외의 다양한 게임이론들을 간단하게 소개하고 넘어가겠다.