Вчений розгадав головоломку теорії ігор майже 60-річної давності

Щоб зрозуміти здатність автономних транспортних засобів керувати складними дорогами, вчені часто вдаються до теорії ігор – розділу математики, який займається моделюванням раціональної поведінки агентів, коли вони прагнуть досягти своїх цілей. Протягом багатьох років Деян Мілутінович, професор електротехніки та комп’ютерної інженерії Каліфорнійського університету в Санта-Крузі, співпрацював із колегами-дослідниками у складній підгрупі теорії ігор, відомої як диференціальні ігри. Це поле стосується гравців у русі. Серед цих ігор є гра переслідування стіни, яка пропонує відносно нескладну структуру для сценарію, коли швидший переслідувач прагне захопити повільнішого ухиляча, який обмежений рухом уздовж стіни.

Оскільки ця гра була вперше описана майже 60 років тому, у грі виникла дилема — набір позицій, для яких вважалося, що оптимального рішення гри не існує. Але тепер Мілутінович і його колеги довели в новій статті, опублікованій в журналі IEEE Transactions on Automatic Control, що цієї давньої дилеми насправді не існує, і запровадили новий метод аналізу, який доводить, що завжди існує детерміноване рішення стіни. гра переслідування. Це відкриття відкриває двері для вирішення інших подібних проблем, які існують у сфері диференціальних ігор, і дозволяє краще міркувати про автономні системи, такі як безпілотні транспортні засоби.

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

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

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

Тож Мілутінович і його співавтори винайшли новий спосіб підійти до проблеми, використовуючи математичну концепцію, якої не існувало, коли спочатку була задумана гра переслідування по стіні. Використовуючи розв’язок в’язкості рівняння Гамільтона–Якобі–Айзекса та запровадивши аналіз швидкості втрат для розв’язання сингулярної поверхні, вони змогли виявити, що оптимальне рішення гри можна визначити за будь-яких умов гри та вирішити дилему.

Розв’язок диференціальних рівнянь із частковими похідними щодо в’язкості — це математична концепція, яка не існувала до 1980-х років і пропонує унікальну лінію міркувань щодо розв’язку рівняння Гамільтона-Якобі-Айзекса. Зараз добре відомо, що ця концепція актуальна для міркувань про оптимальне управління та проблеми теорії ігор.

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

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

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

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

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

«Тепер питання полягає в тому, які ще дилеми ми можемо вирішити?» – сказав Мілутінович.