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

В Алгоритм Лемке – Хаусона^[1] является алгоритм который вычисляет равновесие по Нэшу из биматрикс игра, названный в честь его изобретателей, Карлтон Э. Лемке и Дж. Т. Хаусон.Он считается «самым известным из комбинаторных алгоритмов для нахождения равновесия по Нэшу».^[2]

Описание

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

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

п₁ в р^м; позволять {Икс₁,...,Икс_м} обозначим координаты. P₁ определяется м неравенство Икс_я ≥ 0 для всех я ∈ {1,...,м}, и еще п неравенстваB_1,jИкс₁+ ... + B_м,jИкс_м ≤ 1, для всех j ∈ {1,...,п}.

п₂ в р^п; позволять {Икс_м+1,...,Икс_м+п} обозначим координаты. P₂ определяется п неравенство Икс_м+я ≥ 0 для всех я ∈ {1,...,п}, и еще м неравенстваA_я,1Икс_м+1+ ... + А_я,пИкс_м+п ≤ 1, для всех я ∈ {1,...,м}.

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

Каждая вершина v из P₁ связан с набором меток из множества {1, ...,м + п} следующим образом. я ∈ {1, ..., м}, вершина v получает ярлык я если Икс_я = 0 в вершине v.За j ∈ {1, ..., п}, вершина v получает ярлык м + j если B_1,jИкс₁ + ... + B_м,jИкс_м = 1. Предполагая, что п₁ невырожден, каждая вершина инцидентна мграни п₁ и имеет м Отметим, что начало координат, являющееся вершиной P₁, имеет метки {1, ...,м}.

Каждая вершина ш из п₂ связан с набором меток из множества {1, ...,м + п} следующим образом. j ∈ {1, ..., п}, вершина ш получает ярлык м + j если Икс_м+j = 0 в вершинеш.За я ∈ {1, ..., м}, вершина ш получает ярлык я еслиА_я,1Икс_м+1 + ... + А_я,пИкс_м+п = 1. Предполагая, что P₂ невырожден, каждая вершина инцидентна пграни P₂ и имеет п Отметим, что начало координат, являющееся вершиной P₂, имеет ярлыки {м + 1, ..., м + п}.

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

А поворотная операция состоит из взятия некоторой пары (v,ш) и заменив v с некоторой вершиной, смежной с v в P₁, или, альтернативно, замена ш с некоторой вершиной, смежной с ш в P₂. Это имеет эффект (в случае, еслиv заменяется) замены некоторой метки v с другой меткой. Замененная метка называется упавший. Учитывая любой ярлык v, можно отбросить эту метку, переместившись в вершину, смежную с v который не содержит гиперплоскости, связанной с этой меткой.

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

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

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

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

Хотя алгоритм эффективен на практике, в худшем случае может потребоваться, чтобы количество опорных операций было экспоненциальным по отношению к количеству чистых стратегий в игре.^[4]Впоследствии было показано, что это PSPACE-полный найти любое из решений, которые могут быть получены с помощью алгоритма Лемке – Хаусона.^[5]

Рекомендации