게임이론이란 게임을 하는 것을 말합니다!

여기서 게임이란 흔히 알고 있는 비디오 게임, 온라인 게임, 보드게임 등이 아니라 의사결정을 하는 상황을 게임, 정확히는 게임상황이라고 합니다.

게임이론에는 크게 협조적 게임이론과 비협조적 게임이론으로 나눠지는데 이 분야를 처음 접한 사람은 협조와 비협조의 어감 차이 때문에 착각하는 경우가 종종 있습니다.

협조적 게임이론은 참가하는 사람의 인간성이 좋아 다른 사람과 협조를 잘하는 게임이론이고 비협조적 게임이론은 매우 나쁜사람들이 참가하는 게임이론일까요??

게임이론의 전제조건이 하나 있습니다.

바로 참가하는 모든 사람들은 이성적이라는 것이죠 이 이성적이라는 것은 착하고 나쁘고를 떠나서 항상 합리적인 판단만한다는 것입니다. 

그렇다면 협조적과 비협조적이라는 것은 무엇일까요??

협조적 게임이론은 사람들이 강제가 아닌 자기의지로 구속력 있는 계약을 맺을 수 있는 상황을 분석합니다.

여기서 구속력 있는 계약이란 A와 B가 계약을 맺었는데 A가 그 계약을 깨버렸습니다!!

그 때 B는 C, D, E 등등 다른 사람한테 가서 호소하여 계약을 위반한 A를 처벌할 수 있는 게임이론이 바로 협조적 게임이론입니다.

비협조적 게임이론은 게임의 규칙이 허용하는 구속력 있는 계약은 맺을 수 있지만 게임의 규칙에 있지 않는 계약은 맺지 못합니다. 그래서 규칙에 있지 않은 계약을 맺은 경우 A가 계약 위반 했을 때 처벌할 수 없습니다.

먼저 이 포스트에서 주로 다루게 될 내용은 비협조적 게임이론입니다. 

몇가지 게임이론의 용어가 있는데 저기 위에 있는 문명 5 게임의 간디 짤방으로 이야기를 해보겠습니다.

플레이어 : 간디와 문명 5 게임을 하고 있는 여러분

전략집합 : 각 플레이어가 선택할 수 있는 전략 (간디의 경우 (돈받기, 선빵필승) 문명5의 플레이어(돈주기, 선빵필승))

보수 : 특정 전략을 취함으로써 얻을 수 있는 이익

그러면 이러한 게임을 다음과 같이 표로 나타낼 수 있습니다.

만약 자신이 돈을 주게 되고 간디도 순순히 돈을 받게 된다면 자신은 -5원 손해를 입고 간디는 5원을 얻습니다.

만약 자신이 돈을 주게 되는 상황에서 간디가 주먹을 날리면 돈도 뺏기고 치료비 때문에 -15원을 잃습니다 

그리고 간디는 해맑게 돈받을 준비를 하고 있는 상황에서 자신이 선빵을 치면 간디의 소지금을 털어 얻을 수 있고 간디는 치료비와 소지금을 -25원 잃습니다.

마지막으로 둘다 선빵을 때리면 둘다 중환자실에 가서 -20원씩 잃습니다.

이 상황에서는 과연 어떤 선택이 가장 최선일까요??

그런데 게임이론에서 중요한 사실하나 알고 계신가요??

바로 간디는 여러분이 무엇을 선택할지 알고 있습니다!!!

그러면 간디는 독심술사여서 무엇을 선택할지 알고 있는것일까요??

그런데 충격적인건 여러분 또한 간디가 무엇을 선택할지 알고 있습니다!!

어떻게 이런 상황이 가능할까요??

그것은 아까전 이야기했던 참가자는 모두 이성적이다! 라는 가정에 의한 것입니다.

이성적이면 어떻게 되는가? 간디는 여러분이 쓸 전략을 모두 알고 있고 여러분 또한 간디가 쓸 전략을 모두 알고 있습니다. 또한 간디는 여러분이 이성적이라는 것을 알고 있고 여러분 또한 간디가 이성적이라는 것을 알고 있습니다.

이것을 공통 지식(Common knowledge)라고 합니다.

그러면 서로 이성적인 것을 알고 이성에 의한 로지컬 띵킹으로 모든 전략에서 가장 자신의 이익이 최대화 되는 쪽으로 선택하겠죠?

위의 표를 다시 가져와 봅시다. 

이 행렬을 보수행렬이라고 하며 각 선택한 전략에 따른 이익(보수)를 보여주고 있습니다.

그러면 과연 이성적인 여러분과 간디는 어떤 전략을 취하게 될까요?

둘다 선빵 때리는것은 손해가 크니까 안하겠죠?

자 로지컬 띵킹을 해봅시다

여러분이 돈주기 전략을 택한다면 간디의 전략 돈받기를 할시 -5 , 선빵을 할 시 -15 해서 총 -20의 손해를 봅니다.

똑같이 여러분이 선빵 전략을 택한다면 간디의 전략 돈받기를 할 시 5, 선빵을 할 시 -20을해서 총 -15의 손해를 보는군요. 

따라서 여러분은 손해가 적은 선빵전략을 택하게 됩니다.

간디도 마찬가지입니다.

간디가 돈받기 전략을 택한다면 여러분이 전략 돈주기를 할시 5 , 선빵을 할 시 -25 해서 총 -20의 손해를 봅니다. 

마지막으로 간디가 선빵 전략을 택한다면 여러분이 전략 돈주기를 할시 5 , 선빵을 할 시 -20 해서 총 -15의 손해를 봅니다.

따라서 간디도 선빵전략을 택하게 되죠

이렇게 다른 전략에 비해서 가장 높은 보수를 보장하는 전략을 강우월전략이라고 합니다.

근대 어라??? 둘다 선빵을 때리는 건 손해가 극심한데 이성적으로 생각을 해도 결국 둘다 선빵을 때렸습니다.

이러한 상황을 죄수의 딜레마라고 합니다.

 이런 상황도 생각해봅시다. 

대기업 A와 중소기업 B가 다음과 같은 계약 상황에 놓여있다고 해봅시다.

중소기업의 파기와 합병 선택에 대해서 대기업은 거절이 받아들임 보다더 큰 이득을 줍니다

그리고 대기업 입장에서는 중소기업의 협력에 대해서 동일한 이득(10)을 얻을 수 있습니다.

그러면 대기업은 어찌되건 거절하는게 받아들이는 전략보다 이득이므로 거절할 준비를 합니다.

그러면 자동적으로 중소기업은 파기(1)를 선택하겠죠

그러면 둘다 (1, 1)의 이득을 얻습니다.

그런데 대기업이 "난 큰게 좋아" 하면서 받아들임을 선택한다고 중소기업에게 문서를 보내면 중소기업은 얼쑤 좋다! 하면서 협력을 선택하여 최종적으로는 (10, 2)를 얻게 됩니다.

이렇게 중소기업과 대기업 모두 중간의 (10,0)과 (10,2)에 관한 이득이 가장 큰 것을 알고 있으면서도 실제 전략은 이성에 의하여 대기업은 거절을하고 중소기업은 파기를 하게 됩니다. 이러한 대기업의 거절함 전략을 약우월전략이라고 합니다. 

이렇듯 약 우월전략에서는 협상이나 여러 변수에 의하여 항상 강우월전략처럼 가장 이득이 큰 전략을 택한다는 보장이 없습니다.

그런데 게임이론에서는 강우월전략이나 약우월전략이 없는 경우도 있습니다.

이럴 때는 어떻게 선택해야될까요?? 그냥 정신줄 놓고 찍신 강림하면 될까요?

흠.. ? 위 동영상에 내쉬균형의 대한 내용도 담고 있네요

근대 너무 간략하게 넘어가네요 그럼 다른 포스트에서 내쉬균형이라는 주제로 찾아오겠습니다.

비선형계획법은 목적함수나 제약조건을 선형으로 나타낼 수 없는 것을 말합니다.

선형계획법에선 심플렉스라는 강력한 방법을 이용해서 풀었습니다 그리고 정수계획법에서는 단체법은 쓸 수 없었으나 제약 완화를 통해서 다시 선형계획법으로 만들어 심플렉스를 적용하거나 특수한 기법을 통해 심플렉스를 적용하여 빠르게 정수해를 구할 수 있었죠.

그러나 비선형계획법에서는 이 좋은 심플렉스를 사용하지 못합니다.

예를들어 초밥먹은 갯수에 따라서 만족도가 위와 같다고 합시다

그러면 저 그래프가 최대화가 될 때 돈도 아끼고 만족도도 챙기고 일석이조겠죠??

비용은 한정되어 있는데 얼마나 초밥을 먹어야할까요?

여러가지 제약조건이 걸려 있는 상황에서는 저런 간단한 곡선조차 문제를 매우 풀지 못하게 만듭니다.

선형계획법에서는 제약조건이 많이 걸려있어도 연산 난이도만 올라가지 문제를 못 건드리는 수준까지는 아니였거든요

다른 예로 양에 따른 가격의 감소 문제도 비선형입니다.

(위 그래프 공유합니다 : www.geogebra.org/calculator/ftw7kytb)

만약 선박에 싣은 물건의 총량에 따라 운송비가 할인되면(규모의 경제) 싣는 량에 비래해서 총 비용은 위 그래프와 같습니다. 여기서는 싣는 량에 따라 3단계로 구분하였습니다.

1단계는 싣는량에 비례해서 5원

2단계는 싣는량에 비례해서 2원

3단계는 싣는량에 비례해서 0.5원

이것을 어떻게 풀면 최적으로 선박에 싣을 수 있는 량이나 비용을 구할 수 있을까요?

위의 그래프 개형을 보면 쉽게 예측은 가능하지만 이 또한 여러 제약조건이 덕지덕지 붙기 시작하면 답이 없어집니다.

예를 들어볼까요?

5개의 품목이 있는데 각각의 무게와 이득은 다음과 같습니다.

A = 10      2

B = 20      2.1

C = 25     1.8

D = 30     4

E = 35      3

(단위 Kg)

이것을 선박에 싣는다고 할 때 총 용량은 50Ton 까지 싣을 수 있으면 각각의 물건을 몇개 싣는게 가장 이득이 클까요?

목적은 이득을 가장 최대화하는 것.. 그러면 목적함수는 이렇게 나타낼 수 있겠네요

MAX : 2A+2.1B+1.8C+4D+3E - 운반비용 함수(A+B+C+D+E)

s.t.   : 10A+20B+25C+ 30D + 35E <=50000

흠 선형계획법으로 어떻게 풀지 감이 안잡히네요

그러면 한가지 생각을 해봅시다. 예로부터 복잡한 문제들의 해법을 구하기 위해서 먼저 시행해왔던 기본적인 규칙이 있습니다.

바로 규칙없이 그냥 심플하게 단순한것부터 보는 것입니다.

비선형계획법의 가장 단순한 영역은 목적함수만 생각할 때이며 이것을 제약조건이 없는 최적화라고 합니다.

위에서 다시 한계효용 곡선을 가져왔습니다.

목적함수만 두고 볼때 가장 이득을 볼 수 있는 지점은 명확합니다.

바로 그래프가 오목하게 올라와 있는 부분이죠

이처럼 볼록하거나 오목한 함수는 최대값과 최소값을 찾기가 쉽습니다

정확히는 지역 최소값이나 지역 최대값이 전역 최소값과 전역 최대값입니다.

아하 그러면 오목하거나 볼록한 함수는 공략할만하다는 것을 알았습니다.

이러한 것을 볼록 집합(혹은 오목 집합)이라고 합니다.

그런데 이런 말이 나올 수가 있습니다. "볼록집합만 가지고 뭘할 수 있겠어?? 그냥 진짜 특수한 경우만 쓸 수 있는게 아니야??"라고요

맞는 말이긴 합니다만 아래 예제를 봅시다

y=x는 실수 전체에서 오목집합입니다

이 y=sinx 그래프는 오목집합이 아닙니다.

그런데 정의역을 0~PI(3.14)까지로 줄이면

이 함수는 오목집합이 됩니다.

거기다 0~PI/2까지로 정의역을 줄여도 오목함수가 됩니다.

이제 이해가 되나요??

원래 목적함수가 오목집합이 아니더라도 제약조건에 의하여 오목집합이 될 수 있고 또 그게 아니라면 몇가지 조건을 완화하거나 추가함으로 오목집합으로 만들면되기 때문에 중요한 것입니다.

거기다 지금은 제약조건은 고려 안한다고 했죠?

위에서 설명을 명제으로 쓰면 다음과 같습니다.

먼저 지역 최대값을 만족하는 조건을 정의하면

그리고 지역 최대값이 전역 최대값으로 갈 수 있는 조건을 따져봅시다.

여기서 엄격한 오목함수라는 말이 나왔는데 자세한것은 책을 보시는게 좋고 일단 그냥 y=x는 엄격한 오목함수가 아니고 그냥 오목함수라는 것입니다.

이제 이 오목함수라는 개념을 적용해서 해를 구할 수 있습니다.

어떻게 구하냐고요?

생각해봅시다 오목집합의 경우는 위 조건에 의해서 몇가지 사실과 미적분학에서 기초지식 그리고 저희가 알고 있는 몇가지 상식만 가지고 있으면 어떻게 구하는지 이해가 가능합니다.

사실1 - 함수 F(x)의 경우 오목집합이면 지역 최대값이 전역최대값을 만족한다

사실2 - F(x)의 경우 미분한 그래프에서는 양의 기울기를 가지다 최대값에서 0을 찍고 음의 기울기를 가진다.

사실3 - 오목집합 혹은 볼록집합인 경우는 해가 양수가 나오는 구간과 음수가 나오는 구간이 있다.

사실4 - 중간값 정리에 의하여 양수가 나오는 구간과 음수가 나오는 구간 사이에 F'(x)의 해가 존재한다!!!

      -> 따라서 이 구간을 잘 살펴서 좁히면 F'(x)의 해 지점인 c를 찾을 수 있고 결국 최적화를 만족하는 곳은 c라는 것을 알 수 있습니다. 

이 방법을 바로 이분법(bisection method)라고 합니다.

위키피디아에서 사진을 퍼왔습니다.

이렇게 보면 함수 F(x)가 0이 되는 지점을 찾기 위해서 구간을 정해두고 계속 계산을 하여 중간값 정리를 응용하여

F(b)<0를 만족하는 것을 확인하고 있습니다.

물론 완전한 해를 보장하지는 못하지만 어느정도 구간은 추정할 수 있죠 마치 통계학에서 말하는 구간추청처럼 말이죠

이제 예제를 보면서 하는 방법을 알아봅시다.

일단 몇가지 정의를 해야할 변수가 있습니다.

마지막에 저만의 언어를 넣었습니다. 일일히 수식 입력하기 귀찮아서 제가 "x바"라고 하면 위에서 본 표현을 떠올려주시면 되겠습니다.

그러면 절차를 간단하게 소개를 해보면 오목집합인 경우

그러면 가장 먼저 해야될 일은 과연 위의 1.일까요?

흠.. 가장 먼저 해야될 일은 오목함수라는 것을 보이는 거겠죠?

이계도함수를 구해보면 -12(3x^2 + 5x^4) 가 되는군요

x가 실수 어떤 값을 넣어도 저 함수는 항상 음수값를 가지고 x에 0을 넣으면 함수 값은 0이 되니 오목함수라고 할 수 있습니다.

그 다음 대강 지점을 구해보죠

일단 원래 함수의 한 번 미분한 함수

12(1-x^3 -x^5)에서 x에다 간단하게 0을 넣어봅시다

그러면 -12가 나오네요

그리고  1을 넣으면 음수 나올거같은데...

-12정도 나오네요

그러면 0과 1 사이에 중간값정리의 의하여 해가 존재하는 건 확실합니다.

다음 0과 1 사이값인 0.5를 생각해봅시다.

0.5에서 기울기 값은 10.125가 나옵니다.

이 값은 0 이상의 양수이기 때문에 다시 이것을 x 언더로 둡시다.

그리고 또 사이의 값인 0.75를 구하고

다시 구해보면 4.0xxxx 정도가 나오고 다시 x 언더에 넣고 ... 무한 반복합니다. 원하는 만큼의 정밀도가 나올때까지.......

표로 표현하면 다음과 같습니다.

그러면 이제 어떻게 비선형에서 오목 또는 볼록집합일 경우 푸는 방법은 알았습니다.

하지만 아직 못한 이야기도 있습니다. 바로 변수가 여러개일 경우와 (x1, x2 ... ) 제약조건이 걸려있는 경우에 관한 것이죠

비선형계획법이 상당히 난해하다보니 너무 길어지네요 다른 포스트에서 이 다른 경우에 관해 다루겠습니다.

TTT란 특정 시점까지 시험한 총 시간을 뜻합니다.

예를들어 다음과 같이 자동차에 대한 고장 시점 자료가 있다고 합시다.

1---------X

2---------------------X

3--------------X

4------------------------------------------X

5------------------------------X

----------------------------------------------->시간

자동차 1이 고장날 시점이 5년이라고 한다면 이 때 TTT를 구해봅시다

5년 전까지는 5대 모두 잘 작동하고 있었으므로 TTT는 5*5=25가 됩니다.

자동차 2가 6.5년에 고장 났다고 한다면 이 때 TTT는 그 전까지 4대가 작동하고 있었으므로 다음과 같이 계산됩니다.

TTT(자동차 1 고장시점) + (6.5-5) *4 = 31

그러면 TTT가 왜 필요할까요?

TTT가 필요한 이유는 비모수적 방법 중 고장 분포를 잘 나타내는 방법중 하나이기 때문입니다.

예를들어 어떤 나라에 바이러스가 퍼져서 사망자가 늘어나고 있다고 해봅시다.

그러면 그 사망자에 대한 통계값이 나올텐데 어떤 분포로 나오는지 모르니 일단 데이터만 가지고 분석해보려고 합니다.

이 방법을 전문용어로 비모수적 방법이라고 합니다.

TTT는 이 비모수적 방법중 하나로 유용하게 쓰이기 때문에 사용하는데 보통 그냥 저 데이터만 사용하기 보다는 그래프로 나타내어 사용합니다. 이것을 TTT plot이라고 합니다.

일단 그래프로 나타내기 위해서 (x, y)의 값을 알아야하는데 좌표 수식 한개를 먼저 봅시다.

이것을 1번부품부터 해서 n번 부품까지 값을 차례대로 구해서 점을 찍는거죠

저 수식을 해석해보면 다음과 같습니다.

i/n 은 고장난 부품이 차지하는 비율입니다.

그리고 최종적으로는 n/n으록 가기 때문에 1이 됩니다.

TTT(i 부품 고장 시점 ) / TTT(모든 부품 고장 시점)는 전체 TTT시간(모든 부품이 고장나기까지 걸린 개별시간을 전부 합친값) 에서 특정 i부품까지 고장난 시간이 차지하는 비율입니다.

결론적으로 저 수식은 특정 부품이 파괴될 때까지 전체 부품과 시간에 대한 비율을 나타냅니다.

이제 실제 그래프로 나타내고 해석을 해봅시다.

위에서 언급한 자동차가 출고 후 고장될 때까지 걸린 개월 수가 다음과 같다고 합시다.

6.3 11.0 21.5 48.4 90.1 120.2 163.0 182.5 198.0 219.0

이때 TTT 그래프를 그리기 위해서 일단 고장 시점 막대 그래프를 한번 그려봅시다.

총 10개의 부품이 있고 최종 고장까지 걸린 개월 수는 219개월입니다.

이제 각 TTT지수를 구해봅시다.

이때 TTT plot을 그리면 다음과 같습니다.

이렇게 처음엔 고장률이 단위 TTT비율보다 부품의 고장개수 비율(i/n)이 많은 것을 알 수 있습니다.

좀더 알기 쉽게 하기 위해서 다음과 같이 수정해봅시다.

좀더 해석하기 쉽게 하기 위해서 y=x를 추가했습니다.

이제 확실히 보입니다. 

그래프 초반에는 단위 TTT비율보다 부품의 고장개수 비율(i/n) 이 더 많기 때문에 기울기가 작다가 점점 1:1 비율이 되는 순간 y=x의 기울기를 어느정도 유지하다 후반에는 TTT비율이 상승함으로 끝이납니다.

저 그래프의 고장률을 해석하면 초기에는 고장률이 점점 감소하다가 중반에는 서로 일정한 비율을 유지하고 종국에는 고장률이 다시 증가합니다.

이떄 고장률이 시간에 따라 증가하는 것을 증가형(IFR)이라 하고 i/n < TTT비율이 성립합니다.

다르게 시간에 따라 감소하는 것을 감소형(DER)라 하고 i/n > TTT비율이 성립합니다.