Теорія ігор: розв'язані задачі — рівновага Неша, мінімакс, Шеплі

Q: Які методи розв'язання задач з 🎲 теорія ігор демонструються на цій сторінці?

Сторінка демонструє стандартні та нестандартні методи розв'язання задач з '🎲 Теорія ігор': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.

Q: Якого рівня складності задачі з 🎲 теорія ігор представлені?

Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.

Q: Як вчитися на розв'язаних задачах з 🎲 теорія ігор найефективніше?

Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.

Q: Чи є в розв'язках покрокові пояснення всіх перетворень?

Так, кожен розв'язок 🎲 теорія ігор містить детальні покрокові пояснення: записується перетворення, обґрунтовується його правомірність, вказуються використані теореми та формули. Підхід 'показати думку', а не лише відповідь.

Q: Як ці задачі з 🎲 теорія ігор допомагають при підготовці до контрольних та іспитів?

Розв'язані задачі з '🎲 Теорія ігор' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.

Рівновага Неша у грі координації (чисті стратегії)

Задача: Гравці A і B обирають одночасно. Знайдіть усі рівноваги Неша:

	B: Ліво	B: Право
A: Верх	3, 2	1, 1
A: Низ	0, 0	2, 3

Знаходимо найкращу відповідь (Best Response) гравця A:

Якщо B обирає Ліво: A порівнює 3 vs 0 → A обирає Верх Якщо B обирає Право: A порівнює 1 vs 2 → A обирає Низ

Знаходимо найкращу відповідь гравця B:

Якщо A обирає Верх: B порівнює 2 vs 1 → B обирає Ліво Якщо A обирає Низ: B порівнює 0 vs 3 → B обирає Право

Рівновага Неша — перетин найкращих відповідей:

NE₁: (Верх, Ліво) → виграші (3,2) ✓ Перевірка: A змінює Верх→Низ: 0<3 (не вигідно) B змінює Ліво→Право: 1<2 (не вигідно) ✓ NE₂: (Низ, Право) → виграші (2,3) ✓ Перевірка: A змінює Низ→Верх: 1<2 (не вигідно) B змінює Право→Ліво: 0<3 (не вигідно) ✓

Відповідь: дві рівноваги Неша у чистих стратегіях: (Верх, Ліво) з виграшами (3,2) і (Низ, Право) з виграшами (2,3). Це класична гра координації.

Домінантні стратегії: дилема в'язня

Задача: Двоє підозрюваних: мовчати (С — спів-праця) або зізнатися (D — дефекція). Роки ув'язнення (виграш = −роки):

	B: C (мовчить)	B: D (зізнається)
A: C (мовчить)	−1, −1	−10, 0
A: D (зізнається)	0, −10	−5, −5

Перевіряємо, чи D строго домінує C для гравця A:

Якщо B обирає C: A(D)=0 > A(C)=−1 ✓ D краще Якщо B обирає D: A(D)=−5 > A(C)=−10 ✓ D краще D строго домінує C для A: незалежно від вибору B, D завжди краще!

Симетрично для гравця B: D строго домінує C.

Ітеративне вилучення строго домінованих стратегій (IESDS):

Крок 1: C строго доміновано для A → вилучаємо C для A Крок 2: C строго доміновано для B → вилучаємо C для B Залишається: єдина стратегія (D, D) → NE: (−5, −5) Соціальна дилема: NE = (D,D) = (−5,−5) ← рівновага Неша Парето-оптимум = (C,C) = (−1,−1) ← недосяжне без кооперації!

Відповідь: стратегія D (зізнатися) строго домінує для обох. Єдина рівновага Неша: (D,D)=(−5,−5), хоча спільний оптимум (−1,−1) недосяжний — ось у чому «дилема».

Рівновага Неша у змішаних стратегіях

Задача: Гра «Відповідність пенні» (Matching Pennies): якщо монети однакові — A виграє 1, якщо різні — B виграє 1. Знайдіть змішану рівновагу Неша.

Матриця виграшів для A:

B: Орел B: Решка A: Орел [ +1, -1 ] A: Решка [ -1, +1 ] (нульова сума: виграш B = −виграш A)

Чисті рівноваги: у Matching Pennies немає рівноваги в чистих стратегіях. Шукаємо змішані.

Умова рівноваги: гравець B повинен бути байдужий між своїми стратегіями.

Нехай A грає Орел з ймовірністю p, Решка з (1−p). Виграш B від Орла: −p + (1−p) = 1−2p Виграш B від Решки: p − (1−p) = 2p−1 Байдужість B: 1−2p = 2p−1 → 4p=2 → p* = 1/2 Симетрично: нехай B грає Орел з ймовірністю q. Виграш A: від Орла = q−(1−q) = 2q−1 від Решки = −q+(1−q) = 1−2q Байдужість A: 2q−1 = 1−2q → q* = 1/2

Очікуваний виграш у рівновазі:

E[u_A] = ½·(½·1+½·(−1)) + ½·(½·(−1)+½·1) = 0 Ціна гри = 0 (справедлива гра)

Відповідь: єдина рівновага Неша — змішана: обидва гравці обирають Орел або Решку з ймовірністю ½. Ціна гри = 0.

Мінімакс: гра з нульовою сумою

Задача: Знайдіть мінімаксне рішення для матричної гри з нульовою сумою:

A\B	b₁	b₂	b₃
a₁	3	−2	4
a₂	1	5	−1
a₃	2	3	0

Maximin: A максимізує мінімальний гарантований виграш (рядкові мінімуми):

min(a₁) = min(3,−2,4) = −2 min(a₂) = min(1,5,−1) = −1 min(a₃) = min(2,3,0) = 0 ← максимум! A обирає стратегію a₃: v̲ = max_i min_j aᵢⱼ = 0

Minimax: B мінімізує максимальний виграш A (стовпцеві максимуми):

max(b₁) = max(3,1,2) = 3 max(b₂) = max(−2,5,3) = 5 max(b₃) = max(4,−1,0) = 4 B обирає стратегію b₁: v̄ = min_j max_i aᵢⱼ = 3

v̲=0 ≠ v̄=3: сідлова точка відсутня → потрібні змішані стратегії.

Перевірка сідлової точки: a_{ij}* = max ∈ рядку AND min ∈ стовпці У матриці: a₃₁=2 → min у рядку 3? min(2,3,0)=0 ≠ 2. Немає сідлової. При змішаних стратегіях: 0 ≤ v* ≤ 3 (теорема Неша) Точне v* відповідного LP обчислюється розв'язком: max v subject to A^T · x ≥ v·1, Σxᵢ=1, xᵢ≥0

Відповідь: v̲=0 (maximin), v̄=3 (minimax). Сідлова точка відсутня. Оптимальне рішення — у змішаних стратегіях. 0≤v*≤3 (теорема мінімакс Неймана).

Значення Шеплі для гри трьох гравців

Задача: Три партнери {1,2,3} засновують фірму. Характеристична функція: v(∅)=0, v({1})=0, v({2})=0, v({3})=0, v({1,2})=60, v({1,3})=50, v({2,3})=40, v({1,2,3})=100. Знайдіть значення Шеплі φᵢ.

Формула Шеплі для гравця i:

φᵢ(v) = Σ_{S⊆N\{i}} [|S|!(n−|S|−1)!/n!] · [v(S∪{i})−v(S)] n=3, тому ваги: |S|=0: 0!·2!/3! = 1/3 |S|=1: 1!·1!/3! = 1/6 (по 2 таких коаліції) |S|=2: 2!·0!/3! = 1/3

Обчислимо φ₁ (маргінальні внески гравця 1):

S=∅: v({1})−v(∅) = 0−0 = 0 вага: 1/3 S={2}: v({1,2})−v({2}) = 60−0 = 60 вага: 1/6 S={3}: v({1,3})−v({3}) = 50−0 = 50 вага: 1/6 S={2,3}: v({1,2,3})−v({2,3}) = 100−40=60 вага: 1/3 φ₁ = 1/3·0 + 1/6·60 + 1/6·50 + 1/3·60 = 0 + 10 + 50/6 + 20 = 30 + 50/6 ≈ 38.33

Обчислимо φ₂ і φ₃:

φ₂: S=∅: v({2})−v(∅) = 0 вага: 1/3 S={1}: v({1,2})−v({1}) = 60 вага: 1/6 S={3}: v({2,3})−v({3}) = 40 вага: 1/6 S={1,3}: 100−50 = 50 вага: 1/3 φ₂ = 0 + 10 + 40/6 + 50/3 = 10 + 40/6 + 100/6 = 10 + 140/6 ≈ 33.33 φ₃: S=∅: 0 вага: 1/3 S={1}: 50−0=50 вага: 1/6 S={2}: 40−0=40 вага: 1/6 S={1,2}: 100−60=40 вага: 1/3 φ₃ = 0 + 50/6 + 40/6 + 40/3 = 90/6 + 80/6 = 170/6 ≈ 28.33 Перевірка (ефективність): 38.33+33.33+28.33 = 100 = v(N) ✓

Відповідь: φ₁ ≈ 38.33, φ₂ ≈ 33.33, φ₃ ≈ 28.33 (у частках). Гравець 1 отримує найбільше, бо вносить найбільший маргінальний внесок у коаліції.

Еволюційно стабільна стратегія: гра «Яструб-Голуб»

Задача: Яструб (H) бореться до переможця; Голуб (D) відступає. Ресурс V=10, витрати бою C=20. Знайдіть ESS.

Матриця виграшів (середній виграш одного гравця):

Суперник: H (Яструб) D (Голуб) H: (V−C)/2 = −5 V = 10 D: 0 V/2 = 5 Виграш H vs H: обидва борються → один виграє V, другий платить C → середнє (V−C)/2=−5 Виграш H vs D: Яструб завжди виграє → V=10 Виграш D vs H: Голуб відступає → 0 Виграш D vs D: поділяють ресурс → V/2=5

Перевірка чистих ESS: чи є H або D еволюційно стабільними?

H — ESS? Треба: u(H,H) > u(D,H) → −5 > 0? НІ → H не ESS D — ESS? Треба: u(D,D) > u(H,D) → 5 > 10? НІ → D не ESS → Немає чистих ESS, шукаємо змішану ESS.

Змішана ESS: популяція з часткою p Яструбів. Умова байдужості:

Виграш H в популяції з часткою p яструбів: W(H) = p·(−5) + (1−p)·10 = 10 − 15p Виграш D: W(D) = p·0 + (1−p)·5 = 5 − 5p Байдужість W(H)=W(D): 10 − 15p = 5 − 5p → 5 = 10p → p* = 1/2 (50% яструбів) Середній виграш у рівновазі: W* = 10 − 15·(1/2) = 10 − 7.5 = 2.5 Перевірка стабільності: для мутанта з часткою ε: u(H, p*+εΔ) = u(D, p*+εΔ) для першого порядку, але другий порядок підтверджує стійкість (∂²/∂p² < 0)

Відповідь: жодна чиста стратегія не є ESS. Змішана ESS: рівноважна частка яструбів p*=V/C=10/20=0.5 (50%). Середній виграш у рівновазі W*=V·(1−V/(2C))=2.5.

Часті запитання (FAQ)

Які методи розв'язання задач з 🎲 теорія ігор демонструються на цій сторінці?

Сторінка демонструє стандартні та нестандартні методи розв'язання задач з '🎲 Теорія ігор': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.

Якого рівня складності задачі з 🎲 теорія ігор представлені?

Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.

Як вчитися на розв'язаних задачах з 🎲 теорія ігор найефективніше?

Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.

Чи є в розв'язках покрокові пояснення всіх перетворень?

Так, кожен розв'язок 🎲 теорія ігор містить детальні покрокові пояснення: записується перетворення, обґрунтовується його правомірність, вказуються використані теореми та формули. Підхід 'показати думку', а не лише відповідь.

Як ці задачі з 🎲 теорія ігор допомагають при підготовці до контрольних та іспитів?

Розв'язані задачі з '🎲 Теорія ігор' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.

🎲 Теорія ігор: Розв'язані задачі