У теорії ігор гра називається потенційною грою, якщо стимул усіх гравців змінити свою стратегію можна виразити за допомогою однієї глобальної функції, яка називається потенційною функцією. Ця концепція виникла в статті Дова Мондерера та Ллойда Шеплі 1996 року.

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

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

Потенційні ігри також можуть розглядатися як повторювані ігри зі станом, у яких результат кожного раунду безпосередньо впливає на стан гри в наступному раундіMarden, J., (2012) State based potential games http://ecee.colorado.edu/marden/files/state-based-games.pdf. Такий підхід застосовується у задачах розподіленого керування, зокрема при розподіленому розподілі ресурсів, де гравці, не маючи централізованого механізму координації, можуть взаємодіяти для досягнення глобально оптимального розподілу ресурсів.

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

Дана гра , ми кажемо, що є потенційною грою з точною (зваженою, порядковою, узагальненою порядковою, найкращої відповіді) потенційною функцією, якщо — точна (зважена, порядкова, узагальнена порядкова, найкраща відповідь відповідно) потенційна функція для Нижче ми визначимо ці поняття.

називається точною потенційною функцією, якщо

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

називається зваженою потенційною функцією, якщо існує вектор такий, що

Тобто, коли гравець змінює свою дію, зміна дорівнює зміні виграшу цього гравця, помноженій на додатну вагу, специфічну для цього гравця. Кожна точна потенційна функція є зваженою потенційною функцією з wi=1 для всіх i.

називається порядковою потенційною функцією, якщо

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

називається узагальненою порядковою потенційною функцією, якщо

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

називається потенційною функцією найкращої відповіді, якщо

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

називається псевдопотенційною функцією, якщо

Тобто для кожного гравця i максимізація спільної потенційної функції приводить до деякої найкращої відповіді.

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

Простий приклад У грі з двома гравцями та двома діями з екстерналіями, виграші окремих гравців задаються функцією , де – дія i-го гравця, – дія суперника, а w – позитивний екстерналій від вибору тієї ж дії. Варіанти дій: +1 та −1, як показано на матриці виграшів на рисунку 1.

Ця гра має потенційну функцію

Якщо гравець 1 переміщується з −1 на +1, різниця виграшів становить .

Зміна потенціалу дорівнює .

Розв'язок для гравця 2 еквівалентний. Використовуючи числові значення , , , цей приклад перетворюється на просту битву статей, як показано на рисунку 2. У грі є дві чисті рівноваги Неша, та . Це також локальні максимуми потенційної функції (рис. 3). Єдина стохастично стійка рівновага – , глобальний максимум потенційної функції.

Гра за участю двох гравців, кожен з яких має дві можливі дії, не може бути потенційною, якщо не виконується така умова:

Потенційні ігри та ігри з перевантаженнями Ігри з точним потенціалом еквівалентні іграм із заторами: Розенталь. довів, що кожна гра із заторами має точний потенціал; Мондерер і Шеплі довели протилежний напрямок: кожна гра з точною потенційною функцією є грою із заторами .

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

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

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

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

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

Шлях найкращої реакції – це окремий випадок шляху покращення, в якому кожен вектор досягається з попереднього вектора шляхом зміни стратегії одного гравця на стратегію найкращої реакції. Властивість, що кожен шлях найкращої реакції є скінченним, називається властивістю скінченної найкращої реакції (FBRP). FBRP слабша за FIP, і вона все ще передбачає існування рівноваги Неша з чистою стратегією. Це також означає, що рівновагу Неша можна обчислити розподіленим процесом, але обчислювальне навантаження на агентів вище, ніж у FIP, оскільки вони повинні обчислювати найкращу реакцію.

Ще слабшою властивістю є слабка ациклічність (WA, Weak Acyclicity). Вона означає, що для будь-якого початкового вектора стратегій існує скінченний шлях найкращої відповіді, який починається з цього вектора.

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

Псевдопотенційні ігри Дубей, Гайманко та Запечельнюк  довели:

Будь-яка гра слабких стратегічних замінників або стратегічних доповнень з агрегацією є псевдопотенційною грою. Будь-яка псевдопотенційна гра має рівновагу Неша з чистою стратегією.

Корельовані рівноваги Абрахам Нейман вивчав потенційні ігри, в яких:

потенціал є гладкою та увігнутою функцією, множини стратегій опуклі, корисності обмежені.

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

Якщо, крім того:

набори стратегій компактні, потенціал є суворо увігнутою функцією,

тоді корельована рівновага є унікальною.

Див. також

Еконофізика Характеристика порядкових потенційних ігор.

Посилання

Зовнішні посилання

Конспект лекцій Ішая Мансура про ігри з потенціалом та заторами Розділ 19 у: Алгоритмічна теорія ігор (PDF). Кембридж, Велика Британія: Видавництво Кембриджського університету. . Нетехнічний виклад Х'ю Діксона про неминучість змови . Розділ 8, Світ пончиків та архіпелаг дуополії, Економіка серфінгу.