Теорія ігор: дилема ув'язненого, стратегія мстивого зяблика та реформи

Теорія ігор

Теорія ігор досліджує процеси ухвалення рішень у складних ситуаціях. Для визначення гри потрібно задати гравців (хто власне буде ухвалювати рішення), описати їх можливі дії, визначити всі можливі наслідки дій гравців та задати на них функцію виграшу. Власне гра виникає коли виграші одного гравця залежать від дій інших. Важливою, також, є наявна у гравців інформація, оскільки вона впливає на стратегії гравців. Стратегією гравця називається правило, яке дозволяє вибрати для кожної позиції гри і наявної в цей момент інформації — дію.

Наприклад, відома всім гра у камінь-ножиці-бумагу є предметом дослідження теорії ігор, оскільки в ній є гравці, відомі їх дії (вибір одного з трьох варіантів) та виграші (які залежать від дій інших). При цьому стратегія може бути фіксована — завжди грати камінь (багато ви нею не виграєте), або ймовірністна — вибирати з рівною ймовірністю з усіх варіантів (ця стратегія є рівновагою Неша для даної гри).

Про теорію ігор можна розказувати дуже довго, але ідея цієї статті — розказати про одну гру, яка є найбільш цікавою, складною та контрінтуітивною з базових ігор. І ще її особливість в тому, що вона часто зустрічається у реальному житті. В цій статті я спробую описати ділему ув'язненого у науковій галузі.

Дилема ув'язненого

Класичне формулювання дилеми ув'язненого таке: двох злочинців, яких підозрюють у скоєнні злочину піймали за дрібне правопорушення. Їх садять у різні камери без змоги спілкування і пропонують кожному угоду зі слідством, якщо той зізнається у злочині. Якщо обоє мовчать — вони отримують невеликий термін за правопорушення, якщо обоє зізнаються — отримують помірний термін (пом'якшений за зізнання), якщо один зізнається, то він отримує умовне покарання, а інший — максимальне. Відповідно стратегія кожного або кооперація зі своїм напарником (тобто мовчати), або зрадити (тобто зізнатись). Виграші визначимо у формі балів за той чи інший результат — кожен гравець хоче максимізувати свої бали. Наступна матриці (перша цифра виграш гравця який вибирає рядки, друга — стовпці) описує гру — у клітинках результат для відповідної комбінації стратегій у формі (виграш першого гравця — виграш другого гравця) :

Тут числа описують бажаність результату для гравця. Легко бачити, що кожен з гравців має домінуючу стратегію — зраджувати завжди вигідніше, незалежно від дій суперника. Ситуація зрада-зрада є рівновагою Неша, жодному гравців не вигідно відхилятися — він погіршує свій виграш. Покращити виграш можна лише домовившись — але в рамках некооперативної гри у гравців немає ніяких стимулів дотримуватись угоди.

Виникає дивна ситуація: найкращий результат — кооперація, але він недосяжний! Існує велика кількість обговорень чому і як виникає така ситуація, але давайте просто розглянемо наступний приклад.

Приклад 1. Припустимо Ви прийшли в казино з метою взяти участь у покерному турнірі. Вхідний внесок дорівнює 65$ (ці гроші ідуть у призовий фонд ) і Ви отримуєте 2500 фішок для гри. В цей момент казино пропонує Вам додаткову можливість — докупити ще 500 фішок за 5$.

Як би Ви вчинили? 500 фішок можуть бути критичним на початку і сума досить смішна. Маленька додаткова деталь — ці гроші не потрапляють у призовий фонд — казино бере їх собі.

Виявляється, що стратегія брати додаткові фішки є домінуючою. Якщо інші гравці не взяли фішки — я покращую свої шанси на виграш, якщо інші гравці взяли фішки — я також покращую свої шанси (вирівнюючи їх). Це ї є дилема ув'язненого.

Результат — всі гравці докупили фішки, їх шанси на виграш практично не змінилися, казино отримало N*5$ просто так.

Приклад 2. В 70хх роках на американському телебаченні відбувалась війна брендів цигарок. Реклама досягла візуальної досконалості, були продумані цілі всесвіти, такі як країна Мальборо. Великі компанії витрачали суттєві кошти. Виявилось. що ситуація повторює дилему ув'язненого — великі компанії, які поділили ринок хотіли б припинити агресивну коштовну рекламу — але тільки в тому разі якщо всі це зроблять. Якщо одна компанія рекламується, а інші — ні, то перша кампанія отримує бонуси і переманює покупців. Тому не дивно, що заборону реклами цигарок (1971), можливо (прямих доказів немає), лобіювали великі тютюнові компанії, такі як Філіп Моріс. Заборона їх цілком влаштовувала, оскільки зафіксувала долі ринку.

Нарешті останній приклад був запропонований Р. Докінзом у книжці Егоїстичний ген. Уявимо собі популяцію пташок (нехай це будуть зяблики), яких мучають паразити. Кожна пташка може почистити собі всі частини крім маківки, тому вона звертається по допомогу до інших. Ресурси обмежені, тому кожна пташка зацікавлена у виживанні (навіть за рахунок інших), таким чином вибираючи «не допомагати» я покращую свої шанси на виживання незалежно від дій іншого.

Звичайно, така ситуація сформована декількома елементами моделі, які жорстко задані: раціональність гравців (тобто вважається, що кожен учасник намагається максимізувати виграш), відсутність можливості спілкування, один раунд гри.

Але головна проблема з дилемою ув'язненого така: вона суперечить досвіду — принаймі в деяких іграх, які проводились автором під час популярних лекцій і курсів в КПІ стабільно 30-40% учасників обирали кооперацію. Це підтверджено і іншими соціальними експериментами — люди прагнуть співпрацювати (іноді це бажання залежить від культури, досвіду, освіти).

Також існують приклади поведінки тварин, які в результаті еволюції виробили подібні механізми. Ті ж самі зграйні пташки співпрацюють у природі.

Результат теорії ігор (хоча частково і суперечить досвіду) цілком узгоджений, наприклад, ситуації з голосуванням. Так, голосування «за гречку» також є дилемою ув'язненого. Наприклад, є опції отримати щось корисне зараз, або проголосувати за достойного кандидата. У будь-якому разі — якщо інші проголосують за достойного кандидата, або візьмуть гречку — вигідно брати гречку.

Цікавим наслідком цього є, наприклад, беззмістовність закликів до «всіх» змінити свою поведінку на виборах — ходити, обирати достойних і т.д., оскільки це не працює для дилеми ув'язненого. В рівноважному стані усі гравці задоволені і ніхто не хоче змінювати свою стратегію. Для розв'язання цієї соціальної дилеми потрібно вийти за рамки гри. Які є варіанти змінити поведінку раціональних гравців у цій ситуації? Ось деякі з них:

1. перетворити їх на нераціональних (ситуації екзистенціального вибору — війна, існування держави і т.д.)
2. Змінити платежі так, щоб виграш від короткотермінових бонусів був менше за довготривалі виграші від голосування за хорошого кандидата (ну можливо колись це станеться)
3. Додати зовнішню структуру, яка б заохочувала до кооперації. Наприклад невідворотність покарання за підкуп виборців.

Тож невже все так сумно? Насправді не все.

Багатокрокова дилема ув'язненого

Причина, чому зяблики співпрацюють може полягати у багатокроковості гри. Адже життя не закінчується одним епізодом взаємодії, а продовжується на наступний день. Якщо сьогодні я відмовлюсь рятувати тебе, то завтра не буде кому врятувати мене. Ідея, звичайно, у вірному напрямку, але багатокроковість не працює, якщо кількість раундів фіксована. У цьому випадку на останньому раунді всім знову вигідно зраджувати, а отже і на передостанньому також і т.д.

Ситуацію рятує або нескінченна кількість раундів, або додавання ймовірності (і це красивий несподіваний результат). Якщо на кожному раунді гра закінчується з фіксованою ймовірністю, то (за деяких умов) співпрацювати стає вигідно.

Не зовсім зрозуміло, правда, як використати цей результат на практиці, тому ми розглянемо інший підхід.

Турнір Аксельрода

В 1980 році Роберт Аксельрод запропонував різним вченим взяти участь у особливому турнірі з дилеми ув'язненого. Кожен з них надіслав стратегію гри у вигляді програми. Після цього для кожної пари стратегій була запущена 150 раундова гра. Практична ідея яка за цим стоїть наступна: гравці використовують стратегії і порівнюють виграші свої і інших. Після певного часу раціональні гравці вибирають стратегії, що дають найбільший виграш.

Неймовірно, але переможцем виявилась одна з найпростіших стратегій «зуб-за-зуб». Ця стратегія починала з співпраці а потім копіювала поведінку суперника на попередньому кроці. Тобто мстила за зраду, але враховувала повернення до співпраці.

Ця ж стратегія перемогла і на другому турнірі. Виявилось, що «зуб-за-зуб» дає пристойний виграш проти «паскудних» стратегій і добре кооперується з наївними. Таким чином, в середньому це найкраща стратегія.

На турнірі було багато стратегій, але ми обмежимось розглядом двох з них.

Наївні, паскудні і мстиві зяблики

Розглянемо популяцію наївних зябликів (НЗ), кожен з яких співпрацює з іншими. Додамо новий тип поведінки — паскудні зяблики (ПЗ). Паскудні зяблики просять про допомогу, але ніколи не допомагають у відповідь.

Для ілюстрації використаємо Модель 1 (можна гратись он-лайн), яка є частиною бібліотеки моделей системи NetLogo (можна скачати і погратись тут).

В цій моделі кількість учасників наперед фіксована і не змінюється. Вони зустрічаються під час віпадкових блукань і при зустрічі грають гру (див Таблицю 1).

Результати моделювання протягом часу показує, що виграш паскудних зябликів (синя лінія) завжди більша за виграш наївних (червона лінія).

Однак, якщо ми подивимось на взаємодію мстивих (зелена лінія) і паскудних зябликів, то ми побачимо цікаву динаміку — спочатку останні виграють, до того моменту, як більшість мстивих зябликів (МЗ) зіткнеться з обманом і запам'ятає своїх «партнерів». Це займає багато часу.

Ще більш цікаво, що наявність наївних зябликів не дає можливість перемагати стратегії МЗ. Наївні зяблики є тою харчовою базою, яку використовують паскудні зяблики для отримання виграшів.

Більш ефективним є стратегія мстивих зябликів які галасують (МЗяГ — фіолетова лінія). В цій моделі мстивий зяблик, який зустрічається з обманом починає інформувати всіх інших про того, хто його обманув. В результаті виграш стратегії МЗяГ набагато швидше перебиває стратегію паскудних зябликів.

Схожі шаблони кожен може пошукати навколо нас. Розглянемо такий: науковий плагіат і імітація наукових досліджень. Хронологічно ситуацію можна представити так:

1. Початкова система. Загалом система захисту дисертацій з природничих наук до розвалу союзу виконувала свою функцію. Відповідно наївні зяблики просто робили науку і намагались чесно публікуватись, захищатись і т.д.
2. Зникнення обмежуючих фільтрів. Після 90хх радикальне розрідження наукової спільноти, фактично необхідність виживання призвели до розвалу експертизи у журналах, наукових радах. Виникає можливість «комерційного» захисту.
3. Після зменшення конкуренції починається деградація. Будь-який інститут — це ставки співробітників, крім того певні посади вимагають наявності наукового ступеня. Аспіранти і захисти умова отримання грошей, таким чином виграші паскудних зябликів зростають. Числимось на ставці — пишем статті для звітності — виконуємо формальні вимоги — автозахист — ставка більша.
4. Загроза іншим. В певний момент кількість паскудних зябликів зростає і вони зустрічаються з наївними. Наївні вчені розуміють, що вони програють — витрачені зусилля важать стільки ж скільки імітована наука. Зрозуміло, що справжній вчений запам'ятовує роботу з плагіатом яку він рецензував або захищену порожню дисертацію і робить висновки.
5. В якийсь момент спільнота розуміє, що раз нічого не можна зробити, то потрібно принаймі говорити про це. Інформувати, створювати базу паскудних зябликів. Так виникає стратегія МЗяГ.
6. Тенденції. Поки що виграші паскудних зябликів переважають.

Деякі цікаві моменти

1. Кількість наївних зябликів не має значення — вони не можуть виграти в цій грі просто в силу її структури. Усереднені виграші паскудних зябликів (що цікаво) більші, якщо їх менше. Тобто, якщо зовнішня сила зменшує поточну кількість ПЗ і не змінює правил гри — вони радіють, адже частка кожного зростає.
2. Стратегія мстивих зябликів дозволяє (дуже повільно) вигравати у ПЗ і змінювати ситуацію на краще. Стратегія МЗяГ пришвидшує процес. Позбавлення гравців, що використовують стратегію ПЗ виграшів дає можливість зупинити їх експансію і поступово локалізувати. Але для успішності необхідна включеність у процес максимальної кількості наївних зябликів.
3. Кількість скандалів та їх поширеність є, таким чином, індикатором успішності реформування, а розголос і зберігання інформації про всіх ПЗ є ключовими.
4. Цікаво, що мстивість є якістю, яка сприяє співпраці у середовищі — досить парадоксальний висновок.
5. Статегії «зуб-за-зуб» та мстивий зяблик еквівалентні для паскудних зябликів, але перша пробачає після покарання. Чи є сенс її застосовувати — відкрите питання.