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

Лемке-Хаусон алгоритам је алгоритам за рачунање Нешовог еквилибријума двоматричне игре. Тврди се да је ово "најбољи познати комбинаторни алгоритам за проналажење Нешовог еквилибријума".

Алгоритам

Улаз алгоритма је игра два играча, Г. Г је представљена матрицама игара А и Б, димензија м × н, које садрже добити играча 1 и 2 респективно, који имају м и н чистих стратегија респективно. Од сада па надаље претпостављамо да су све добити позитивне (јер се скалирањем свака игра може трансформисати у стратешки еквивалентну игру са позитивним добитима).

Г има два одговарајућа политопа (звани политопи најбољег одзива) П₁ и П₂, у м димензија и н димензија респективно, дефинисана на следећи начин:

П₁ је из Р^м; нека {x₁,...,x_м} представља координате. П₁ је дефинисано са м неједнакости x_и ≥ 0, за све и ∈ {1,...,м}, и додатних н неједнакости Б_1,јx₁+...+Б_м,јx_м ≤ 1, за све ј ∈ {1,...,н}.

П₂ је из Р^н; нека {x_м+1,...,x_м+н} представља координате. П₂ је дефинисано са н неједнакости x_м+и ≥ 0, за све и ∈ {1,...,н}, и додатних м неједнакости А_и,1x_м+1+...+А_и,нx_м+н ≤ 1, за све и ∈ {1,...,м}.

П₁ представља скуп ненормализованих расподела вероватноће за м чистих стратегија играча 1, тако да је очекивана добит играча 2 највише 1. Првих м услова ограничава вероватноће на ненегативне вредности, а других н услова ограничава очекивану добит сваке од н чистих стратегија играча 2 на највише 1. П₂ има слично значење, при чему су улоге играча обрнуте.

Свако теме П₁ је повезано са скупом ознака из скупа {1,...,м + н} на следећи начин. За и ∈ {1, ..., м}, теме в добија ознаку и ако је x_и = 0 у темену в. За ј ∈ {1, ..., н}, теме в добија ознаку м + ј ако је Б_1,јx₁ + ... + Б_м,јx_м = 1. Под претпоставком да је П₁ недегенерисано, свако теме је везано за м пљосни П₁ и има м ознака. Приметимо да извор, који је теме П₁, има ознаке {1, ..., м}.

Свако теме П₂ повезано са скупом ознака из скупа {1, ..., м + н} на следећи начин. За ј ∈ {1, ..., н}, Теме w добија ознаку м + ј ако је x_м+ј = 0 у темену w. За и ∈ {1, ..., м}, теме w добија ознаку и ако је А_и,1x_м+1 + ... + А_и,нx_м+н = 1. Под претпоставком да је П₂ недегенерисано, свако теме је везано за м пљосни П₂ и има м ознака. Приметимо да извор, који је теме П₂, има ознаке {м + 1, ..., м + н}.

Посматрајмо пар темена (в,w), в ∈ П₁, w ∈ П₂. Кажемо да је (в,w) потпуно означен ако скупови придружени в и w садрже све ознаке из {1, ..., м + н}. Приметимо да ако су в анд w извори Р^м и Р^н респективно, онда је (в,w) потпуно означен. Кажемо да је (в,w) скоро потпуно означен (у погледу недостајуће ознаке г) ако скупови придружени в и w садрже све ознаке из {1, ..., м + н} осим г. У том случају ће постојати дупликатна ознака која је придружена и в и w.

Пивот операција подразумева замену в у пару (в,w) неким другим теменом суседним в у П₁, или алтернативно заменом w неким другим теменом суседним w у П₂. Ефекат операције је (у случају да је в замењено) замена неке ознаке в неком другом ознаком. За замењену ознаку се каже да је одбачена. За било коју задату ознаку в, могуће је одбацити дату ознаку померањем на теме суседно в које не садржи хиперраван повезану са том ознаком.

Алгоритам полази од потпуно означеног пара (в,w) састављеног од пара извора. Произвољена ознака г се одбаци пивот операцијом, доводећи нас до скоро потпуно означеног пара (в′,w′). Било који скоро потпуно означени пар подлеже двема пивот операцијама које одговарају одбацивању једне или друге копије дупликатне ознаке и свака од ових операција може резултовати новим скоро потпуно означеним паром или комплетно означеним паром. Најзад, алгоритам проналази потпуно означени пар (в^*,w^*), који није извор. (в^*,w^*) одговара пару ненормализованих расподела вероватноће у којима свака стратегија и играча 1 доноси добит 1, или доноси добит мању од 1 и играна је са вероватноћом 0 од стране играча 1 (слично опажање важи и за играча 2). Нормализовањем ових вредности на расподеле вероватноће добијамо Нешов еквилибријум (чије добити за играче су инверзије нормализационих фактора).

Особине алгоритма

Алгоритам може да пронађе највише н + м различитих Нешових еквилибријума. Избор првобитно одбачене ознаке одређује који ће еквилибријум на крају алгоритам да пронађе.

Лемке-Хаусон алгоритам је еквивалентан следећем приступу заснованом на хомотопији: Модификовати Г одабиром произвољне чисте стратегије г и дати играчу који поседује ту стратегију велику исплату Б да је одигра. У модификованој игри, стратегија г се игра са вероватноћом 1, а други играч одиграва свој најбољи одговор на стратегију г са вероватноћом 1. Разматрати континуум игара у којима се Б стално смањује до 0. Постоји путања Нешових еквилибријума која повезује јединствени еквилибријум модификоване игре са еквилибријумом Г. Чиста стратегија г одабрана да добије бонус Б одговара првобитно одбаченој ознаци.

Иако је алгоритам ефикасан у пракси, у најгорем случају број пивот операција може експоненцијално зависити од броја чистих стратегија у игри. Такође, показано је да је проблем проналажења решења помоћу Лемке-Хаусон алгоритма ПСПАЦЕ-комплетан.