예제를 포함한 게임 이론. 게임 이론

08.07.2019

인기있는 미국 블로그 Cracked에서.

게임 이론은 최선의 움직임을 만드는 방법을 연구하고 결과적으로 다른 플레이어의 파이 중 일부를 잘라서 최대한 많은 승리 파이를 얻는 방법에 관한 것입니다. 다양한 요소를 분석하고 논리적으로 균형 잡힌 결론을 도출하는 방법을 가르쳐줍니다. 숫자 다음, 알파벳 이전에 공부해야 할 것 같아요. 단순히 너무 많은 사람들이 받아들이기 때문에 중요한 결정, 직관, 비밀 예언, 별의 위치 및 기타 유사한 것들을 기반으로 합니다. 지금까지 게임이론을 철저하게 공부했으니 이제 그 기본에 대해 말씀드리고 싶습니다. 아마도 이것이 추가 될 것입니다 상식당신의 삶에.

1. 죄수의 딜레마

Berto와 Robert는 도난당한 차량을 적절하게 사용하여 탈출하지 못한 후 은행 강도 혐의로 체포되었습니다. 경찰은 그들이 은행을 털었다는 것을 증명할 수 없었지만 도난당한 차에서 그들을 적발했습니다. 그들은 서로 다른 방으로 끌려갔고 각각 공범자를 넘겨주고 10년 동안 감옥에 보내고 스스로 석방되는 거래를 제안 받았습니다. 그러나 둘 다 서로 배반하면 각각 7년의 형을 받게 될 것입니다. 아무도 아무 말도 하지 않으면 둘 다 자동차 절도 혐의로 2년 동안 감옥에 갇히게 됩니다.

Berto가 묵비권을 행사했지만 Robert가 그를 신고하면 Berto는 10년 동안 감옥에 갇히고 Robert는 석방됩니다.

각 죄수는 플레이어이며 모든 사람의 이익은 "공식"(둘 다 얻는 것, 다른 사람이 얻는 것)으로 표현될 수 있습니다. 예를 들어, 내가 당신을 때리면 내 승리 패턴은 다음과 같습니다. 극심한 고통). 각 죄수에게는 두 가지 옵션이 있으므로 결과를 표로 표시할 수 있습니다.

실제 적용: 소시오패스 식별

여기서 우리는 게임 이론의 주요 적용을 볼 수 있습니다: 자기 자신만 생각하는 소시오패스를 식별합니다.진정한 게임 이론은 강력한 분석 도구이며 아마추어주의는 종종 명예가 없는 사람을 표시하는 위험 신호 역할을 합니다. 직관적인 계산을 하는 사람들은 추한 일을 하는 것이 다른 플레이어가 무엇을 하든 징역형이 더 짧아지기 때문에 더 낫다고 믿습니다. 기술적으로 이것은 정확하지만 숫자를 더 높게 설정하는 근시안적인 사람인 경우에만 해당됩니다. 인간의 삶. 금융계에서 게임이론이 인기를 끄는 이유가 바로 이것이다.

죄수의 딜레마의 실제 문제는 데이터를 무시한다는 것입니다.예를 들어, 10년 동안 감옥에 보낸 사람의 친구, 친척, 심지어 채권자와 만날 가능성도 고려하지 않습니다.

가장 나쁜 점은 죄수의 딜레마에 관련된 모든 사람이 마치 들어본 적도 없는 것처럼 행동한다는 것입니다.

그리고 최선의 조치는 침묵을 지키는 것이고, 2년 후에는 좋은 친구일반 돈을 사용합니다.

2. 지배적 전략

이것은 당신의 행동이 주는 상황이다 가장 큰 승리, 상대방의 행동에 관계없이.무슨 일이 일어나더라도 당신은 모든 일을 올바르게 했습니다. 이것이 바로 죄수의 딜레마를 겪는 많은 사람들이 상대방이 무엇을 하든 배신이 '최선의' 결과로 이어진다고 믿는 이유이며, 이 방법에 내재된 현실에 대한 무지가 이를 매우 쉽게 보이게 만듭니다.

우리가 플레이하는 대부분의 게임에는 엄격하게 지배적인 전략이 없습니다. 그렇지 않으면 끔찍할 것이기 때문입니다. 당신이 항상 같은 일을 했다고 상상해 보세요. 가위바위보 게임에는 우세한 전략이 없습니다. 하지만 오븐 장갑을 끼고 바위나 종이만 보여줄 수 있는 사람과 놀고 있다면 종이라는 지배적인 전략을 갖게 될 것입니다. 당신의 종이는 그의 돌을 감싸거나 무승부로 이어질 것이며, 상대가 가위를 보여줄 수 없기 때문에 당신은 질 수 없습니다. 이제 당신은 지배적인 전략을 갖고 있으므로 다른 것을 시도하는 것은 바보일 것입니다.

3. 남녀싸움

게임은 엄격하게 지배적인 전략이 없을 때 더 흥미로워집니다. 예를 들어, 남녀 싸움. 안잘리와 보리슬라프는 데이트를 하지만 발레와 복싱 중 하나를 선택할 수 없다. Anjali는 누군가의 머리를 박살내기 위해 돈을 지불했다는 이유만으로 자신들이 문명화되었다고 생각하는 비명을 지르는 관중들의 기쁨을 위해 피가 흐르는 것을 보는 것을 좋아하기 때문에 권투를 좋아합니다.

Borislav는 발레리나가 엄청난 수의 부상과 어려운 훈련을 겪으며 한 번의 부상으로 모든 것이 끝날 수 있다는 것을 이해하기 때문에 발레를 보고 싶어합니다. 발레 댄서는 지구상에서 가장 위대한 운동선수입니다. 발레리나는 당신의 머리를 걷어찰 수 있지만 결코 그렇게 하지 않을 것입니다. 그녀의 다리는 당신의 얼굴보다 훨씬 더 가치가 있기 때문입니다.

각자 자기 갈 길을 가고 싶어해 좋아하는 이벤트, 그러나 그들은 혼자 즐기고 싶어하지 않으므로 우리는 그들의 승리 패턴을 얻습니다. 가장 높은 가치- 그들이 좋아하는 일을 하세요. 가장 작은 값- 그냥 다른 사람과 함께 있는 것, 제로 - 혼자 있는 것.

어떤 사람들은 완고한 벼랑 끝 전술을 제안합니다. 무슨 일이 있어도 당신이 원하는 것을 한다면 상대방도 당신의 선택에 따르거나 그렇지 않으면 모든 것을 잃게 될 것입니다. 내가 이미 말했듯이, 단순화된 게임 이론은 바보를 식별하는 데 탁월합니다.

실제 적용: 날카로운 모서리를 피하십시오

물론 이 전략에는 심각한 단점도 있습니다. 우선 연애를 '성별 대결'로 치부하면 소용이 없다. 각자가 좋아하는 사람을 찾을 수 있도록 헤어지세요. 그리고 두 번째 문제는 이 상황에서 참가자들이 자신에 대해 확신이 없어서 그렇게 할 수 없다는 것입니다.

모든 사람을 위한 진정한 승리 전략은 자신이 원하는 것을 하는 것입니다.그리고 그 다음날이나 시간이 나면 함께 카페에 가세요. 아니면 복싱과 발레를 번갈아 가며 엔터테인먼트의 세계로 나아가세요. 혁명이 일어날 것이다권투 발레는 발명되지 않을 것입니다.

4. 내쉬 균형

내쉬 균형은 사실 이후에 누구도 다르게 행동하고 싶어하지 않는 일련의 움직임입니다.그리고 우리가 그것을 작동시킬 수 있다면 게임 이론은 지구상의 전체 철학적, 종교적, 금융 시스템을 대체하게 될 것입니다. 왜냐하면 "파산하지 않으려는 의지"가 인류에게 더욱 강력해졌기 때문입니다. 추진력불보다.

빨리 100달러를 나누자. 당신과 나는 필요한 수백 개 중 몇 개를 결정하고 동시에 금액을 발표합니다. 합계가 100 미만이면 모두가 원하는 것을 얻습니다. 만약에 총백 개가 넘으면 가장 적은 금액을 요구한 사람이 원하는 금액을 받고, 욕심이 많은 사람이 남은 금액을 얻습니다. 같은 금액을 요구하면 모두가 50달러를 받습니다. 얼마를 물어보실 건가요? 돈을 어떻게 나눌 것인가? 승리하는 움직임은 단 하나뿐입니다.

$51를 청구하면 얻을 수 있습니다. 최대 금액상대가 무엇을 선택하든 상관없습니다. 그가 더 달라고 하면 당신은 51달러를 받게 될 것입니다. 그가 50달러나 51달러를 요구하면 당신은 50달러를 받게 됩니다. 그리고 그가 50달러 미만을 요구하면 귀하는 51달러를 받게 됩니다. 어쨌든, 당신을 데려올 다른 옵션은 없습니다 더 많은 돈이것보다. 내쉬 균형 - 우리 둘 다 $51를 선택하는 상황입니다.

실제 적용: 먼저 생각하세요

이것이 게임이론의 핵심이다. 승리할 필요도 없고 다른 플레이어에게 해를 끼칠 필요도 없지만 주변 사람들이 무엇을 준비하고 있는지에 관계없이 스스로 최선을 다해야 합니다. 그리고 이 움직임이 다른 플레이어에게 도움이 된다면 더욱 좋습니다. 이것은 사회를 변화시킬 수 있는 일종의 수학이다.

이 아이디어의 흥미로운 변형은 시간 의존적 내쉬 균형이라고 부를 수 있는 음주입니다. 술을 충분히 마시면 다른 사람이 무엇을 하든 상관하지 않지만, 다음날에는 다르게 행동하지 않은 것을 정말 후회하게 됩니다.

5. 토스 게임

토스(toss)는 플레이어 1과 플레이어 2 사이에서 진행됩니다. 각 플레이어는 동시에 앞면이나 뒷면을 선택합니다. 추측이 맞다면 플레이어 1은 플레이어 2의 동전을 얻고, 그렇지 않다면 플레이어 2는 플레이어 1의 동전을 얻습니다.

승리 매트릭스는 간단합니다 ...

...최적의 전략: 완전히 무작위로 플레이합니다.선택이 완전히 무작위여야 하기 때문에 생각보다 어렵습니다. 앞면 또는 뒷면을 선호하는 경우 상대방이 이를 사용하여 돈을 가져갈 수 있습니다.

물론 여기서 진짜 문제는 서로에게 한 푼이라도 던져주면 훨씬 나을 것이라는 점이다. 결과적으로, 그들의 이익은 동일할 것이고, 그로 인한 트라우마는 이 불행한 사람들이 끔찍한 지루함 이외의 다른 것을 느끼는 데 도움이 될 수 있습니다. 결국, 이것은 최악의 게임항상 존재합니다. 이 완벽한 모델승부차기를 위해.

실제 적용: 페널티

축구, 하키 및 기타 여러 게임에서 연장 시간은 승부차기입니다. 그리고 플레이어가 몇 번이나 플레이했는지에 따라 결정되면 더 흥미로울 것입니다. 완전한 형태수레바퀴를 굴릴 수 있을 것입니다. 왜냐하면 그것은 적어도 그들의 신체적 능력을 나타내는 지표이고 보는 것이 재미있을 것이기 때문입니다. 골키퍼는 공이나 퍽의 움직임을 처음부터 명확하게 판단할 수 없습니다. 불행히도 로봇은 아직 스포츠 대회에 참여하지 않기 때문입니다. 골키퍼는 왼쪽 또는 오른쪽 방향을 선택해야 하며 자신의 선택이 골을 쏘는 상대의 선택과 일치하기를 바랍니다. 이는 동전 놀이와 공통점이 있습니다.

그러나 이것이 앞면과 뒷면 게임과의 유사성을 보여주는 완벽한 예는 아니라는 점에 유의하십시오. 올바른 선택을 하는 것방향에 따라 골키퍼가 공을 잡지 못할 수도 있고, 공격수가 골대를 맞추지 못할 수도 있습니다.

그렇다면 게임 이론에 따른 결론은 무엇입니까? 구기 게임은 "멀티 볼" 방식으로 끝나야 합니다. 여기서 한쪽이 특정 결과를 얻을 때까지 일대일 플레이어에게 추가 공/퍽이 매분 제공됩니다. 이는 플레이어의 실제 기술을 나타냅니다. 놀라운 우연의 일치가 아닙니다.

결국 게임이론을 활용해 게임을 더욱 스마트하게 만들어야 합니다. 즉, 더 낫다는 뜻입니다.

게임 이론운영 연구의 한 분야로서 채택의 수학적 모델 이론입니다. 최적의 솔루션서로 다른 이해관계를 가진 여러 당사자 간의 불확실성이나 갈등이 있는 상황에서. 게임 이론은 게임 상황에서 최적의 전략을 연구합니다. 여기에는 과학 및 경제 실험 시스템을 위한 가장 수익성 있는 생산 솔루션 선택과 관련된 상황, 조직이 포함됩니다. 통계적 통제, 산업 기업과 기타 부문 간의 경제적 관계. 갈등 상황을 수학적으로 공식화하면 2인 게임, 3인 게임 등으로 표현될 수 있습니다. 플레이어들은 각자 자신의 이익을 극대화하려는 목표를 추구하며, 상대방을 희생시키면서 승리를 쟁취합니다.

"게임 이론" 섹션은 세 가지로 표현됩니다. 온라인 계산기:

플레이어의 최적의 전략. 이러한 문제에서는 다음과 같이 지정됩니다. 결제 매트릭스. 플레이어의 순수 또는 혼합 전략을 찾는 것이 필요하며, 게임 가격. 풀려면 행렬의 차원과 풀이 방법을 지정해야 합니다. 이 서비스는 2인 게임을 해결하기 위해 다음 방법을 구현합니다.
1. 최소최대 플레이어의 순수 전략을 찾고 싶거나 게임의 안장점에 대한 질문에 대답해야 한다면 이 해결 방법을 선택하세요.
2. 단순 방법. 선형 프로그래밍 방법을 사용하여 혼합 전략 게임을 해결하는 데 사용됩니다.
3. 그래픽 방법. 혼합 전략 게임을 해결하는 데 사용됩니다. 안장점이 있으면 용액이 중지됩니다. 예: 주어진 결제 매트릭스에 대해 다음을 사용하여 플레이어의 최적 혼합 전략과 게임 가격을 찾습니다. 그래픽 방법게임 솔루션.
4. 브라운-로빈슨 반복 방법. 반복적 방법은 그래픽 방법을 적용할 수 없을 때와 대수적 방법과 매트릭스 방법. 이 방법은 게임 가격의 대략적인 가치를 제공하며, 참뜻원하는 정도의 정확도로 얻을 수 있습니다. 이 방법은 최적의 전략을 찾기에는 충분하지 않지만 역학을 추적할 수 있습니다. 턴제 게임각 단계에서 각 플레이어의 게임 가격을 결정합니다.
예를 들어, 작업은 "보상 매트릭스에 의해 주어진 게임에 대한 플레이어의 최적 전략을 나타냅니다"처럼 들릴 수 있습니다..
모든 방법은 주요 행과 열에 대한 검사를 사용합니다.
바이매트릭스 게임. 일반적으로 이러한 게임에서는 첫 번째 플레이어와 두 번째 플레이어의 보상 크기가 동일한 두 개의 행렬이 지정됩니다. 이 행렬의 행은 첫 번째 플레이어의 전략에 해당하고, 행렬의 열은 두 번째 플레이어의 전략에 해당합니다. 이 경우 첫 번째 행렬은 첫 번째 플레이어의 상금을 나타내고, 두 번째 행렬은 두 번째 플레이어의 상금을 나타냅니다.
자연과 함께하는 게임. 선택해야 할 때 사용됩니다. 경영 결정 Maximax, Bayes, Laplace, Wald, Savage, Hurwitz의 기준에 따라.
베이즈 기준의 경우 사건 발생 확률도 입력해야 합니다. 지정하지 않은 경우 기본값을 그대로 둡니다(동등한 이벤트가 발생함).
Hurwitz 기준의 경우 낙관 수준 λ를 나타냅니다. 이 매개변수가 조건에 지정되지 않은 경우 0, 0.5 및 1 값을 사용할 수 있습니다.

많은 문제는 컴퓨터를 사용하여 해결책을 찾아야 합니다. 위의 서비스와 기능은 도구 중 하나입니다.

목차 1 일반 정보 2 1.1 게임. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 이동. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 전략. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 매트릭스 게임. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 트레일 포인트. 순수 전략 7 2.1 예. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 예시 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 예시 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 혼합 전략 9 3.1 게임 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 예시. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 예시 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 예시 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 기하학적 해석. . . . . . . . . . . . . . . . . . . . 12 3.2 게임 2×n 및 m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 예시 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. 게임이론의 일반정보 1.1. 게임 게임 이론은 수학적 이론갈등 상황, 즉 서로 다른 목표를 추구하는 둘 이상의 당사자의 이해관계가 충돌하는 상황. 게임은 갈등상황이며, 규제된다 특정 규칙, 이는 다음을 나타내야 합니다: 참가자의 행동에 대해 가능한 옵션 게임의 정량적 결과 또는 주어진 일련의 동작으로 인해 발생하는 지불(승리, 패배) 상대방의 행동에 대한 양측의 정보량. 복식 게임은 두 명의 파티(두 명의 선수)만이 참가하는 게임입니다. 제로섬 짝 게임은 지불 합계가 0인 짝 게임입니다. 한 플레이어의 손실은 두 번째 플레이어의 이득과 동일합니다. 보상 기능의 가치에 대한 각 플레이어의 태도에 따라 짝을 이루는 게임은 다음과 같이 세분화됩니다. 제로섬 짝을 이루는 게임(적대적) - 지불 금액이 0인 짝을 이루는 게임, 즉 한 플레이어의 손실은 두 번째 플레이어의 이득과 동일합니다. 비적대적 게임 - 복식 게임플레이어는 서로 다르지만 직접적으로 반대되는 목표는 아닙니다. 2 1.2. 이동 이동 - 게임 규칙에 따라 제공되는 작업 중 하나를 선택하고 이 선택을 구현합니다. 이동에는 두 가지 유형이 있습니다. 개인 이동 - + 의식적인 선택게임 규칙에 따라 제공되는 작업 중 하나 + 이 선택의 구현 무작위 이동 - 무작위 이동은 플레이어의 결정이 아닌 임의 선택 메커니즘에 의해 수행되는 여러 가능성 중에서 선택하는 것입니다. 아래에서는 개인적인 움직임만 포함하는 제로섬 짝 게임을 고려합니다. 양측에는 상대방의 행동에 대한 정보가 부족합니다. 3 1.3. 전략 플레이어의 전략은 게임 중에 발생하는 상황에 따라 이 플레이어의 각 개인 움직임에 대한 행동 선택을 결정하는 일련의 규칙입니다. 가능한 전략의 수에 따라 게임은 유한과 무한으로 구분됩니다. 끝없는 게임- 적어도 한 명의 플레이어가 참여하는 게임 무한한 수전략. 유한 게임은 각 플레이어가 유한한 수의 전략만 가지고 있는 게임입니다. 모든 플레이어의 연속 이동 횟수에 따라 게임이 단일 이동, 다중 이동 또는 위치 지정으로 구분됩니다. + 1턴 게임에서는 각 플레이어가 가능한 옵션 중에서 하나만 선택하고 게임의 결과를 결정합니다. + 다중 이동 또는 위치 게임은 시간이 지남에 따라 개발되어 일련의 연속 단계를 나타내며 각 단계는 플레이어 중 한 사람의 이동과 이에 따른 상황 변화 후에 발생합니다. 1턴 게임에서는 각 플레이어가 다음 중에서 하나만 선택할 수 있습니다. 가능한 옵션그리고 게임의 결과를 결정합니다. 플레이어의 최적 전략은 게임이 여러 번 반복될 때 해당 플레이어에게 가능한 최대 평균 승리(또는 동일한 의미로 최소 평균 손실)를 제공하는 전략입니다. 게임 이론에서 모든 권장 사항은 플레이어의 합리적인 행동을 가정하여 이루어집니다. 모든 경기에서 피할 수 없는 선수들의 오산과 실수 갈등 상황, 게임 이론에서는 흥분과 위험 요소를 고려하지 않습니다. 4 1.4. 매트릭스 게임 매트릭스 게임은 1회 이동 유한 제로섬 게임입니다. 매트릭스 게임은 이론적인 게임입니다. 게임 모델정반대의 목표를 달성하기 위해 상대방이 유한한 수 중에서 하나를 선택(이동)하는 갈등 상황 가능한 방법행동 선택한 행동 방법(전략)에 따라 달성된 결과가 결정됩니다. 예를 살펴보겠습니다. 두 명의 플레이어 A와 B가 있고 그 중 한 명이 선택할 수 있습니다. i번째 전략 m개의 가능한 전략 A1, A2, ...Am 중에서 두 번째는 가능한 전략 B1, B2, ...Bm 중에서 j번째 전략을 선택합니다. 결과적으로 첫 번째 플레이어는 aij 값을 획득하고 두 번째 플레이어는 이 값을 잃습니다. 숫자 aij로부터 우리는 행렬   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. ..   를 생성합니다. . . .  am1 am2 · · · amn 행렬 A = (aij), i = 1, m, j = 1, n을 보수 행렬 또는 m × n 게임 행렬이라고 합니다. 이 행렬에서 행은 항상 승리한(최대화하는) 플레이어 A, 즉 자신의 승리를 극대화하기 위해 노력하는 플레이어의 전략에 대한 것입니다. 패배한 플레이어 B, 즉 효율성 기준을 최소화하려고 노력하는 플레이어의 전략에 대해 열이 할당됩니다. 게임 정규화는 위치 게임을 게임에 의해 매트릭스 게임으로 줄이는 과정입니다. 정상적인 형태- 매트릭스 게임으로 축소된 위치 게임 위치 다중 이동 게임은 상대방이 목표를 달성하기 위해 순차적으로 하나의 선택(이동)을 내리는 갈등 상황에 대한 게임 이론 모델이라는 점을 기억합시다. 이 상황이 전개되는 모든 단계에서 가능한 행동 방침은 유한합니다. 게임의 해결책은 두 플레이어의 최적의 전략을 찾아 게임의 가격을 결정하는 것이며, 게임의 가격은 플레이어의 예상 이익(손실)입니다. 게임에 대한 해결책은 순수 전략(플레이어가 하나의 단일 전략을 따라야 하는 경우) 또는 혼합 전략(플레이어가 특정 확률로 두 개 이상의 순수 전략을 사용해야 하는 경우)에서 찾을 수 있습니다. 이 경우 후자를 활성이라고 합니다. 5 한 플레이어의 혼합 전략은 벡터이며, 각 구성 요소는 해당 순수 전략 플레이어의 사용 빈도를 나타냅니다. 게임의 최대값 또는 낮은 가격 - 숫자 α = 최대 min aij i j 최대값 전략(라인) - 플레이어가 최소 상금을 최대화하기 위해 선택한 전략입니다. 분명히 가장 신중한 최대화 전략을 선택할 때 플레이어 A는 (상대방의 행동에 관계없이) 최소 α의 보상을 보장받습니다. Maximin 또는 게임의 최고 가격 - 숫자 β = min max aij j i Minimax 전략(열) - 플레이어가 최대 손실을 최소화하기 위해 선택한 전략입니다. 분명히 가장 신중한 미니맥스 전략을 선택할 때 플레이어 B는 어떤 상황에서도 플레이어 A가 β보다 더 많은 승리를 거두는 것을 허용하지 않습니다. 게임의 최저 가격은 항상 초과되지 않습니다. 최고 가격게임 α = max min aij 6 min max aij = β i j j i 정리 1(이론의 주요 정리 매트릭스 게임). 모든 유한 게임에는 혼합 전략 영역에서 적어도 하나의 솔루션이 있습니다. 6 2. 안장 포인트가 있는 게임. 순수 전략의 해법 안장점이 있는 게임은 다음과 같은 게임입니다. α = max min aij = min max aij = β i j j i 안장점이 있는 게임의 경우, 해결책을 찾는 것은 최적의 최대화 및 최소최대화 전략을 선택하는 것으로 구성됩니다. 게임의 순수 비용 - 일반적인 의미게임의 낮은 가격과 높은 가격 α=β=ν 2.1. 예 예 1 행렬   8 4 7 A= 6 5 9  7 7 8 해결책: 게임의 상한 가격과 하한 가격을 결정하는 게임의 순수 전략에서 해결책을 찾습니다. 이를 위해 우리는 숫자 aij의 최소값을 찾습니다. i번째 줄αi = 최소 aij j 및 숫자 aij의 최대값 j번째 열βj = max aij i 추가 열 형태로 오른쪽 결제 매트릭스 옆에 숫자 αi(행 최소값)를 작성하겠습니다. 추가 라인 형태로 행렬 아래에 숫자 βi(열 최대값)를 씁니다. αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 숫자의 최대값 αi α = max αi = 7 i 및 최소 숫자 βj β = min βj = 7 j α = β - 게임에는 안장 지점이 있습니다. 플레이어를 위한 최적의 전략은 전략 A3이고, 플레이어 B를 위한 최적의 전략은 전략 B2입니다. 정가게임 ν = 7 예 2 보수 행렬이 주어지면:   2 2 1 1 2  0 1 1 1 1  A=  1 1 1 1 2   1 2 1 1 2 순수 전략에서 게임에 대한 해법을 찾습니다. . 풀이: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. 게임에는 6개의 안장 점이 있습니다. 최적의 전략은 다음과 같습니다: A1 및 B3 또는 B4 A3 및 B3 또는 B4 A4 및 B3 또는 B4 8 3. 혼합 전략의 게임 솔루션 α = β일 때. 전략을 선택할 때 두 플레이어 모두 상대방의 선택에 대한 정보가 없는 경우 게임에는 혼합 전략의 솔루션이 있습니다. SA = (p1, p2, ..., 오후) - 혼합 전략플레이어 A, 전략 A1, A2, ..., Am에 확률 ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2, ..., qn)은 플레이어 B의 혼합 전략으로, 전략 B1, B2, ..., Bm에 확률 ∑ n q1, q2, ..., qm, qi = 1, qi가 적용됩니다. > 0, i = 1, n i=1 만약: SA*가 플레이어 A의 최적 전략이고, SB*가 플레이어 B의 최적 전략이라면, 게임 가격은 ∑ n ∑ m ν= aij · p*i입니다. · qi* j=1 i=1 다음으로 정리는 2 × 2, 2 × n, m × 2 게임에 대한 해를 찾는 방법에 대한 질문에 답합니다. 정리 2(2 × 2 게임에 대한 해를 찾는 방법, 2×n, m×2). 플레이어 중 한 명이 최적의 혼합 전략을 사용하는 경우 두 번째 플레이어가 최적의 혼합 전략(순수 전략 포함)에 포함된 전략을 사용할 확률에 관계없이 그의 보상은 게임 비용 ν와 같습니다. 9 3.1. 게임 2 × 2 다음 행렬을 사용하는 2 × 2 게임을 생각해 보십시오. () a11 a21 a21 a22 게임에 순수 전략에는 해결책이 없습니다. 최적의 전략 SA*와 SB*를 찾아보겠습니다. 먼저, SA* = (p*1, p*2) 전략을 정의합니다. 정리에 따르면, 당사자 A가 전략 ν를 고수한다면 당사자 B의 행동 과정에 관계없이 보상은 ν 플레이 비용과 동일하게 유지됩니다. 결과적으로, A 측이 최적의 전략 SA* = (p*1, p*2)을 고수한다면 B 측은 보상을 변경하지 않고 모든 전략을 적용할 수 있습니다. 그런 다음 플레이어 B가 순수 전략 B1 또는 B2를 사용하면 플레이어는 게임 비용과 동일한 평균 보상을 받게 됩니다. a11 p*1 + a21 p*2 = ν ← 전략 B1의 경우 a12 p*1 + a22 p* 2 = ν ← 전략 B2의 경우 p*1 + p*2 = 1이라는 점을 고려하면: p*1 = a2 2−a2 1 a11 +a22 −a12 −a21 p*2 = a1 1−a1 2 a11 +a22 −a12 −a21 게임 가격: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 플레이어 B의 최적 전략은 유사하게 발견됩니다: SB* = (q1* , q2*). q1* + q2* = 1을 고려하면: q1* = a2 2−a1 2 a11 +a22 −a12 −a21 q2* = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. 예 예 3 행렬 () −1 1 A= 1 −1 10을 사용하여 게임에 대한 해법을 찾습니다. 해법: 게임에는 다음이 없습니다. 안장 포인트 , α= -1, β = 1, α̸= β이므로. 우리는 혼합 전략에서 해결책을 찾고 있습니다. p*와 q*에 대한 공식을 사용하여 p*1 = p*2 = 0.5 및 q1* = q2* = 0.5, ν = 0을 얻습니다. 따라서 SA* = (0.5, 0.5) SB* = (0.5, 0.5 ) 예 4 행렬 () 2 5 A= 6 4로 게임에 대한 해를 구합니다. 해법: α= 4, β = 5, α ̸= β이므로 게임에 새들 포인트가 없습니다. 우리는 혼합 전략에서 해결책을 찾고 있습니다. p*와 q*에 대한 공식을 사용하여 p*1 = 0.4, p*2 = 0.6 및 q1* = 0.2를 얻습니다. q2* = 0.8, ν = 4.4 따라서 SA* = (0.4, 0.6) SB* = ( 0.2, 0.8) 11 3.1.2. 기하학적 해석 2×2 게임은 간단한 기하학적 해석을 제공할 수 있습니다. 가로축의 단일 섹션을 취하고 각 지점을 일부 혼합 전략 S = (p1, p2) = (p1, 1 − p1)과 연관시키고 전략 A1의 확률 p1은 다음과 같습니다. SA가 섹션의 오른쪽 끝을 가리키고 확률 p2, 전략 A2 - 왼쪽 끝까지의 거리입니다. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .* .x .P2 .SA* .P1* 특히 섹션의 왼쪽 끝(가로좌표 = 0인 지점)이 해당됩니다. 전략 A1, 세그먼트 오른쪽 끝(x = 1) - 전략 A2 세그먼트 끝에서 x축에 수직인 두 개의 수직선이 복원됩니다: 축 I − I - 전략 A1에 대한 보상이 연기됩니다. 축 II − II - 전략 A2에 대한 보상이 연기되고 플레이어 B가 전략 B1을 적용하도록 합니다. 축 I − I 및 II − II에 각각 좌표 a11 및 a21이 있는 점을 제공합니다. 이 점들을 지나 직선 B1 − B1'을 그립니다. 혼합 전략 SA = (p1, p2)에 대해 플레이어의 보상은 세그먼트를 p2:p1 비율로 나누는 x축의 SA 점에 해당하는 직선 B1 − B1' 위의 점 N에 의해 결정됩니다. 분명히, 전략 B2의 보수를 결정하는 직선 B2 − B2'는 정확히 같은 방식으로 구성될 수 있습니다. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .* .x .P2 .SA* .P1* 최적의 전략 SA*를 찾는 것이 필요합니다. 즉, 플레이어 A의 최소 보상(플레이어 B가 그에게 최악의 행동을 제공한 경우)이 최대값으로 바뀔 것입니다. 이를 위해 전략 B1, B2에 대해 플레이어 A의 보수에 대한 하한을 구성합니다. 파선 B1 N B2' ;. 이 경계에는 혼합 전략에 대한 플레이어 A의 최소 보수, 즉 N 지점이 있으며, 이 보수는 최대치에 도달하고 게임의 결정과 가격을 결정합니다. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .* .x .P2 . A* S . 1* P 점 N의 세로 좌표는 게임 비용 ν에 불과하고 가로 좌표는 *2와 같으며 세그먼트 오른쪽 끝까지의 거리는 *1과 같습니다. SA* 지점에서 세그먼트 끝까지의 거리는 플레이어 A의 최적 혼합 전략의 전략 A2 및 A1의 확률 *2 및 *1과 같습니다. 이 경우 게임의 해결책은 전략 B1과 B2의 교차점에 의해 결정되었습니다. 아래는 플레이어의 최적 전략이 순수 전략 A2인 경우입니다. 여기서 전략 A2(모든 적 전략에 대해)는 전략 A1보다 수익성이 더 높습니다. 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .I . .엑스. 2* P . A*S = A2. 2* P . A* S = A2 오른쪽은 플레이어 B가 명백히 수익성이 없는 전략을 가지고 있는 경우를 보여줍니다. 기하학적 해석을 통해 게임의 낮은 가격 α와 높은 가격 β .y .I .I I .B2를 시각화할 수도 있습니다. .B1′ .N .B1 . B2′ .β = a21 .α = a22 .I I .I .* .x .P2 . A* S . 1* P 동일한 그래프에서 플레이어 B의 최적 전략에 대한 기하학적 해석도 제공할 수 있습니다. 최적의 혼합 전략 SB* = (q1*, q2*)의 전략 B1의 점유율 q1*이 세그먼트 KB1 길이의 합에 대한 세그먼트 KB2 길이의 비율과 동일하다는 것을 쉽게 확인할 수 있습니다. I − I 축의 KB2: .y .I .I I .B2 . B1′ .N .K .L .B1 .B2′ .I I .I .* .x .P2 . A* S . 1* P 14 KB2 q1* = KB2 + KB1 또는 LB2′ q1* = LB2′ + LB1′ 최적의 전략 SB* = (q1* , q2*)는 선수 B와 B를 교체하면 다른 방법으로 찾을 수 있습니다. 상금 하한의 최대 대신 상한의 최소를 고려하십시오. .y .I .I I .A2 .A'1 .N .A1 .A'2 .I I .I . .x .q2* . B* S.q1* 15 3.2. 2 × n 및 m × 2 게임 2 × n 및 m × 2 게임의 해법은 다음 정리에 기초합니다. 정리 3. 모든 유한 게임 m × n은 각 측의 활성 전략 수가 m과 n 중 가장 작은 숫자를 초과하지 않는 해를 가집니다. 이 정리에 따르면 2×n 게임에는 항상 각 플레이어가 최대 2개의 활성 전략을 갖는 솔루션이 있습니다. 이러한 전략을 찾으면 2×n 게임은 2×2 게임으로 바뀌며, 이는 초보적인 방법으로 해결할 수 있습니다. 활성 전략을 찾는 것은 그래픽으로 수행할 수 있습니다. 1) 그래픽 해석이 구성됩니다. 2) 상금의 하한선이 결정됩니다. 3) 두 번째 플레이어의 두 가지 전략은 보상 하한에서 식별되며, 이는 최대 세로 좌표 지점에서 교차하는 두 개의 선에 해당합니다(이 지점에서 두 개 이상의 선이 교차하는 경우 임의의 쌍이 선택됩니다). 는 플레이어 B의 활성 전략을 나타냅니다. 따라서 2 × n 게임은 2 × 2 게임으로 축소됩니다. m × 2 게임도 풀 수 있지만, 보상의 하한이 아니라 상한이 다음과 같습니다. 구성되어 있으며 최대 값은 아니지만 최소값을 추구합니다. 예 5 게임에 대한 해결책 찾기 () 7 9 8 A= 10 6 9 해결책: 기하학적 방법을 사용하여 활성 전략을 선택합니다. 직선 B1 − B1', B2 − B2' 및 B3 − B3'은 전략 B1, B2, B3에 해당합니다. 점선 B1 N B2는 플레이어의 상금 하한선입니다. 게임에는 S*A = (23, 31)이라는 솔루션이 있습니다. S*B = (0.5; 0.5; 0); v = 8. 16 .y .I .I I . 1′ BB . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .엑스. 2* P . A* S . 1* P 17 인덱스 게임, 2 이동, 3 2 × 2, 10 개인, 3 2 × 2, 9 무작위, 3 기하학, 12 순 게임 가격, 7 예, 10 2 × n, 9, 16 m × 2, 9 , 16개 무한, 4개 정규형, 5개 유한, 4개 다중 이동, 4개 단일 이동, 4개 행렬, 5개 쌍, 2개 제로섬, 2개 길항, 2개 비길항, 2해, 5개 혼합 전략, 5 , 순수 전략 9개, 안장점 포함 5개, 가격 7개, 상위 5개, 하위 6개, 순수 6개, 최대값 7개, 게임 매트릭스 6개, 보수 5개, 미니맥스 5개, 게임 정규화 5개, 전략 5개, 최대값 4개, 미니맥스 6개, 6개 최적, 4 혼합, 5 게임 이론, 2 18

여러 충돌 당사자(사람)가 있고, 각각은 주어진 규칙 세트에 따라 특정 결정을 내리고 각 사람은 각 당사자에 대해 미리 결정된 지불금으로 갈등 상황의 최종 상태를 알고 있는 경우 게임 일어난다고 합니다.

게임 이론의 임무는 특정 플레이어의 행동 라인을 선택하는 것입니다. 이로부터 벗어나면 그의 승리가 줄어들 수 있습니다.

게임에 대한 몇 가지 정의

게임 결과에 대한 정량적 평가를 결제라고 합니다.

더블스 (두 사람) 지불 합계가 0인 경우 제로섬 게임이라고 합니다. 한 플레이어의 손실이 다른 플레이어의 이득과 같은 경우.

플레이어가 개인적인 움직임을 취해야 하는 가능한 상황 각각에서 플레이어의 선택에 대한 명확한 설명을 호출합니다. 플레이어의 전략 .

게임이 여러 번 반복될 때 플레이어에게 가능한 최대 평균 보수(또는 동일한 의미로 최소 가능한 평균 보수)를 제공하는 경우 플레이어의 전략을 최적이라고 합니다.

매트릭스로 정의된 게임 ㅏ데 중라인과 N열은 차원의 유한쌍 게임이라고 불린다. 중* N;

어디 나=
- 전략을 갖춘 첫 번째 플레이어의 전략; 제이=- 두 번째 플레이어의 전략은 n개의 전략을 가지고 있습니다. ij– 첫 번째 플레이어의 승리 나-두 번째로 사용할 때의 전략 제이두 번째 전략(또는 동일한 의미로 두 번째 전략의 손실) 제이-번째 전략, 처음 사용하는 경우 나일);