Алгоритм Лемке – Хаусона

Алгоритм Лемке-Хаусона — это алгоритм , который вычисляет равновесие Нэша в биматричной игре , названный в честь его изобретателей Карлтона Э. Лемке и Дж. Т. Хаусона . Говорят, что это «наиболее известный среди комбинаторных алгоритмов поиска равновесия Нэша». хотя в последнее время алгоритм Портера-Нудельмана-Шохама превзошла по ряду показателей.

Описание

Входными данными для алгоритма является игра G для двух игроков . Здесь G представлена ​​двумя m × n игровыми матрицами размера A и B , содержащими выигрыши для игроков 1 и 2 соответственно, которые имеют m и n чистых стратегий соответственно. Далее предполагается, что все выигрыши положительны. (Благодаря изменению масштаба любую игру можно превратить в стратегически эквивалентную игру с положительными выигрышами.)

G имеет два соответствующих многогранника (называемых многогранниками наилучшего ответа ) P ₁ и P ₂ в измерениях m и n соответственно, определяемых следующим образом:

• P ₁ находится в R ^м ; пусть { x ₁ ,..., x _m } обозначают координаты. P ₁ определяется m неравенствами x _i ≥ 0 для всех i ∈ {1,..., m } и еще n неравенствами $$B_{1,j}x_{1}+\dots +B_{m,j}x_{m}\leq 1,$$ для всех j ∈ {1,..., n } .
• P ₂ находится в R ^н ; пусть { x _{m +1} ,..., x _{m + n} } обозначают координаты. P ₂ определяется n неравенствами x _{m + i} ≥ 0 для всех i ∈ {1,..., n } и еще m неравенствами $$A_{i,1}x_{m+1}+\dots +A_{i,n}x_{m+n}\leq 1,$$ для всех i ∈ {1,..., m } .

Здесь P ₁ представляет собой набор ненормализованных распределений вероятностей по игрокам 1. m чистых стратегий, таких, что ожидаемый выигрыш игрока 2 не превышает 1. Первые m ограничений требуют, чтобы вероятности были неотрицательными, а остальные n ограничений требуют, чтобы каждая из n чистых стратегий игрока 2 имела ожидаемый выигрыш при большинство 1. P ₂ имеет аналогичное значение, меняя роли игроков.

Каждой вершине v графа P1 _{множества} сопоставлен набор меток из {1,..., m + n } следующим образом. Для i ∈ {1, ..., m } вершина v получает метку i, если x _i = 0 в вершине v . Для j ∈ {1, ..., n } вершина v получает метку m + j, если $$B_{1,j}x_{1}+\dots +B_{m,j}x_{m}=1.$$ Предполагая, что P ₁ невырожден, каждая вершина инцидентна m граням P ₁ и имеет m меток. Обратите внимание, что начало координат, которое является вершиной P ₁ , имеет метки {1, ..., m } .

Каждой вершине графа P2 сопоставлен _w набор меток из множества {1, ..., m + n } следующим образом. Для j ∈ {1, ..., n } вершина w получает метку m + j, если x _{m + j} = 0 в вершине w . Для i ∈ {1, ..., m } вершина w получает метку i, если $$A_{i,1}x_{m+1}+\dots +A_{i,n}x_{m+n}=1.$$ Предполагая, что невырождена _P2 , каждая вершина инцидентна n граням P2 _n и имеет меток . Обратите внимание, что начало координат, которое является вершиной P ₂ , имеет метки { m + 1, ..., m + n } .

Рассмотрим пары вершин ( v , w ) , v ∈ P ₁ , w ∈ P ₂ . Пары вершин ( v , w ) называются полностью помеченными, если множества, связанные с v и w, содержат все метки {1, ..., m + n } . Обратите внимание, что если v и w являются началами R ^м и Р ^н соответственно, тогда ( v , w ) полностью помечено. Пары вершин ( v , w ) называются почти полностью помеченными (относительно некоторой отсутствующей метки g ), если множества, связанные с v и w, содержат все метки в {1, ..., m + n }, кроме г . Обратите внимание, что в этом случае будет повторяющаяся метка , связанная как с v , так и с w .

Операция поворота состоит из взятия некоторой пары ( v , w ) и замены v на некоторую смежную с v в P1 _{вершину ,} , или, альтернативно, замену некоторой вершиной, смежной с w в P2 _w . Это имеет эффект (в случае, если v заменяется) замены некоторой метки v какой-то другой меткой. Говорят, что замененная метка отброшена . Учитывая любую метку v , можно удалить эту метку, перейдя к вершине, смежной с v , которая не содержит гиперплоскости, связанной с этой меткой.

Алгоритм начинается с полностью помеченной пары ( v , w ), состоящей из пары начальных координат. Произвольная метка g удаляется с помощью операции поворота, что приводит нас к почти полностью помеченной паре ( v ′ , w ′ ) . Любая почти полностью помеченная пара допускает две операции поворота, соответствующие удалению той или иной копии ее дублированной метки, и каждая из этих операций может привести к созданию другой почти полностью помеченной пары или полностью помеченной пары. В конечном итоге алгоритм находит полностью помеченная пара ( v ^* , В ^* ) , что не является началом координат. ( в ^* , В ^* ) соответствует паре ненормализованных распределений вероятностей, в которых каждая стратегия i игрока 1 либо платит этому игроку 1, либо платит меньше 1 и используется этим игроком с вероятностью 0 (аналогичное наблюдение справедливо и для игрока 2). Нормализуя эти значения к распределениям вероятностей, мы получаем равновесие Нэша (выигрыши которого для игроков являются обратными факторам нормализации).

Характеристики

Алгоритм может найти не более n + m различных равновесий Нэша. Любой выбор изначально отброшенной метки определяет равновесие, которое в конечном итоге находится алгоритмом.

Алгоритм Лемке-Хаусона эквивалентен следующему гомотопическому подходу. Измените G , выбрав произвольную чистую стратегию g и предоставив игроку, владеющему этой стратегией, большую плату B за ее игру. В модифицированной игре стратегия g используется с вероятностью 1, а другой игрок будет использовать свой лучший ответ на g с вероятностью 1. Рассмотрим континуум игр, в которых B непрерывно сводится к 0. Существует путь равновесия Нэша. соединяющее единственное равновесие модифицированной игры с равновесием G . Чистая стратегия g, выбранная для получения бонуса B, соответствует первоначально выпавшей метке. Хотя на практике алгоритм эффективен, в худшем случае количество операций поворота может экспоненциально зависеть от количества чистых стратегий в игре. Впоследствии было показано, что PSPACE-полно найти любое из решений. которые можно получить с помощью алгоритма Лемке–Хаусона.